Maharashtra Board Class 12 Maths Part 2 Chapter 7 Assignment Problem 7.2 Solutions

Question 1. A machine operator has to perform two operations, turning and threading on 6 different jobs. The time required to perform these operations (in minutes) for each job is known. Determine the order in which the jobs should be processed in order to minimize the total time required to complete all the jobs. Also, find the total processing time and idle times for turning and threading operations.
Answer: Solution: Let turning to be A and threading be B.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका 6 विभिन्न नौकरियों (जॉब 1 से 6) के लिए टर्निंग और थ्रेडिंग प्रक्रियाओं के लिए आवश्यक समय (मिनटों में) को दर्शाती है। 'टाइम फॉर टर्निंग' मशीन A पर लगने वाला समय है और 'टाइम फॉर थ्रेडिंग' मशीन B पर लगने वाला समय है।

ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका 6 विभिन्न नौकरियों के लिए टर्निंग (A) और थ्रेडिंग (B) प्रक्रियाओं के लिए आवश्यक समय (मिनटों में) को दर्शाती है, जिसे जॉब शेड्यूलिंग समस्या को हल करने के लिए उपयोग किया जाता है।

Observe Min{A, B} = 1 for job 6 on B.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब 6 को पहले संसाधित किया गया है।

Then the problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब 6 को संसाधित करने के बाद शेष 5 नौकरियों के लिए टर्निंग (A) और थ्रेडिंग (B) प्रक्रियाओं के लिए आवश्यक समय को दर्शाती है।

Now Min {A, B} = 2 for job 4 on A
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब 4 को अगली संसाधित किया गया है, उसके बाद जॉब 6 है।

Then the problem reduce to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब 4 को संसाधित करने के बाद शेष 4 नौकरियों के लिए टर्निंग (A) और थ्रेडिंग (B) प्रक्रियाओं के लिए आवश्यक समय को दर्शाती है।

Now Min {A, B} = 3 for job 1 on A and job 5 on B
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब 1 और 5 को उनके न्यूनतम समय के आधार पर अनुक्रम में रखा गया है।

Then the problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब 1 और 5 को संसाधित करने के बाद शेष 2 नौकरियों के लिए टर्निंग (A) और थ्रेडिंग (B) प्रक्रियाओं के लिए आवश्यक समय को दर्शाती है।

Now Min {A, B) = 5 for job 3 on A
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब 3 को उसके न्यूनतम समय के आधार पर अनुक्रम में रखा गया है।

Only job 2 is left so the optimal sequence is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका सभी नौकरियों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है, जिसे जॉनसन के एल्गोरिथम का उपयोग करके निर्धारित किया गया है।

Worktable is given by
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक जॉब के लिए मशीन A (टर्निंग) और मशीन B (थ्रेडिंग) पर इन-टाइम, आउट-टाइम और मशीन B के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और मशीन निष्क्रियता का निर्धारण होता है।

Total elapsed time = 43 minutes Idle time for A (turning) = 43 - 42 = 1 min Idle time for B (threshing) = 2 + 4 = 6 min
In simple words: To minimize total time, jobs are sequenced using Johnson's algorithm, processing jobs with shorter A-times first and shorter B-times last. The calculated total elapsed time is 43 minutes, with 1 minute idle time for turning and 6 minutes for threading.

🎯 Exam Tip: Focus on accurately applying Johnson's rule for sequencing two-machine problems. Clearly show the step-by-step reduction of jobs and the final worktable calculation for elapsed time and idle times to secure full marks.

Question 2. A company has three jobs on hand, Each of these must be processed through two departments, in the AB where Department A: Press shop and Department B: Finishing The table below gives the number of days required by each job each department
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका तीन नौकरियों (I, II, III) के लिए दो विभागों (A: प्रेस शॉप और B: फिनिशिंग) में आवश्यक दिनों की संख्या को दर्शाती है, जिसे प्रसंस्करण अनुक्रम को अनुकूलित करने के लिए उपयोग किया जाता है।

Find the sequence in which the three jobs should be processed so as to take minimum time to finish all the three jobs. Also find idle time for both the departments.
Answer: Solution: Observe Min {A, B} = 3 for job II on B.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब II को पहले संसाधित किया गया है।

Then the problem is reduced to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब II को संसाधित करने के बाद शेष 2 नौकरियों के लिए विभाग A और B में आवश्यक दिनों की संख्या को दर्शाती है।

Now Min {A, B} = 4 for job III at B
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब III को II के बाद संसाधित किया गया है।

Now only job I in left
\( \implies \) the optimal sequence is given by
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉनसन के एल्गोरिथम का उपयोग करके प्राप्त तीन नौकरियों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है।

