Earliest Deadline First Minimizes Maximum Lateness
Claim
For minimizing maximum lateness on a single machine, running jobs in earliest-deadline-first order with no idle time minimizes the maximum lateness \(L = \max_i \max(0, f_i - d_i)\) (Kleinberg and Tardos 2005).
Setup
A schedule assigns each of \(n\) jobs (with processing times \(t_i \ge 0\) and deadlines \(d_i\)) to a contiguous time interval \([s_i, f_i)\) with \(f_i = s_i + t_i\), and intervals are pairwise disjoint. Earliest-deadline-first orders jobs by \(d_1 \le d_2 \le \dots \le d_n\) and runs them back-to-back from time \(0\).
An inversion in a schedule is a pair \((i, j)\) such that \(i\) runs before \(j\) but \(d_i > d_j\).
Proof
The argument has three steps: (1) restrict to schedules with no idle time, (2) show that any inversion can be undone by an adjacent swap that doesn’t increase \(L\), (3) conclude that earliest-deadline-first is optimal.
Step 1 — no idle time. Compressing any idle gap moves later jobs earlier, which can only reduce each finish time and thus each lateness. So some optimal schedule has no idle time, and we may restrict attention to schedules parameterized by a permutation of the jobs.
Lemma 1 (adjacent inversion exists). If a no-idle-time schedule has any inversion, it has an inversion between adjacent jobs.
Proof. Take any inverted pair \((i, j)\) with \(i\) scheduled before \(j\). Walk forward from \(i\). If the job immediately after \(i\) has deadline \(\ge d_i\), then together with \(j\) it forms an inversion closer to \(j\). Otherwise the immediately-after job has deadline \(< d_i\), an inversion adjacent to \(i\). Iterating shrinks the gap until an adjacent inversion is found. \(\square\)
Lemma 2 (adjacent swap does not increase \(L\)). Swapping two adjacent inverted jobs does not increase the maximum lateness.
Proof. Let \(i, j\) be adjacent in the schedule with \(i\) first and \(d_i > d_j\). After the swap, \(j\) runs before \(i\). Only \(i\)’s and \(j\)’s finish times change. Let the start time of the pair be \(s\).
Before swap: \(f_i = s + t_i\), \(f_j = s + t_i + t_j\), with lateness contributions \(\max(0, s + t_i - d_i)\) and \(\max(0, s + t_i + t_j - d_j)\).
After swap: \(f'_j = s + t_j\), \(f'_i = s + t_i + t_j\), with lateness contributions \(\max(0, s + t_j - d_j)\) and \(\max(0, s + t_i + t_j - d_i)\).
The maximum after the swap is \(\max(0, s + t_i + t_j - d_i)\), since \(d_i > d_j\) and \(t_j \ge 0\) give \(s + t_i + t_j - d_i < s + t_i + t_j - d_j\). The maximum before the swap was \(\ge \max(0, s + t_i + t_j - d_j) \ge \max(0, s + t_i + t_j - d_i)\). So the swap does not increase the maximum. \(\square\)
Step 3 — earliest-deadline-first is optimal. Start with any optimal schedule. By Step 1, it can be assumed to have no idle time. By Lemmas 1 and 2, repeatedly swap adjacent inverted pairs without increasing \(L\). Each swap strictly decreases the inversion count, so the process terminates at an inversion-free schedule. Any two no-idle-time schedules with no inversions agree on the order of jobs with distinct deadlines (ties may differ but yield the same \(L\)), so the resulting schedule is identical to earliest-deadline-first. Therefore \(L_{\text{EDF}} \le L_{\text{OPT}}\), and earliest-deadline-first is optimal. \(\square\)