Lawler's algorithm

Lawler’s algorithm is a powerful technique for solving a variety of constrained scheduling problems. The algorithm handles any precedence constraints. It schedules a set of simultaneously arriving tasks on one processor with precedence constraints to minimize maximum tardiness or lateness. Precedence constraints occur when certain jobs must be completed before other jobs can be started.

Objective Functions

The objective function is assumed to be in the form $min\,max_{0\leq i\leq n}\,g_{i}(F_{i})$, where $g_{i}$ is any nondecreasing function and $F_{i}$ is the flow time. When $g_{i}(F_{i})=F_{i}-d_{i}=L_{i}$, the objective function corresponds to minimizing the maximum lateness, where $d_{i}$ is due time for job $i$ and $L_{i}$ lateness of job $i$. Another expression is $g_{i}(F_{i})=max{(F_{i}-d_{i},0)}$, which corresponds to minimizing the maximum tardiness.

Algorithm

The algorithm works by planning the job with the least impact as late as possible. Starting at $t=\sum p_{j}$.

$S$ set of already scheduled jobs (at start: S = $\emptyset$)
$J$ set of jobs which successors have been scheduled (at start: all jobs without successors)
$t$ time when the next job will be completed (at start: $t=\sum p_{j}$)
while$J\neq \emptyset$:
    select $j\in J$ such that $f_{j}(t)=min_{k\in J}f_{k}(t)$
    schedule $j$ such that it completes at time $t$
    add $j$ to $S$, delete $j$ from $J$ and update $J$.
    $t=t-p_{j}$
end while

Further reading

• Michael Pinedo. Scheduling: theory, algorithms, and systems. 2008. ISBN 978-0-387-78934-7
• Conway, Maxwell, Miller. Theory of Scheduling. 1967. ISBN 0-486-42817-6