CMSC 451 Minimizing Lateness Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Section 4 3 of Algorithm Design by Kleinberg Tardos Minimizing Lateness A new kind of scheduling problem Not given intervals with start and end times Instead requests are of the form ti di where ti is the job length and di is the job deadline We want to schedule these jobs on a single processor Definition The lateness Li of job i is max 0 fi di i e the length of time past its deadline that it finishes Our goal minimize the maximum lateness Example t1 1 t2 2 t3 3 t4 4 t1 t3 t2 t4 L2 L4 Possible Greedy Rules Short jobs first Possible Greedy Rules Short jobs first t1 10 t2 100 d2 100 d1 110 Possible Greedy Rules Short jobs first t1 10 t2 100 d2 100 Smallest slack time di ti d1 110 Possible Greedy Rules Short jobs first t1 10 t2 100 d2 100 d1 110 Smallest slack time di ti t1 10 t2 100 d1 20 d2 100 The Right Greedy Rule Earliest deadline first get the job with the most pressing deadline done first Surprisingly don t need to consider the length of the job The algorithm Let d 1 d n be the jobs sorted by increasing deadline Let f s For i 1 n Schedule job i starting from time f to f t i Let f f t i Proving Correctness Idle time gaps in the schedule Lemma There is an optimal schedule with no idle time Note some optimal solutions may have idle time Given an OPT schedule with gaps closing the gaps can only decrease the maximum lateness The Exchange Argument There may be lots of optimal schedules A Let A be the schedule produced by our algorithm We ll start with some optimal solution OPT We make local changes to OPT trying to transform it into A Each local change will preserve optimality OPT Inversions Definition An inversion is a pair of jobs i j such that i is scheduled before j but dj di i j inversion i j dj di Inversions in Schedules Lemma All schedules with no inversions and no idle time have the same maximum lateness If there are no inversions this means the jobs are sorted by increasing deadlines Let S1 and S2 be two such schedules The only way these could differ is when several jobs i1 ik have the same deadline which must be adjacent in the schedule The last of these jobs is the only one that matters for maximum lateness And it doesn t matter what the order of these jobs are Proof Outline Property P A schedule has Property P if it has no idle time no inversions 1 Our solution has property P 2 All solutions with property P have the same lateness 3 An optimal solution has property P Proof Outline Property P A schedule has Property P if it has no idle time no inversions 1 Our solution has property P True by construction 2 All solutions with property P have the same lateness True by last lemma 3 An optimal solution has property P Proof of 3 outline Theorem There is an optimal solution with no idle time no inversions Idea Start with any optimal solution OPT0 A Flip two adjacent jobs that are an inversion This will reduce the number of inversions without increasing the maximum lateness Repeat until we have no inversions OPT Proof of 3 deadline a If OPT0 has an inversion it must have an inversion i j where i and j are adjacent da db a c2 c1 c3 b Time If a b is an inversion then da db so there must be some step down b If we swap i and j we reduce the number of inversions by 1 Proof of 3 cont c Let OPT1 be the schedule with i and j swapped OPT1 has maximum lateness OPT0 Old max Li Lj OPT0 i j j OPT1 dj di New max Li Lj i Summary for Minimizing Maximum Lateness So If we keep swapping adjacent inversions in an optimum solution we will eventually arrive a solution with no inversions without changing the maximum lateness Our greedy algorithm produced a solution without inversions Since all solutions without inversions have the same maximum lateness our greedy algorithm sort by deadline must have the same maximum lateness as the optimum