Minimizing Maximum Lateness
Motivation
A single processor must run \(n\) jobs back-to-back, each with a duration \(t_i\) and a deadline \(d_i\). Once a job starts it runs to completion (no preemption). The processor finishes job \(i\) at some time \(f_i\); the job’s lateness is \(\ell_i = \max(0, f_i - d_i)\). The goal is to schedule the jobs so that the maximum lateness is as small as possible (Kleinberg and Tardos 2005).
This is the canonical worst-case-deadline variant of single-machine scheduling and a textbook illustration that the order of greedy choices matters as much as the choice itself. The right ordering is earliest deadline first, and the proof is the canonical exchange argument on inversions.
Problem
- \(n\) jobs, where job \(i\) has processing time \(t_i \ge 0\) and deadline \(d_i\).
- A schedule assigns each job a contiguous time interval \([s_i, f_i)\) with \(f_i = s_i + t_i\), and the intervals are pairwise disjoint.
- Lateness of \(i\): \(\ell_i = \max(0, f_i - d_i)\).
- Maximum lateness: \(L = \max_i \ell_i\).
- Goal: choose a schedule that minimizes \(L\).
Key Ideas
A few natural orderings suggest themselves.
- Shortest job first ignores deadlines: a short job with a far deadline can be processed before a long job with a tight deadline, making the long job late.
- Smallest slack first (\(d_i - t_i\)) also fails on simple two-job examples.
- Earliest deadline first — run the job with the most urgent deadline next — turns out to be optimal.
Two observations make earliest-deadline-first work.
- Idle time never helps. 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 permutations of the jobs.
- Inversions can always be fixed cheaply. An inversion is a pair of jobs \((i, j)\) where \(i\) runs before \(j\) but \(d_i > d_j\) (a later-deadline job runs first). Earliest-deadline-first has no inversions, and any adjacent inversion can be swapped without increasing the maximum lateness — so any schedule can be converted to earliest-deadline-first one swap at a time without making \(L\) worse (proof).
Algorithm
Sort jobs by deadline \(d_1 \le d_2 \le \dots \le d_n\) and run them in this order with no idle time: \[ s_1 = 0, \quad f_i = s_i + t_i, \quad s_{i+1} = f_i. \]
sort jobs so that d_1 <= d_2 <= ... <= d_n
s = 0
for i = 1 to n:
s_i = s
f_i = s + t_i
s = f_i
return schedule (s_i, f_i)Walkthrough
Four jobs with \((t_i, d_i)\) values \((2, 4), (3, 5), (2, 8), (4, 10)\). The deadlines are already in increasing order, so earliest-deadline-first runs them as numbered. Deadlines are marked as triangles above the time axis; the only late job is \(4\), with \(\ell_4 = 1\).
Each job finishes at a time stamped on its right edge: \(f_1 = 2, f_2 = 5, f_3 = 7, f_4 = 11\). Comparing to deadlines: \(J_1\) finishes \(2\) early, \(J_2\) on time, \(J_3\) one early, \(J_4\) one late. The maximum lateness is \(\ell_4 = 1\). No reordering can do better — the total processing time \(11\) already exceeds the tightest deadline \(d_2 = 5\) for at least one job in any schedule, and earliest-deadline-first arranges the slack so that all of it lands on the job with the latest deadline.
Complexity and Tradeoffs
Sorting by deadline: \(O(n \log n)\). Sequential scheduling: \(O(n)\). Total: \(\Theta(n \log n)\), with \(\Theta(n)\) extra memory for the sorted permutation.
The problem changes character along several dimensions:
- Preemption. Earliest-deadline-first is also optimal in the preemptive single-machine version.
- Multiple machines. NP-hard in general; approximation algorithms exist.
- Different objectives. Sum of latenesses or weighted lateness can be NP-hard even on a single machine; earliest-deadline-first is specific to the min-max objective. See single-machine scheduling for the variant landscape.
- Release times. If each job has a release time \(r_i\) before which it cannot start, the problem becomes NP-hard and earliest-deadline-first must be modified — the preemptive variant remains tractable.
- Tie-breaking. Jobs with equal deadlines may be ordered arbitrarily without changing \(L\) — useful slack when integrating into a larger system.
When to Use It
Earliest-deadline-first is the right choice whenever a single resource must process jobs with deadlines and the objective is to minimize the worst lateness.
- Worst-case deadline performance on a single machine: optimal whether or not preemption is allowed.
- Real-time scheduling with dynamic priorities: the canonical deadline-driven scheduler.
- Jobs with precedence constraints: run topological sort first to get a valid order, then apply earliest-deadline-first within each chain of independent jobs.
- Different objectives. For average completion time, weighted completion, or counting late jobs, see the table in single-machine scheduling. For selecting a maximum number of compatible jobs without deadlines, use interval scheduling; for weighted selection, use weighted interval scheduling.