Lawler's Algorithm

Purpose: Minimise the maximum penalty ${\max }_j{f}_j(C_j)$ on a single machine subject to precedence constraints, in $O(n^2)$. Eugene Lawler, 1973.

The Problem

$n$ jobs, job $j$ has processing time $p_j$ and a non-decreasing cost function $f_j$ of its completion time $C_j$. Precedence constraints form a DAG: job $i$ must finish before job $j$ starts. Minimise ${\max }_j{f}_j(C_j)$.

Common special case: $f_j(t)=t-d_j$, giving minimum maximum lateness $L_{\max }$.

Algorithm — schedule backwards

The whole schedule occupies $[0,P]$ where $P=\sum p_j$. Build it from the end:

1. Let $S$ = the set of unscheduled jobs, $t=P$.
2. Among jobs in $S$ with no unscheduled successors (they can legally go last), pick the one minimising $f_j(t)$.
3. Place it in the last remaining slot, ending at time $t$. Set $t-=p_j$, remove $j$ from $S$.
4. Repeat.

// jobs 0..n-1, succ[j] = successors; f[j](t) = penalty
vector<int> lawler(int n, vector<long long> p, vector<vector<int>> succ,
                   function<long long(int,long long)> f) {
    vector<int> outdeg(n, 0);
    for (int j = 0; j < n; j++) for (int k : succ[j]) outdeg[j]++;
    long long t = accumulate(p.begin(), p.end(), 0LL);
    vector<bool> done(n, false);
    vector<int> order;
    vector<vector<int>> pred(n);
    for (int j = 0; j < n; j++) for (int k : succ[j]) pred[k].push_back(j);
 
    for (int step = 0; step < n; step++) {
        int best = -1;
        for (int j = 0; j < n; j++)
            if (!done[j] && outdeg[j] == 0)
                if (best < 0 || f(j, t) < f(best, t)) best = j;
        done[best] = true; order.push_back(best);
        t -= p[best];
        for (int i : pred[best]) outdeg[i]--;
    }
    reverse(order.begin(), order.end());
    return order;
}

Complexity

• Time: $O(n^2)$ — $n$ rounds, each scanning $n$ jobs. $O(n\log n)$ with a heap when $f_j$ has enough structure.
• Space: $O(n+|E|)$

Proof (exchange argument)

Claim: there is an optimal schedule in which the job chosen in step 2 is last.

Let $j^{\ast }$ be the algorithm’s choice and let $k$ be last in some optimal schedule. Both are eligible to be last (no unscheduled successors), and $f_{j^{\ast }}(P)\le f_k(P)$ by the choice rule. Move $j^{\ast }$ to the end and shift everything between forward. Then:

• $j^{\ast }$‘s new cost is $f_{j^{\ast }}(P)\le f_k(P)\le \mathrm{OPT}$;
• every other job finishes no later than before, and each $f$ is non-decreasing, so no other cost increases;
• precedence is preserved, because $j^{\ast }$ had no unscheduled successors.

So the modified schedule is still optimal. Induct on the remaining prefix. ∎

Where it sits among scheduling results

Problem	Notation	Result
Min max lateness, no precedence	$1\Vert \Vert L_{\max }$	EDD — sort by due date, $O(n\log n)$
Min max penalty, precedence	$1\Vert prec\Vert f_{\max }$	Lawler, $O(n^2)$
Min sum of completion times	$1\Vert \Vert \sum C_j$	SPT — sort by processing time
Min weighted sum	$1\Vert \Vert \sum w_j{C}_j$	Smith’s rule — sort by $p_j/w_j$
Min number of late jobs	$1\Vert \Vert \sum U_j$	Moore-Hodgson, $O(n\log n)$
Min max lateness with release times	$1\Vert r_j\Vert L_{\max }$	NP-hard
Two machines, min makespan	$P2\Vert \Vert C_{\max }$	NP-hard (partition)

The pattern

Almost every polynomially solvable single-machine scheduling problem is solved by “sort by the right key” plus an exchange argument. When you meet a scheduling problem, the first move is to guess the sort key and try to prove the adjacent swap never hurts. See Exchange Arguments.

Variants / Use Cases

• Minimising Maximum Lateness — the special case
• Job Sequencing with Deadlines — the profit-maximising cousin, solved with DSU or a heap
• Exchange Arguments — the proof technique
• Scheduling — the branch overview