Sign in to watch this lesson
Advanced - Greedy and Scheduling · 4:18
Two-Machine Flow Shop: Johnson's Rule
Every job runs first on machine 1 for a and then on machine 2 for b, and we want machine 2 to finish as early as possible. The makespan is the sum of the b's plus machine 2's idle time, which an adjacent swap analysis turns into Johnson's rule: sort by min(a, b), send jobs with a < b to the front by increasing a and the rest to the back by decreasing b. We also see why the pairwise comparator is unsafe in std::sort and why three machines make the problem NP-hard.
You will learn
- Simulate a two-machine flow shop with two clocks (t1 += a; t2 = max(t2, t1) + b) in 64-bit integers
- Express the makespan as Σb plus machine 2's idle time and use the lower bounds Σa + min b and Σb + min a
- Apply Johnson's rule with the two-list construction (front by increasing a, back by decreasing b)
- Explain why the pairwise comparator min(a_i, b_j) < min(b_i, a_j) is not a strict weak ordering, and why three machines are NP-hard