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:
- State the condition under which a 3-machine problem reduces to 2 machines.
- Perform the \(G\)–\(H\) conversion and apply Johnson's rule.
- Construct the 3-machine in–out table.
- Solve 2 jobs through \(m\) machines by the graphical (45°) method.
- 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¶
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:
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:
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.
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] |
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.
Step 5 — idle times.
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¶
The problem is therefore: find the path from origin to corner that maximises diagonal travel while avoiding the shaded (conflict) rectangles.
Elapsed time formula.
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\).
(Condition 2 also fails to be needed: \(4 \ge 3\) ✓ — both hold, doubly safe.)
(b) \(\min A = 3\), \(\max B = 7\), \(\min C = 2\).
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\).
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 |
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] |
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.
Step 5 — idle times.
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.
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.
Cross-check with Job 2.
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.
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 % |
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.
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.
-
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.
-
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.
-
Configuration B is robust but underutilised. No machine exceeds 50 %, so disruptions absorb easily — but 63 % of capacity is idle.
-
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.
-
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.
-
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¶
- 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]
- Compute \(G\) and \(H\) for job \((A,B,C) = (5,3,7)\). [Ans: \(G=8\), \(H=10\)]
- In the 2-job graphical method, what does a horizontal move represent? [Ans: Job 1 works, Job 2 idles]
- Why must the path avoid the shaded rectangles?
- Job 1 totals 15 h and idles 4 h. What is the elapsed time? [Ans: 19 h]
- State both reducibility conditions and explain what they mean physically.
- 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.