The work table is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक जॉब के लिए विभाग A और B पर इन-टाइम, आउट-टाइम और विभाग B के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और विभागों की निष्क्रियता का निर्धारण होता है।

Total elapsed time = 23 days Idle time for A = 23 - 19 = 4 days Idle time for B = 8 days
In simple words: Using Johnson's algorithm, the optimal sequence to minimize total time for the three jobs is I-III-II. The total elapsed time for all jobs is 23 days. Department A will be idle for 4 days, and Department B will be idle for 8 days.

🎯 Exam Tip: When solving sequencing problems, always clearly state the optimal sequence derived from Johnson's rule. Follow up by constructing a detailed worktable to correctly calculate the total elapsed time and individual machine idle times, as this is crucial for evaluation.

Question 3. An insurance company receives three types of policy application bundles daily from its head office for data entry and filing. The time (in minutes) required for each type for these two operations is given in the following table:
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका तीन प्रकार की पॉलिसी (1, 2, 3) के लिए डेटा एंट्री और फाइलिंग प्रक्रियाओं में आवश्यक समय (मिनटों में) को दर्शाती है, जिसका उपयोग कुल कार्य पूरा करने में लगने वाले न्यूनतम समय को निर्धारित करने के लिए किया जाता है।

Find the sequence that minimizes the total time required to complete the entire task. Also, find the total elapsed time and idle times for each operation.
Answer: Solution: Let Data entry be A and filing be B. So
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका तीन पॉलिसी प्रकारों (1, 2, 3) के लिए डेटा एंट्री (A) और फाइलिंग (B) प्रक्रियाओं के लिए आवश्यक समय को पुनर्व्यवस्थित करती है, जिसे जॉनसन के एल्गोरिथम के आवेदन के लिए तैयार किया गया है।

Observe min {A, B} = 90 for policy 1 at A
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका पॉलिसी शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें पॉलिसी 1 को पहले संसाधित किया गया है।

Then the problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका पॉलिसी 1 को संसाधित करने के बाद शेष 2 पॉलिसी प्रकारों के लिए डेटा एंट्री (A) और फाइलिंग (B) प्रक्रियाओं के लिए आवश्यक समय को दर्शाती है।

Observe min {A, B} = 100 for policy 3 at B
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका पॉलिसी शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें पॉलिसी 3 को 1 के बाद संसाधित किया गया है।

Now only policy 2 is left
\( \implies \) The optimal sequence is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉनसन के एल्गोरिथम का उपयोग करके प्राप्त तीनों पॉलिसी प्रकारों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है।

Worktable
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक पॉलिसी के लिए डेटा एंट्री (A) और फाइलिंग (B) प्रक्रियाओं पर इन-टाइम, आउट-TIME और फाइलिंग के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और संचालन की निष्क्रियता का निर्धारण होता है।

So Total elapsed time = 490 min Idle time for A (data entry) = 490 - 390 = 100 min Idle time for B (filing) = 140 min.
In simple words: The optimal sequence for processing policies to minimize total time is 1-2-3. The total elapsed time for completing all tasks is 490 minutes. Data entry (A) will be idle for 100 minutes, and filing (B) will be idle for 140 minutes.

🎯 Exam Tip: Remember to clearly define the machines (A and B) and apply Johnson's rule methodically. The final worktable should correctly calculate 'In' and 'Out' times for each job on both machines, leading to accurate total elapsed time and idle time computations.

Question 4. There are five jobs, each of which must go through two machines in the order XY. Processing times (in hours) are given below. Determine the sequence for the jobs that will minimize the total elapsed time. Also, find the total elapse time and idle time for each machine.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका पाँच विभिन्न नौकरियों (A, B, C, D, E) के लिए मशीन X और मशीन Y पर आवश्यक प्रसंस्करण समय (घंटों में) को दर्शाती है, जिसका उपयोग कुल बीता हुआ समय को कम करने वाले अनुक्रम को निर्धारित करने के लिए किया जाता है।

Answer: Solution: Observe min {x, y} = 2 for job B on x
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब B को पहले संसाधित किया गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब B को संसाधित करने के बाद शेष 4 नौकरियों (A, C, D, E) के लिए मशीन X और Y पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min [x, y] = 4 for job A on x
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब A को अनुक्रम में अंतिम स्थिति में रखा गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब A को संसाधित करने के बाद शेष 3 नौकरियों (C, D, E) के लिए मशीन X और Y पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min [x, y] = 6 for job D on x
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब D को B के तुरंत बाद अनुक्रम में रखा गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब D को संसाधित करने के बाद शेष 2 नौकरियों (C, E) के लिए मशीन X और Y पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min [x, y] = 8 for job E on y
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब E को A से पहले अनुक्रम में रखा गया है।

