Skip to content

Lesson 15: Sequencing: n Jobs Through 3 Machines, 2 Jobs Through m Machines

15.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the condition under which a 3-machine problem reduces to 2 machines.
  2. Perform the \(G\)–\(H\) conversion and apply Johnson's rule.
  3. Construct the 3-machine in–out table.
  4. Solve 2 jobs through \(m\) machines by the graphical (45°) method.
  5. Read the optimal schedule and idle times from the graph.

15.2 n Jobs Through 3 Machines

The setup

Each job passes M1 → M2 → M3 in that order, with times \(A_i\), \(B_i\), \(C_i\).

The general 3-machine flow-shop problem is NP-hard. But a special case reduces exactly to Johnson's rule.

The reducibility condition

\[ \boxed{\ \textbf{Either } \ \min_i A_i \ \ge\ \max_i B_i \qquad \textbf{or} \qquad \min_i C_i \ \ge\ \max_i B_i\ } \]

At least one must hold. If neither does, this method is invalid and gives no guarantee.

The interpretation. The condition says the middle machine is never the bottleneck — it is dominated either by M1 (every job spends at least as long on M1 as any job does on M2) or by M3. When M2 cannot constrain the flow, the three-stage problem behaves like a two-stage one.

The G–H conversion

Define two fictitious machines:

\[ \boxed{\ G_i = A_i + B_i, \qquad H_i = B_i + C_i\ } \]

Apply Johnson's rule to the pairs \((G_i, H_i)\). The resulting sequence is optimal for the original 3-machine problem.

Why it works. Under the condition, the makespan is determined by the M1–M2 and M2–M3 transitions, which \(G\) and \(H\) capture exactly. The middle machine's contribution appears in both, which is why \(B_i\) is counted twice.

The in–out table

Now with three columns per job:

