CSCC73H3 Lecture Notes - The Algorithm, Joule, Society Of Jesus
19 Oct 2011
School
Department
Course
Professor
Document Summary
The greedy algorithm that minimises the maximum lateness does not also minimise the sum of latenesses. The greedy algorithm that minimises maximum lateness orders the jobs in increasing deadline. In this example, the algorithm orders a before b, resulting in lateness of 2 for job a and 2 for job b, so the sum of latenesses for the two jobs is 4. In the schedule where b is before a, however, job b has lateness 0 and job a has lateness 3, so the sum of latenesses of the two jobs is 3. A clue that the algorithm that minimises maximum lateness does not also minimise the sum of lateness is provided by the proof of optimality for the former. A crucial step in that proof, where we showed that. Xing an inversion does not increase the maximum lateness, does not apply to the sum of the latenesses.