Now only job C in left
\( \implies \) The optimal sequence is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉनसन के एल्गोरिथम का उपयोग करके प्राप्त पाँच नौकरियों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है।

Worktable
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक जॉब के लिए मशीन X और मशीन Y पर इन-टाइम, आउट-टाइम और मशीन Y के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और मशीनों की निष्क्रियता का निर्धारण होता है।

Total elapsed time = 60 hrs Idle time for X = 60 - 56 = 4 hrs Idle time for Y = 6 hrs
In simple words: The optimal sequence to minimize total elapsed time for the five jobs is B-D-C-E-A. The total time to complete all jobs is 60 hours. Machine X will be idle for 4 hours, and Machine Y will be idle for 6 hours.

🎯 Exam Tip: Systematically apply Johnson's rule by identifying the minimum processing times and placing jobs accordingly (left for machine X, right for machine Y). Ensure that the worktable calculations for 'In' and 'Out' times are precise, as errors here will affect the total elapsed time and idle times significantly.

Question 5. Find the sequence that minimizes the total elapsed time to complete the following jobs in the order AB. Find the total elapsed time and idle times for both machines.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका सात विभिन्न नौकरियों (I से VII) के लिए मशीन A और मशीन B पर आवश्यक प्रसंस्करण समय को दर्शाती है, जिसका उपयोग कुल बीता हुआ समय को कम करने वाले अनुक्रम को निर्धारित करने के लिए किया जाता है।

Answer: Solution: Observe min {A, B} = 5 for job VI for B and job VII for A
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब VII को सबसे पहले और जॉब VI को सबसे बाद में संसाधित किया गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब VII और VI को संसाधित करने के बाद शेष 5 नौकरियों (I, II, III, IV, V) के लिए मशीन A और B पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min {A, B] = 7 for job I on A
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब I को VII के तुरंत बाद अनुक्रम में रखा गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब I को संसाधित करने के बाद शेष 4 नौकरियों (II, III, IV, V) के लिए मशीन A और B पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min {A, B] = 10 for job IV on A and B so we have two options.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए दो वैकल्पिक इष्टतम अनुक्रमों में से एक को दर्शाती है, जिसमें जॉब IV को उसकी न्यूनतम समय के आधार पर अनुक्रम में रखा गया है।

Or
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए दो वैकल्पिक इष्टतम अनुक्रमों में से दूसरे को दर्शाती है, जिसमें जॉब IV को उसकी न्यूनतम समय के आधार पर अनुक्रम में रखा गया है।

we take the 1st one. The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब IV को संसाधित करने के बाद शेष 3 नौकरियों (II, III, V) के लिए मशीन A और B पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min {A, B} = 14 for job V on A and job II and III for job B.
\( \implies \) We have
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए एक संभावित आंशिक अनुक्रम को दर्शाती है, जिसमें जॉब V को I के बाद रखा गया है और जॉब II और III को VI से पहले रखा गया है।

Or
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए एक वैकल्पिक संभावित आंशिक अनुक्रम को दर्शाती है, जिसमें जॉब V को I के बाद रखा गया है और जॉब III और II को VI से पहले रखा गया है।

We take the optimal sequence as. VII-I-IV - V - III - II - VI Worktable
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक जॉब के लिए मशीन A और मशीन B पर इन-टाइम, आउट-टाइम और मशीन B के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और मशीनों की निष्क्रियता का निर्धारण होता है।

Total elapsed time = 91 units Idle time for A = 91 - 86 = 5 units Idle time for B = 13 units
In simple words: The optimal sequence to minimize total elapsed time for the seven jobs is VII-I-IV-V-III-II-VI. The total time to complete all jobs is 91 units. Machine A will be idle for 5 units, and Machine B will be idle for 13 units.

🎯 Exam Tip: When multiple jobs have the minimum processing time, choose the one with the shorter time on the first machine (for the left side of the sequence) or the longer time on the second machine (for the right side). Carefully constructing the worktable is crucial for accurate calculation of idle times and total elapsed time.

Question 6. Find the optimal sequence that minimizes the total time required to complete the following jobs in the order ABC. The processing times are given in hrs.
(i)
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका सात विभिन्न नौकरियों (I से VII) के लिए तीन मशीनों (A, B, C) पर आवश्यक प्रसंस्करण समय (घंटों में) को दर्शाती है, जिसे कुल समय को कम करने वाले इष्टतम अनुक्रम को निर्धारित करने के लिए उपयोग किया जाता है।