\[ \text{M1 start} = \text{previous job's M1 finish} \]
\[ \text{M2 start} = \max\big(\text{this job's M1 finish},\ \text{previous job's M2 finish}\big) \]
\[ \text{M3 start} = \max\big(\text{this job's M2 finish},\ \text{previous job's M3 finish}\big) \]

The same \(\max\) rule cascades down the machines.

15.3 Worked Example — 3 Machines

Five jobs, times in hours:

Job M1 (\(A\)) M2 (\(B\)) M3 (\(C\))
1 8 3 8
2 3 4 7
3 7 5 6
4 2 2 9
5 5 1 10

Step 1 — check the condition.

\[ \min_i A_i = \min(8,3,7,2,5) = \mathbf{2}, \qquad \max_i B_i = \max(3,4,5,2,1) = \mathbf{5}, \qquad \min_i C_i = \min(8,7,6,9,10) = \mathbf{6} \]
\[ \text{Condition 1: } \min A = 2 \ge 5 = \max B \ ? \qquad \textbf{NO} \]
\[ \text{Condition 2: } \min C = 6 \ge 5 = \max B \ ? \qquad \textbf{YES} \ \checkmark \]

At least one condition holds, so the conversion is valid.

Step 2 — compute \(G\) and \(H\).

Job \(A\) \(B\) \(C\) \(G = A+B\) \(H = B+C\)
1 8 3 8 11 11
2 3 4 7 7 11
3 7 5 6 12 11
4 2 2 9 4 11
5 5 1 10 6 11

(A striking coincidence: every \(H_i = 11\). This makes the ordering depend entirely on \(G\).)

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

Pass Smallest Machine Action Sequence
1 \(G_4 = 4\) G (=M1) job 4 first [4,_,_,_,_]
2 \(G_5 = 6\) G job 5 next [4,5,_,_,_]
3 \(G_2 = 7\) G job 2 next [4,5,2,_,_]
4 \(G_1 = 11\), \(H\) values all 11 — tie G job 1 next [4,5,2,1,_]
5 job 3 remains — fill [4,5,2,1,3]
\[ \boxed{\ \text{Optimal sequence: } 4 \to 5 \to 2 \to 1 \to 3\ } \]

Step 4 — the in–out table.

Job M1 in M1 out M2 in M2 out M3 in M3 out
4 0 2 2 4 4 13
5 2 7 7 8 13 23
2 7 10 10 14 23 30
1 10 18 18 21 30 38
3 18 25 25 30 38 44

Sample calculations.

Job 5 on M2: \(\max(\text{5's M1 finish}=7,\ \text{4's M2 finish}=4) = 7\). Job 5 on M3: \(\max(\text{5's M2 finish}=8,\ \text{4's M3 finish}=13) = 13\) — M3 is busy, so job 5 waits 5 hours.

\[ \boxed{\ \textbf{Total elapsed time} = 44\ \text{hours}\ } \]

Step 5 — idle times.

\[ \sum A = 25, \qquad \sum B = 15, \qquad \sum C = 40 \]
\[ \text{M1 idle} = 44 - 25 = \mathbf{19\ h} \quad (56.8\%\ \text{utilised}) \]
\[ \text{M2 idle} = 44 - 15 = \mathbf{29\ h} \quad (34.1\%\ \text{utilised}) \]
\[ \text{M3 idle} = 44 - 40 = \mathbf{4\ h} \quad (\mathbf{90.9\%}\ \text{utilised}) \]
\[ \boxed{\ \textbf{M3 is the clear bottleneck — 91 \% utilised while M2 sits idle two-thirds of the time.}\ } \]

Note how this validates the reducibility condition. Condition 2 (\(\min C \ge \max B\)) held, and indeed M3 dominates while M2 is nearly irrelevant to the makespan — exactly what the condition predicts.

Management implication. Any capacity investment belongs at M3. Speeding up M2 would achieve nothing.

15.4 Two Jobs Through m Machines — the Graphical Method

The setup

Two jobs, each with its own technological order through \(m\) machines (the orders may differ). Times are given per job per machine. Minimise total elapsed time.

The method

1. Draw axes: HORIZONTAL = cumulative processing time of Job 1
              VERTICAL   = cumulative processing time of Job 2
2. Mark each machine's interval on both axes (in that job's own order)
3. Shade RECTANGLES where BOTH jobs need the SAME machine -- these are FORBIDDEN
       (a machine cannot serve two jobs at once)
4. Start at the origin; move to the top-right corner
5. Allowed moves:
       HORIZONTAL  -> Job 1 processes, Job 2 waits
       VERTICAL    -> Job 2 processes, Job 1 waits
       45-DIAGONAL -> BOTH process simultaneously (on different machines)
6. MAXIMISE the diagonal travel -- diagonal movement is 'free' concurrency
7. Total elapsed time = (Job 1 total) + (Job 2's IDLE time)
                      = (Job 2 total) + (Job 1's IDLE time)

The key insight

\[ \boxed{\ \textbf{Diagonal movement = both jobs working at once. Every non-diagonal unit is WAITING.}\ } \]

The problem is therefore: find the path from origin to corner that maximises diagonal travel while avoiding the shaded (conflict) rectangles.

Elapsed time formula.

\[ \text{Total elapsed} = \sum(\text{Job 1 times}) + \text{Job 1's idle time} \]

15.5 Solved Problems

Problem 1 — Checking the condition before converting

For each data set, decide whether the 3-machine conversion is valid.

(a) \(A = (6,7,5,8)\), \(B = (2,3,1,2)\), \(C = (5,6,4,7)\) (b) \(A = (4,3,6)\), \(B = (5,7,4)\), \(C = (3,2,5)\) (c) \(A = (9,8,10)\), \(B = (4,6,5)\), \(C = (7,3,8)\)

Solution.

(a) \(\min A = 5\), \(\max B = 3\), \(\min C = 4\).

\[ \text{Condition 1: } 5 \ge 3 \ \checkmark \qquad \textbf{VALID} \]

(Condition 2 also fails to be needed: \(4 \ge 3\) ✓ — both hold, doubly safe.)

(b) \(\min A = 3\), \(\max B = 7\), \(\min C = 2\).

\[ \text{Condition 1: } 3 \ge 7 \ \textbf{✗}, \qquad \text{Condition 2: } 2 \ge 7 \ \textbf{✗} \]
\[ \boxed{\ \textbf{NEITHER holds — the conversion is INVALID.}\ } \]

What to do instead. The middle machine genuinely constrains the flow. Options:

  • Branch and bound for an exact answer (feasible up to ~15 jobs).
  • Apply the \(G\)–\(H\) heuristic anyway and accept a near-optimal answer, verifying by comparing against the lower bound \(\max(\sum A + \min(B+C),\ \ldots)\).
  • Use a metaheuristic (simulated annealing, tabu search) for large instances.

(c) \(\min A = 8\), \(\max B = 6\), \(\min C = 3\).

\[ \text{Condition 1: } 8 \ge 6 \ \checkmark \qquad \textbf{VALID} \]

Summary.

Case \(\min A\) \(\max B\) \(\min C\) Cond 1 Cond 2 Verdict
(a) 5 3 4 ✓ ✓ valid
(b) 3 7 2 ✗ ✗ INVALID
(c) 8 6 3 ✓ ✗ valid
\[ \boxed{\ \textbf{ALWAYS check the condition first. Applying the conversion blindly gives an answer with no guarantee.}\ } \]

Problem 2 — Complete 3-machine solution

Solve case (a) of Problem 1 fully:

Job M1 M2 M3
1 6 2 5
2 7 3 6
3 5 1 4
4 8 2 7

Solution.

Step 1 — condition. \(\min A = 5 \ge 3 = \max B\) ✓ VALID.

Step 2 — \(G\) and \(H\).

Job \(G = A+B\) \(H = B+C\)
1 \(6+2 = 8\) \(2+5 = 7\)
2 \(7+3 = 10\) \(3+6 = 9\)
3 \(5+1 = 6\) \(1+4 = 5\)
4 \(8+2 = 10\) \(2+7 = 9\)

Step 3 — Johnson on \((G,H)\).

Pass Smallest Machine Action Sequence
1 \(H_3 = 5\) H job 3 last [_,_,_,3]
2 \(G_3\) gone; next is \(H_1 = 7\) H job 1 next last [_,_,1,3]
3 \(H_2 = H_4 = 9\) (tie); take \(H_2\) H job 2 next last [_,2,1,3]
4 job 4 remains — fill [4,2,1,3]
\[ \boxed{\ \text{Sequence: } 4 \to 2 \to 1 \to 3\ } \]

Step 4 — in–out table.

Job M1 in M1 out M2 in M2 out M3 in M3 out
4 0 8 8 10 10 17
2 8 15 15 18 18 24
1 15 21 21 23 24 29
3 21 26 26 27 29 33

Sample: job 1 on M3: \(\max(23,\ 24) = 24\) — M3 still busy with job 2.

\[ \boxed{\ \textbf{Total elapsed time} = 33\ \text{hours}\ } \]

Step 5 — idle times.

\[ \sum A = 26, \quad \sum B = 8, \quad \sum C = 22 \]
\[ \text{M1 idle} = 33-26 = 7\ \text{h} \ (78.8\%) \]
\[ \text{M2 idle} = 33-8 = 25\ \text{h} \ (24.2\%) \]
\[ \text{M3 idle} = 33-22 = 11\ \text{h} \ (66.7\%) \]

M1 is the bottleneck here (78.8 % utilised), consistent with condition 1 holding (\(\min A \ge \max B\) means M1 dominates M2).

Sanity check against the lower bound.

\[ \text{makespan} \ \ge\ \sum A + \min_i(B_i + C_i) = 26 + \min(7,9,5,9) = 26 + 5 = 31 \]

We achieved 33 — within 6.5 % of the bound ✓.

Problem 3 — Two jobs through 5 machines, graphically

Job 1 order: \(M_1 \to M_2 \to M_3 \to M_4 \to M_5\) with times \((3, 4, 2, 6, 2)\). Job 2 order: \(M_3 \to M_1 \to M_4 \to M_5 \to M_2\) with times \((5, 4, 3, 2, 6)\). Find the minimum elapsed time.

Solution.

Step 1 — cumulative axes.

Job 1 (horizontal), in its own order:

Machine Time Interval
\(M_1\) 3 \([0, 3]\)
\(M_2\) 4 \([3, 7]\)
\(M_3\) 2 \([7, 9]\)
\(M_4\) 6 \([9, 15]\)
\(M_5\) 2 \([15, 17]\)

Job 1 total = 17.

Job 2 (vertical), in its own order:

Machine Time Interval
\(M_3\) 5 \([0, 5]\)
\(M_1\) 4 \([5, 9]\)
\(M_4\) 3 \([9, 12]\)
\(M_5\) 2 \([12, 14]\)
\(M_2\) 6 \([14, 20]\)

Job 2 total = 20.

Step 2 — the forbidden rectangles (where both jobs need the same machine):

Machine Job 1 interval (x) Job 2 interval (y) Forbidden rectangle
\(M_1\) \([0,3]\) \([5,9]\) \([0,3]\times[5,9]\)
\(M_2\) \([3,7]\) \([14,20]\) \([3,7]\times[14,20]\)
\(M_3\) \([7,9]\) \([0,5]\) \([7,9]\times[0,5]\)
\(M_4\) \([9,15]\) \([9,12]\) \([9,15]\times[9,12]\)
\(M_5\) \([15,17]\) \([12,14]\) \([15,17]\times[12,14]\)
 Job2
 20 |                    +------+
    |                    | M2   |
 14 |                    +------+
 12 |                        +--------+
    |                        |  M5    |
    |         +------------+ +--------+
  9 |  +---+  |    M4      |
    |  |M1 |  +------------+
  5 |  +---+       +---+
    |              |M3 |
  0 +--------------+---+-----------------  Job1
    0    3    7   9        15   17

Step 3 — find the path. Start at \((0,0)\), end at \((17, 20)\), moving right, up or diagonally, never entering a shaded rectangle.

From \((0,0)\): move diagonally. The \(M_3\) block occupies \(x\in[7,9], y\in[0,5]\) and the \(M_1\) block \(x\in[0,3], y\in[5,9]\). Moving diagonally from \((0,0)\) we reach \((3,3)\) — safe (below the \(M_1\) block's \(y\ge5\), left of the \(M_3\) block's \(x\ge7\)).

Continue diagonally to \((5,5)\) — safe. To \((7,7)\): now \(x = 7\) enters the \(M_3\) block's range, but \(y = 7 > 5\), so we are above it — safe ✓.

Continue to \((9,9)\) — the \(M_4\) block starts at \(x=9, y=9\). We must go around it.

Go up (Job 2 works, Job 1 waits) from \((9,9)\) to \((9,12)\) — passing the \(M_4\) block on its left edge. Job 1 idles 3 units.**

Then diagonal from \((9,12)\) to \((15,18)\)? Check the \(M_5\) block \([15,17]\times[12,14]\): at \(x=15\) we would be at \(y = 18 > 14\) — above it ✓ safe.

Finally from \((15,18)\): move diagonally to \((17,20)\) ✓.

Step 4 — compute the elapsed time.

\[ \text{Job 1 idle} = 3 \ \text{units (the vertical segment)} \]
\[ \boxed{\ \text{Total elapsed} = \text{Job 1 total} + \text{Job 1 idle} = 17 + 3 = \mathbf{20\ \text{hours}}\ } \]

Cross-check with Job 2.

\[ \text{Job 2 idle} = 0 \ \text{(no horizontal segments in our path)} \]
\[ \text{Total elapsed} = \text{Job 2 total} + \text{Job 2 idle} = 20 + 0 = \mathbf{20} \ \checkmark \]

Both formulas agree ✓ — the standard consistency check.

Is 20 optimal? The absolute lower bound is \(\max(17, 20) = 20\), achieved when one job never waits. Our schedule has Job 2 working continuously.

\[ \boxed{\ \textbf{20 hours is OPTIMAL — Job 2 (the longer job) never idles.}\ } \]

Interpretation. The bottleneck is Job 2's total workload of 20 hours. Job 1 (17 hours of work) absorbs all the waiting, idling 3 hours while Job 2 occupies \(M_4\).

Problem 4 — Reading idle times from the graph

For the schedule of Problem 3, compute each machine's idle time and identify the busiest machine.

Solution.

Machine workloads.

Machine Job 1 time Job 2 time Total busy
\(M_1\) 3 4 7
\(M_2\) 4 6 10
\(M_3\) 2 5 7
\(M_4\) 6 3 9
\(M_5\) 2 2 4
Total 37

Idle times (elapsed 20 hours each):

Machine Busy Idle Utilisation
\(M_1\) 7 13 35 %
\(M_2\) 10 10 50 %
\(M_3\) 7 13 35 %
\(M_4\) 9 11 45 %
\(M_5\) 4 16 20 %
\[ \boxed{\ M_2 \textbf{ is the busiest machine at 50 \% utilisation.}\ } \]

Total machine-hours. \(5\times20 = 100\) machine-hours available, 37 used ⟹ overall utilisation 37 %.

Why utilisation is so low. With only 2 jobs and 5 machines, most machines are idle most of the time — this is inherent to a job shop with few jobs, not a scheduling failure.

Management implication. The correct response is not to buy faster machines (they are idle) but to increase throughput — release more jobs into the shop. With 5 jobs instead of 2, utilisation would rise sharply without any capital expenditure.

\[ \boxed{\ \textbf{Low utilisation with few jobs is a demand problem, not a capacity problem.}\ } \]

Problem 5 — A comparative study of the two methods

A workshop must decide between two production configurations. Configuration A processes 5 jobs through 3 machines; Configuration B processes 2 large jobs through 5 machines. Using the results of §2 and Problem 3, compare and advise.

Solution.

Configuration A (5 jobs, 3 machines — §2 results):

Metric Value
Makespan 44 hours
Total work content \(25+15+40 = 80\) machine-hours
Machine-hours available \(3\times44 = 132\)
Overall utilisation \(80/132 = \mathbf{60.6\%}\)
Bottleneck M3 at 90.9 %
Jobs completed 5
Throughput \(5/44 = 0.114\) jobs/hour

Configuration B (2 jobs, 5 machines — Problem 3/4 results):

Metric Value
Makespan 20 hours
Total work content 37 machine-hours
Machine-hours available \(5\times20 = 100\)
Overall utilisation \(37/100 = \mathbf{37.0\%}\)
Bottleneck M2 at 50 %
Jobs completed 2
Throughput \(2/20 = 0.100\) jobs/hour

Comparison.

Criterion Config A Config B Winner
Makespan 44 h 20 h B
Utilisation 60.6 % 37.0 % A
Throughput (jobs/h) 0.114 0.100 A
Bottleneck severity 90.9 % (critical) 50 % (comfortable) B
Flexibility low high B

Advice.

  1. Configuration A gives higher throughput and utilisation, which matters if the shop is capacity constrained and jobs are queueing. Its 60.6 % utilisation versus B's 37 % means less idle capital.

  2. But Configuration A has a critical bottleneck. M3 runs at 90.9 %. Queueing theory (Unit III, L24) shows that waiting time grows as \(\frac{\rho}{1-\rho}\) — at \(\rho = 0.909\) that factor is 10, versus 1 at \(\rho = 0.5\). Configuration A is fragile: any breakdown or overrun on M3 propagates through the whole schedule.

  3. Configuration B is robust but underutilised. No machine exceeds 50 %, so disruptions absorb easily — but 63 % of capacity is idle.

  4. The recommendation.

    \[ \boxed{\ \textbf{Adopt Configuration A, but invest in M3 capacity or add a parallel M3.}\ } \]

    Reducing M3's load would cut the makespan below 44 hours and relieve the bottleneck, capturing A's throughput advantage without its fragility.

  5. Quantifying the M3 investment. M3's total load is 40 hours against a 44-hour makespan. Adding a second M3 unit halves that to 20 hours, and the new binding constraint becomes M1 (25 hours). The makespan would fall to roughly

    \[ \approx \sum A + B_{\text{last}} + C_{\text{last}} = 25 + 5 + 6 = 36\ \text{hours} \]

    — an 18 % reduction, and utilisation of the remaining machines rises correspondingly.

  6. The honest caveat. Both models assume deterministic processing times. Real shops have variability, and at 90.9 % utilisation variability is punishing. Before committing to Configuration A, model the variability — Unit III's queueing theory (L24–L29) is the right tool, and it will typically recommend keeping the bottleneck below about 85 %.

15.6 Practice Problems

  1. Check the 3-machine condition for \(A=(7,9,6)\), \(B=(3,4,2)\), \(C=(8,5,9)\). [Ans: \(\min A = 6 \ge 4\) ✓ valid]
  2. Compute \(G\) and \(H\) for job \((A,B,C) = (5,3,7)\). [Ans: \(G=8\), \(H=10\)]
  3. In the 2-job graphical method, what does a horizontal move represent? [Ans: Job 1 works, Job 2 idles]
  4. Why must the path avoid the shaded rectangles?
  5. Job 1 totals 15 h and idles 4 h. What is the elapsed time? [Ans: 19 h]
  6. State both reducibility conditions and explain what they mean physically.
  7. If both conditions fail, name two valid approaches.

15.7 Summary

  • 3 machines reduce to 2 iff \(\min_i A_i \ge \max_i B_i\) OR \(\min_i C_i \ge \max_i B_i\) — the middle machine must never be the bottleneck. Always check first; otherwise the problem is NP-hard.
  • \(G\)–\(H\) conversion: \(G_i = A_i+B_i\), \(H_i = B_i+C_i\); apply Johnson's rule to \((G_i, H_i)\).
  • The in–out table cascades: each machine's start is \(\max(\text{this job's previous-machine finish},\ \text{previous job's finish on this machine})\).
  • 2 jobs through \(m\) machines is solved graphically: cumulative times on the axes, forbidden rectangles where both jobs need the same machine, and a path from origin to corner maximising 45° diagonal travel (= concurrency).
  • \(\text{Elapsed} = \text{Job 1 total} + \text{Job 1 idle} = \text{Job 2 total} + \text{Job 2 idle}\) — always check both.
  • The lower bound is \(\max(\text{Job 1 total},\ \text{Job 2 total})\), attained when the longer job never waits.
  • Low machine utilisation with few jobs is a demand problem, not a capacity problem; conversely, a bottleneck above ~85 % is fragile once variability is considered (Unit III).

Next lesson: L16 — Integer programming and Gomory's cutting-plane method.

Practise now: unit2-games-networks-lab.html → Sequencing Lab: switch to 3-machine mode (with the condition checked automatically) or 2-job graphical mode with draggable path.