Minimizing Lateness

Greedy Algorithm to minimize lateness when scheduling jobs on a processor

Problem Statement

• Processor can process 1 job at a time
• Job j requires t_j units of processing time and is due at time d_j
• j starts at time s(j), it finishes at time f(j) = s(j) + t_j
• Lateness = max {0, f(j) – d_j}
• Goal: schedule all jobs to minimize the maximum lateness

Input Jobs

Algorithm

Consider jobs with Earlieast Deadline first

Runtime

Sorting O(n log(n)) + for-loop Θ(n)
O(n log(n))

Optimal Job Ordering

Max Lateness = 1

References

• Tudelft slides
• Kevin Wayne slides
• Srinivasan Parthasarathy slides
• Carl Kingsford slides
• Chandra Chekuri slides