# Lawler's algorithm

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Lawler’s algorithm is a powerful technique for solving a variety of constrained scheduling problems.[1] 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 ${\displaystyle min\,max_{0\leq i\leq n}\,g_{i}(F_{i})}$, where ${\displaystyle g_{i}}$ is any nondecreasing function and ${\displaystyle F_{i}}$ is the flow time.[2] When ${\displaystyle g_{i}(F_{i})=F_{i}-d_{i}=L_{i}}$, the objective function corresponds to minimizing the maximum lateness, where ${\displaystyle d_{i}}$ is due time for job ${\displaystyle i}$ and ${\displaystyle L_{i}}$ lateness of job ${\displaystyle i}$. Another expression is ${\displaystyle g_{i}(F_{i})=max{(F_{i}-d_{i},0)}}$, which corresponds to minimizing the maximum tardiness.

## References

1. Steven Nahmias. Production and Operations Analysis. 2008. ISBN 978-0-07-126370-2
2. Joseph Y-T. Leung. Handbook of scheduling: algorithms, models, and performance analysis. 2004. ISBN 978-1-58488-397-5