(ii)
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका पाँच विभिन्न नौकरियों (1 से 5) के लिए तीन मशीनों (A, B, C) पर आवश्यक प्रसंस्करण समय को दर्शाती है, जिसे कुल समय को कम करने वाले इष्टतम अनुक्रम को निर्धारित करने के लिए उपयोग किया जाता है।

Answer: Solution: (i) Min A = 5, Max B = 5 As min A ≥ max B. The problem can be converted into two machine problems. Let G and H be two fictitious machines such that G = A + B and H = B + C we get
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका तीन मशीनों (A, B, C) वाली समस्या को दो काल्पनिक मशीनों (G = A+B, H = B+C) में बदलने के बाद सात नौकरियों के लिए प्रसंस्करण समय को दर्शाती है, जिसका उपयोग जॉनसन के एल्गोरिथम को लागू करने के लिए किया जाता है।

Now min {G, H} = 7 for job III & V for G and job I for H
\( \implies \) We have two options
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए दो वैकल्पिक इष्टतम अनुक्रमों में से एक को दर्शाती है, जिसमें जॉब V और III को उनकी न्यूनतम समय के आधार पर अनुक्रम में रखा गया है।

Or
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए दो वैकल्पिक इष्टतम अनुक्रमों में से दूसरे को दर्शाती है, जिसमें जॉब III और V को उनकी न्यूनतम समय के आधार पर अनुक्रम में रखा गया है।

We take the first one The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब V, III और I को संसाधित करने के बाद शेष 4 नौकरियों (II, IV, VI, VII) के लिए काल्पनिक मशीन G और H पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Min {G, H} = 9 for job IV on H
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब IV को I से पहले अनुक्रम में रखा गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब IV को संसाधित करने के बाद शेष 3 नौकरियों (II, VI, VII) के लिए काल्पनिक मशीन G और H पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min {G, H} = 10 for job II for G and job VII for H
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब II को V, III के बाद और जॉब VII को IV, I से पहले अनुक्रम में रखा गया है।

Now job VI is left
\( \implies \) The optimal sequence is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉनसन के एल्गोरिथम का उपयोग करके प्राप्त सात नौकरियों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है।

The work table is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक जॉब के लिए मशीन A, B और C पर इन-टाइम, आउट-टाइम और मशीन B व C के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और मशीनों की निष्क्रियता का निर्धारण होता है।

Total elapsed time = 61 hrs Idle time for A = 61 - 54 = 7 hrs Idle time for B = 35 + [61 - 58] = 38 hrs Idle time for C = 15 hrs
In simple words: For the seven jobs processed through three machines, the optimal sequence is V-III-II-VI-VII-IV-I. This sequence results in a total elapsed time of 61 hours. Machine A is idle for 7 hours, Machine B for 38 hours, and Machine C for 15 hours.

🎯 Exam Tip: For three-machine problems, correctly convert it into an equivalent two-machine problem using the condition (Min A ≥ Max B or Min C ≥ Max B). Then apply Johnson's algorithm to the fictitious machines. Remember to construct a comprehensive worktable for all three original machines to calculate total elapsed time and individual idle times accurately.

(ii) Min A = 5, Max B = 5 Min A ≥ Max B. The problem can be converted into two machine problems. Let G and H be two fictitious machines such that G = A + B and H = B + C we get
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका तीन मशीनों (A, B, C) वाली समस्या को दो काल्पनिक मशीनों (G = A+B, H = B+C) में बदलने के बाद पाँच नौकरियों के लिए प्रसंस्करण समय को दर्शाती है, जिसका उपयोग जॉनसन के एल्गोरिथम को लागू करने के लिए किया जाता है।

Now min {G, H} = 5 for job 1 for H.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब 1 को अंत में संसाधित किया गया है।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब 1 को संसाधित करने के बाद शेष 4 नौकरियों (2, 3, 4, 5) के लिए काल्पनिक मशीन G और H पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min {G, H} = 8 for job 2 for G and job H also job 5 for G
\( \implies \) We have two options
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए दो वैकल्पिक इष्टतम अनुक्रमों में से एक को दर्शाती है, जिसमें जॉब 2 को पहले और जॉब 5 को अंत में (जॉब 1 से पहले) अनुक्रम में रखा गया है।

Or
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए दो वैकल्पिक इष्टतम अनुक्रमों में से दूसरे को दर्शाती है, जिसमें जॉब 5 को पहले और जॉब 2 को अंत में (जॉब 1 से पहले) अनुक्रम में रखा गया है।

