Operations & Analytics
Johnson’s Rule Two-Machine Flow-Shop Makespan (Cmax) & Utilization
Classify jobs into Johnson’s Rule Group 1 (M1 <= M2, sort ascending M1) vs. Group 2 (M1 > M2, sort descending M2) and compute exact 4-job flow-shop makespan Cmax and Machine 2 utilization.
Minimize two-stage shop-floor makespan without idle bottlenecks!
Every job in a two-stage fabrication shop must pass through Machine 1 (Laser Cutting) before Machine 2 (Robotic Welding). Selmer Johnson’s classic 1954 scheduling theorem guarantees the minimum possible total completion time (Makespan C_max) in two steps: (1) assign jobs with M1 <= M2 to Group 1 (scheduled earliest, sorted by ascending M1) so Machine 2 starts working as quickly as possible, and assign jobs with M1 > M2 to Group 2 (scheduled latest, sorted by descending M2) so Machine 1 finishes while Machine 2 clears its tail!
Even better, for any 4-job sequence in B2:C5, exact two-machine permutation makespan equals the longest critical path across the handover job k = 1..4: C_max = MAX(M1_1 + SUM(M2_1..4), SUM(M1_1..2) + SUM(M2_2..4), SUM(M1_1..3) + SUM(M2_3..4), SUM(M1_1..4) + M2_4)! For our Johnson-ordered shop schedule [(3,8), (5,9), (7,6), (6,4)], C_max = 30 min with 90.00% Machine 2 utilization (only 3 min startup idle while Job 1 cuts!); if Job 3’s cutting time spikes from 7 min to 18 min, C_max shifts to critical path k = 3 at 36 min and utilization drops to 75.00%!
| Sequenced Job | Machine 1 Cut (min) | Machine 2 Weld (min) | Johnson Partition Rule |
|---|---|---|---|
| J-Alpha (Pos 1) | 3 min | 8 min | Group 1: M1 <= M2 (Early, Asc M1) |
| J-Beta (Pos 2) | 5 min | 9 min | Group 1: M1 <= M2 (Early, Asc M1) |
| J-Gamma (Pos 3) | 7 min | 6 min | Group 2: M1 > M2 (Late, Desc M2) |
| J-Delta (Pos 4) | 6 min | 4 min | Group 2: M1 > M2 (Late, Desc M2) -> Cmax = 30 min |
Exact 4-Job Two-Machine Flow-Shop Critical-Path Makespan Cmax (min)
Evaluates MAX_{k=1..4}(SUM(M1_1..k) + SUM(M2_k..4)) across all four possible Machine 1 -> Machine 2 handover points.
=MAX(B2 + SUM(C2:C5), SUM(B2:B3) + SUM(C3:C5), SUM(B2:B4) + SUM(C4:C5), SUM(B2:B5) + C5)Downstream Machine 2 Utilization (%) & Johnson Group Classification
Divides total Machine 2 processing time SUM(C2:C5) by C_max, or classifies any job row into Group 1 vs. Group 2.
=ROUND(100 * SUM(C2:C5) / MAX(B2 + SUM(C2:C5), SUM(B2:B3) + SUM(C3:C5), SUM(B2:B4) + SUM(C4:C5), SUM(B2:B5) + C5), 2)Try the example
Use the original values or change them to test your understanding.