Skip to content
Worked Examples · Example 11
Q.

Five jobs must be processed through three machines in the order M1→M2→M3M_1 \to M_2 \to M_3. The times (in hours) are:

Job12345
M1M_18106711
M2M_256234
M3M_399899

Show that the problem can be converted to a two-machine problem, find the optimal sequence, and compute the total elapsed time.

Maharashtra MsbshseTextbookSubjectiveImportance★★★★★
41% · 13/32 Questions
🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Step 1 — Test the conversion condition.

min⁡i(M1)=6,max⁡i(M2)=6.\min_i(M_1) = 6, \qquad \max_i(M_2) = 6.

Since min⁡M1=6≥max⁡M2=6\min M_1 = 6 \ge \max M_2 = 6, the condition min⁡Ai≥max⁡Bi\min A_i \ge \max B_i is satisfied, so the problem may be converted to a two-machine problem.

Step 2 — Form the fictitious machines Gi=Ai+BiG_i = A_i + B_i and Hi=Bi+CiH_i = B_i + C_i:

Job12345
G=M1+M2G = M_1 + M_2131681015
H=M2+M3H = M_2 + M_31415101213

Step 3 — Johnson's rule on (G,H)(G, H).

  • Smallest =8= 8 (job 33, on GG) →\to first: (3,−,−,−,−)(3,-,-,-,-).
  • Next =10= 10 (job 44, on GG) →\to next earliest: (3,4,−,−,−)(3,4,-,-,-).
  • Remaining 1,2,51,2,5: smallest =13= 13 — job 11 on GG (→\to earliest free) and job 55 on HH (→\to latest free): (3,4,1,−,5)(3,4,1,-,5).
  • Last job 22 takes the middle: (3,4,1,2,5)(3,4,1,2,5).

Optimal sequence: 3→4→1→2→53 \to 4 \to 1 \to 2 \to 5.

Step 4 — In/out-time table on the real machines (in-time =max⁡(out-time on previous machine, previous job’s out-time on this machine)= \max(\text{out-time on previous machine, previous job's out-time on this machine})):

JobM1M_1 inM1M_1 outM2M_2 inM2M_2 outM3M_3 inM3M_3 out
30668816
461313161625
1132121262635
2213131373746
5314242464655

Step 5 — Results. Total elapsed time == last M3M_3 out-time =55= \mathbf{55} hours. …

Unlock everything free for 14 days

  • Full step-by-step solutions
  • Concept-first explanations
  • Methods, shortcuts & mistakes
  • PYQ mapping + timed mock tests

Full access for 14 days. No credit card required.