⚙ Controls
1 Hit Johnson's Rule to see the optimal order
2 Note the Makespan & M2 Idle time
3 Switch to Manual and try to beat it!
📋 Jobs
| Job | M1 | M2 |
|---|
💼 Interview Tip
Johnson's Rule gives the provably optimal sequence for a 2-machine flow shop. The algorithm: find the shortest time among all jobs & machines. If it's on M1, schedule that job as early as possible; if on M2, as late as possible. Repeat. Be ready to walk through the steps — it's a common OSCM interview question.
Instructor Notes
- Have students apply Johnson's Rule first, then try to beat it manually — they can't, which proves optimality.
- Debrief: Why does M2 idle? Because M2 must wait for M1 to finish. Johnson's Rule minimizes this idle gap.
- Challenge: give teams random data and 2 minutes to find the optimal order without the button.
📊 Gantt Chart
Machine 1
Machine 2
Idle
M1
M2
Makespan
–
M2 Idle
–
M1 Util
–
M2 Util
–
💡 How Johnson's Rule Works
Among all remaining jobs, find the shortest processing time. If that time is on Machine 1, schedule the job as early as possible. If it's on Machine 2, schedule it as late as possible. Remove the job and repeat until all jobs are placed. Ties may be broken arbitrarily.