We take the first one The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब 2, 5 और 1 को संसाधित करने के बाद शेष 2 नौकरियों (3, 4) के लिए काल्पनिक मशीन G और H पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Now min {G, H} = 9 for job 3 for H
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉब शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें जॉब 3 को 5 के बाद और 1 से पहले अनुक्रम में रखा गया है।

Now only job 4 is left
\( \implies \) The optimal sequence is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉनसन के एल्गोरिथम का उपयोग करके प्राप्त पाँच नौकरियों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है।

Worktable
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक जॉब के लिए मशीन A, B और C पर इन-टाइम, आउट-टाइम और मशीन B व C के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और मशीनों की निष्क्रियता का निर्धारण होता है।

Total elapsed time = 40 hrs Idle time for A = 40 - 32 = 8 hrs Idle time for B = 19 + [40 - 34] = 25 hrs Idle time for C = 12 hrs
In simple words: For the five jobs processed through three machines, the optimal sequence is 2-5-4-3-1. This sequence results in a total elapsed time of 40 hours. Machine A is idle for 8 hours, Machine B for 25 hours, and Machine C for 12 hours.

🎯 Exam Tip: When multiple jobs yield the same minimum processing time on either fictitious machine, ensure you choose an option that keeps the job's position consistent with Johnson's rule (smaller value on G to the left, smaller value on H to the right). Accurately calculate cumulative idle times for the middle machine by accounting for both initial idle time and subsequent waiting times.

Question 7. A publisher produces 5 books on Mathematics. The books have to go through composing, printing, and binding was done by 3 machines P, Q, E. The time schedule for the entire task in the proper unit is as follows. Determine the optimum time required to finish the entire task.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका 5 पुस्तकों (A, B, C, D, E) के लिए तीन मशीनों (P, Q, R) पर आवश्यक प्रसंस्करण समय को दर्शाती है, जिसका उपयोग कुल कार्य पूरा करने में लगने वाले न्यूनतम समय को निर्धारित करने के लिए किया जाता है।

Answer: Solution: Min R = 6, Max Q = 6 As min R ≥ max Q. The problem can be converted into a two-machine problem. Let G and H be two fictitious machines such that G = P + Q and H = Q + R we get
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका तीन मशीनों (P, Q, R) वाली समस्या को दो काल्पनिक मशीनों (G = P+Q, H = Q+R) में बदलने के बाद पाँच पुस्तकों के लिए प्रसंस्करण समय को दर्शाती है, जिसका उपयोग जॉनसन के एल्गोरिथम को लागू करने के लिए किया जाता है।

Min {G, H} = 9 for books A, D, E for G.
\( \implies \) We have more than one option we take
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका बुक शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें किताबें D, A, E को पहले संसाधित किया गया है, क्योंकि उनके G-मशीन पर न्यूनतम समय हैं।

The problem reduces to
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका किताबें D, A, E को संसाधित करने के बाद शेष 2 पुस्तकों (B, C) के लिए काल्पनिक मशीन G और H पर आवश्यक प्रसंस्करण समय को दर्शाती है।

Min {G, H} = 8 for book C on H
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका बुक शेड्यूलिंग के लिए इष्टतम अनुक्रम को दर्शाती है, जिसमें बुक C को अंत में संसाधित किया गया है (D, A, E के बाद)।

Now only B is left. So the optimal sequence is
ℹ️ चित्र व्याख्या (Diagram Explanation): यह तालिका जॉनसन के एल्गोरिथम का उपयोग करके प्राप्त सभी पांच पुस्तकों के लिए अंतिम इष्टतम प्रसंस्करण अनुक्रम को दर्शाती है।

Worktable
ℹ️ चित्र व्याख्या (Diagram Explanation): यह कार्य तालिका प्रत्येक पुस्तक के लिए मशीन P, Q और R पर इन-टाइम, आउट-टाइम और मशीन Q व R के लिए निष्क्रिय समय को दर्शाती है, जिससे कुल बीता हुआ समय और मशीनों की निष्क्रियता का निर्धारण होता है।

Total elapsed time = 51 units Idle time for P = 51 - 32 = 19 units Idle time for Q = 14 + [51 - 34] = 31 units Idle time for R = 9 units
In simple words: The optimal sequence for processing the five books on three machines (P, Q, R) is D-A-E-B-C. This sequence minimizes the total elapsed time to 51 units. Machine P has an idle time of 19 units, Machine Q has 31 units, and Machine R has 9 units.

🎯 Exam Tip: When dealing with three-machine problems that satisfy Johnson's conditions (Min P ≥ Max Q or Min R ≥ Max Q), always transform them into a two-machine problem. The most critical part is setting up the correct worktable for all three original machines (P, Q, R) to accurately calculate the total elapsed time and all individual idle times.