One machine, a set of jobs all available at time 0, no preemption once a job
starts. Each job i has a processing time pi and a deadline
di. Run the jobs one at a time, back to back, in any order — every job
finishes at some completion time Ci, and its lateness is
Li = Ci - di (negative if it finishes early, zero if it
lands exactly on the deadline, positive if it's late). The question: which order minimizes the
worst lateness across all jobs, max Li?
The greedy rule: sort by deadline, earliest first, and run them in that order — no lookahead, one pass, done. This is the site's eleventh entry filed under Greedy, and its own proof of correctness is a genuinely different shape from every one of the site's other ten: Huffman Coding, Activity Selection, Interval Point Cover, Fractional Knapsack, and Job Sequencing all swap in a single best-looking item and argue the rest of the schedule tolerates it; Interval Partitioning matches a lower bound to an upper bound; Stable Matching shows no proposal is ever wasted. This entry's proof instead looks at any two jobs scheduled back to back out of deadline order and shows swapping just that adjacent pair can only help — an inversion-removal argument, the same shape a bubble sort's correctness proof uses, applied here to a scheduling order instead of a numeric array.
Type a list of processing/deadline pairs (comma-separated), pick an ordering rule,
and press Load, then Step or Run. Each row is one
job on the shared machine's timeline — a green bar means it finished at or before its own deadline
tick, a red dashed bar means it finished late. The demo also brute-forces the true optimal max
lateness for comparison (capped at 8 jobs so that stays instant), so a rule that falls short is
visible immediately, not just claimed.
timeline
The proof is an adjacent-exchange argument, not a single-item substitution. Take any schedule
that contains an inversion: two jobs i and j scheduled
back to back with j running immediately before i, even though
i's deadline is earlier (di < dj). Let
t be the time the earlier of the two starts. Before the swap, j finishes
at t + pj and i finishes at t + pj +
pi, so Li = t + pj + pi - di.
Swap them: i now finishes at t + pi and j finishes
at t + pi + pj, the identical total span, just reordered. The new
lateness of j is t + pi + pj - dj — and
because dj > di, that's strictly less than
t + pi + pj - di, which is exactly the pre-swap
Li. The new lateness of i is t + pi -
di, which is no more than the pre-swap Li either (dropping
pj ≥ 0 from the sum can't increase it). Every other job's completion time
is untouched by a swap of two adjacent jobs. So both new lateness values are bounded above by the
single pre-swap value Li — the swap never increases the schedule's overall
max lateness, and can only decrease it. Any schedule with an inversion can therefore be improved (or
matched) by removing that inversion, one adjacent swap at a time, exactly like sorting by repeated
adjacent transpositions — and a schedule with zero inversions is, by definition, sorted by deadline.
Earliest-deadline-first is what's left once every possible improvement has been taken.
On the default 5-job set, earliest-deadline-first schedules job 1 (p=6,d=7), then 4
(p=9,d=9), then 5 (p=2,d=22), then 3 (p=9,d=25), then 2
(p=9,d=29) — finishing at times 6, 15, 17, 26, 35, for latenesses -1, 6, -5, 1, 6. The
worst is 6, tied between jobs 4 and 2, confirmed by brute force to be the true optimum:
of all 120 orderings of these 5 jobs, only 2 reach max lateness 6, and none reach lower. The other
two rules offered in the demo above don't reach it — see Pitfalls.
function minimizeMaxLateness(jobs) {
// jobs: [{ p, d }] — processing time, deadline; all released at time 0
const sorted = [...jobs].sort((a, b) => a.d - b.d);
let t = 0;
let maxLateness = -Infinity;
const schedule = [];
for (const job of sorted) {
t += job.p;
const lateness = t - job.d;
maxLateness = Math.max(maxLateness, lateness);
schedule.push({ ...job, completion: t, lateness });
}
return { schedule, maxLateness };
}Ignoring deadlines entirely fails badly. Switch the demo's rule to
shortest processing time first on the unchanged default data: job 5 (only 2 units of work)
runs first since nothing about that rule ever looks at a deadline, which pushes job 4
(p=9, d=9) — the job with by far the tightest deadline on the list — all the way to the
end, finishing at time 35 against a deadline of 9, a lateness of 26, more than four
times the optimal 6. Checked beyond this one example: across 20,000 random trials (4-6 jobs each),
shortest-processing-time-first misses the true optimum 84.6% of the time. This rule
is exactly correct for a different objective — minimizing total completion time across all
jobs, with no deadlines involved at all — but that's a different question with a different proof,
and being right for that one buys nothing here.
Least slack first looks more informed and still fails. Slack —
di - pi, deadline minus processing time — at least accounts for
both numbers the correct rule needs, which makes it a much more tempting near-miss than ignoring
deadlines outright. It's still wrong: on the same default data, job 4 has the least slack
(9 - 9 = 0) and runs first, then job 1 (7 - 6 = 1) — but running job 4
first pushes job 1's own tight deadline of 7 to a completion time of 15, a lateness of 8 already
worse than the optimal schedule's worst case, and the schedule goes on to finish job 5 last at a
lateness of 13, more than double the optimal 6. Slack conflates two different jobs'
situations that a single subtraction can't tell apart: a job with a loose deadline but long
processing time can have the same slack as a job with a tight deadline and short processing time,
yet only one of those two is actually urgent to schedule first. Checked across the same 20,000
trials: least-slack-first misses the true optimum 41.2% of the time — better than
ignoring deadlines outright, but the adjacent-swap proof above backs only one specific rule, and
slack isn't it.
Time: O(n log n), entirely the cost of sorting by deadline — the
single pass that follows is O(n), one addition and one comparison per job.
Space: O(n) for the sorted copy and the returned schedule, or
O(1) extra if only the max lateness value is needed, not the full reconstruction. This
demo's brute-force optimal check, shown purely for comparison, is O(n!) and capped at 8
jobs for exactly that reason — nothing about the greedy algorithm itself needs it.
See Choosing a Greedy Strategy for how this entry's adjacent-swap proof compares against the site's other ten Greedy entries — short version: this is Tier 1, exact on every input, but the only entry whose safety argument works on a pair of adjacent items instead of a single substituted one.