scheduling to minimize lateness

You have one machine and a list of jobs, each needing some processing time and each carrying a deadline. You run jobs one after another with no gaps. A job that finishes after its deadline is 'late' by the amount it overshoots; the lateness of the whole schedule is the worst single overshoot. The goal is to order the jobs to make that maximum lateness as small as possible.

The greedy rule is delightfully simple and ignores the processing times entirely: sort the jobs by deadline, earliest deadline first, and run them in that order back to back. This is called earliest-deadline-first (EDF). The proof is a textbook exchange argument. Define an inversion as a pair of jobs scheduled out of deadline order — a job with a later deadline running before one with an earlier deadline. Claim: swapping an adjacent inverted pair never increases the maximum lateness. The job moved earlier can only finish sooner (helping it), and the job moved later now finishes when the pair as a whole finished before, but it has the earlier deadline, so its lateness is bounded by what the other job's lateness already was. Repeatedly removing adjacent inversions turns any optimal schedule into the deadline-sorted one without ever increasing lateness, so EDF is optimal. Trace jobs (time, deadline) = (1,2),(2,4),(3,3): by deadline order (1,2),(3,3),(2,4) finish at 1,4,6 with latenesses 0,1,2 — max 2; other orders do no better.

Earliest-deadline-first is a foundational result in scheduling theory and real-time systems. The instructive surprise is that processing times do not enter the sort at all — only deadlines do — which feels wrong until the exchange argument convinces you. Caveat: this exact rule is optimal for minimizing MAXIMUM lateness on a single machine with all jobs available at time zero. Change the objective (say, total tardiness, or number of late jobs) or allow release times, and a different rule, or even dynamic programming, may be required.