Sign in to watch this lesson
Advanced - Greedy and Scheduling · 4:18
One-Machine Scheduling: the Permutation Method
One machine, a queue of jobs, and a penalty for every moment a job waits. An adjacent swap changes the total by c_i·t_j − c_j·t_i, so the optimal order sorts by c/t (Smith's ratio rule), compared exactly as integer products. The same argument covers exponential and identical penalties, and a theorem of Livshits and Kladov says those three families are the only ones a sort can solve.
You will learn
- Derive the change in total weighted waiting cost when two adjacent jobs are swapped, c_i·t_j − c_j·t_i, and use it to prove the c/t ordering optimal
- Implement Smith's ratio rule with a strict cross-multiplied comparator in 64-bit integers and a 128-bit total
- Apply the exponential key (1 − e^{αt})/c and the shortest-first rule for identical penalties
- Explain why a quadratic penalty admits no sorting key, so other techniques (DP, search) are needed