Back to all solvers
Job Sequencing (Johnson's Rule)
Sequence jobs on a two-machine flow shop to minimize makespan using Johnson's rule.
Jobs
CSV: name,timeMachine1,timeMachine2. After Solve, also Export results CSV.
Johnson’s rule
For a two-machine flow shop (every job visits M1 then M2), Johnson’s rule minimizes makespan: jobs with smaller M1 time go early; jobs with smaller M2 time go late.
Procedure
1) List all jobs with times (aᵢ, bᵢ). 2) Find the job with the smallest remaining time on either machine. 3) If that time is on M1, schedule early; if on M2, schedule late. 4) Remove and repeat.
Makespan
Simulate the sequence: M1 processes continuously; M2 starts a job only when both M1 finished it and M2 is free. Makespan = finish time of the last job on M2.
Classic 5-job example. Optimal sequence J2 → J4 → J3 → J5 → J1 with makespan 30.
Frequently Asked Questions
Not in general. Three-machine flow shops are NP-hard; heuristics or branch-and-bound are used.