Minimising Maximum Lateness

$n$ jobs on one machine; job $j$ takes $p_j$ time and is due at $d_j$. If it completes at $C_j$, its lateness is $L_j=C_j-d_j$ (possibly negative). Minimise ${\max }_j{L}_j$.

Earliest Due Date (EDD)

Sort by deadline ascending and run the jobs in that order.

sort(jobs.begin(), jobs.end(), [](auto& a, auto& b){ return a.deadline < b.deadline; });
long long t = 0, maxLate = LLONG_MIN;
for (auto& j : jobs) { t += j.p; maxLate = max(maxLate, t - j.deadline); }

$O(n\log n)$, and processing times are irrelevant to the ordering — only deadlines matter.

The exchange argument

Take an optimal schedule with an inversion: adjacent jobs $i$ then $j$ with $d_i>d_j$. Swap them.

• $j$ now finishes earlier, so $L_j$ decreases.
• $i$ now finishes at the time $j$ previously finished, so its new lateness is $t-d_i<t-d_j$ = $j$‘s old lateness.
• Every other job is unaffected (the pair occupies the same total time).

So the maximum lateness does not increase. Repeatedly removing inversions transforms any optimal schedule into EDD order without ever getting worse. ∎

This is the textbook example of an adjacent-swap exchange argument — worth knowing as a template.

The single-machine landscape

Using the standard $\alpha \mid \beta \mid \gamma$ notation:

Problem	Objective	Rule	Cost
$1\mid \mid L_{\max }$	max lateness	EDD	$O(n\log n)$
$1\mid \mid \sum C_j$	total completion time	SPT (shortest first)	$O(n\log n)$
$1\mid \mid \sum w_j{C}_j$	weighted completion	Smith’s rule ($p_j/w_j$)	$O(n\log n)$
$1\mid \mid \sum U_j$	number of late jobs	Moore-Hodgson	$O(n\log n)$
$1\mid prec\mid f_{\max }$	max penalty, precedence	Lawler	$O(n^2)$
$1\mid r_j\mid L_{\max }$	with release times	NP-hard
$1\mid \mid \sum T_j$	total tardiness	NP-hard (pseudo-poly DP exists)
$1\mid \mid \sum w_j{U}_j$	weighted late jobs	NP-hard (knapsack)
$P2\mid \mid C_{\max }$	2 machines, makespan	NP-hard (partition)
$F2\mid \mid C_{\max }$	2-machine flow shop	Johnson’s rule	$O(n\log n)$

The pattern is worth internalising: max-type objectives on one machine are usually easy; sum-type objectives with weights, or anything with release times or multiple machines, are usually NP-hard.

Johnson’s rule (two-machine flow shop)

Every job passes through machine A then machine B, taking $a_j$ and $b_j$.

Schedule jobs with $a_j<b_j$ first, in increasing $a_j$; then the rest in decreasing $b_j$.

Minimises the makespan, provably, by an exchange argument. A rare case where a two-machine problem is polynomial.

Preemption

Allowing jobs to be interrupted often makes hard problems easy:

Problem	Non-preemptive	Preemptive
$1\mid r_j\mid L_{\max }$	NP-hard	EDD with preemption, $O(n\log n)$
$P\mid \mid C_{\max }$	NP-hard	$O(n)$ (McNaughton’s rule)
$1\mid r_j\mid \sum C_j$	NP-hard	SRPT (shortest remaining time), $O(n\log n)$

Preemptive EDD with release times: at every moment run the available job with the earliest deadline, preempting when a more urgent one arrives. A priority queue keyed by deadline, processed in event order.

If a problem allows preemption, check for these — they are usually the intended solution.

Related objectives

$T_j=\max (0,L_j)\text{(tardiness)},U_j=[L_j>0]\text{(late indicator)},E_j=\max (0,-L_j)\text{(earliness)}.$

Minimising $\max L_j$ (EDD) and $\max T_j$ are the same problem. Minimising $\sum T_j$ or $\sum w_j{U}_j$ is NP-hard — a good illustration that swapping “max” for “sum” changes everything.

See also: Lawler’s Algorithm · Exchange Arguments · Job Sequencing with Deadlines