Scheduling to Minimize Lateness Section 4 2 The Problem p Minimizing lateness n Set of jobs 1 2 n all of them must be scheduled on a single resource room processor n All jobs arrive at time s n Each job i has its own deadline di and length ti n We choose the start time si for each job i n Jobs are allowed to be late p n job i finishes at time fi si ti which could be di If job i is late its lateness li fi di if not late li 0 Goal Minimize the maximum lateness minimize L maxi li 1 PDF created with pdfFactory trial version www pdffactory com Minimizing lateness Greedy approaches Shortest jobs first p Earliest deadline first p Slack time for job i di ti p n Smallest slack time first 2 PDF created with pdfFactory trial version www pdffactory com Greedy approaches p Shortest jobs first n Two jobs 1 and 2 p p p t1 1 d1 100 t2 10 d2 10 Smallest slack time first n Two jobs 1 and 2 p p t1 1 d1 2 t2 10 d2 10 Earliest deadline first 3 PDF created with pdfFactory trial version www pdffactory com Exchange Argument We will transform the optimal solution step by step into our solution p At each step we will show that the maximum lateness does not increase p Hence our solution is optimal p Idle time p Idle time n Time when the machine is not working even though there are jobs left to be done 4 7 There is an optimal solution with no idle times p Observation Our solution has no idle times p 4 PDF created with pdfFactory trial version www pdffactory com Inversion p Inversion n n Jobs i and j with deadlines dj di If j is scheduled after i then there is an inversion Inversion 5 PDF created with pdfFactory trial version www pdffactory com No Inversion No Inversion p Observation 1 Our solution has no inversions or idle times 6 PDF created with pdfFactory trial version www pdffactory com Schedules with no inversions p No two jobs with identical deadline n p unique schedule with no inversions no idle times Multiple jobs with identical deadlines n Many schedules with no inversions no idle times Schedules with no inversions p 4 8 All schedules with no inversions and no idle times have the same maximum lateness 7 PDF created with pdfFactory trial version www pdffactory com Optimal schedule p 4 9 There is an optimal schedule that has no inversions and no idle times n n n n Let OPT be an optimal schedule a If OPT has an inversion then there is a pair i and j such that j is scheduled immediately after i and has dj di b After swapping i and j we get a schedule with on less inversion c The new swapped schedule has a maximum lateness no larger than that of OPT Optimality p 4 10 The greedy solution produced by earliest deadline first is optimal n Observation 1 4 8 and 4 9 together yield this immediately 8 PDF created with pdfFactory trial version www pdffactory com