Generalization of Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF): Identifying all optimal online algorithms for minimizing maximum lateness

It is well known that the Earliest-Deadline-First and the Least-Laxity-First algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|rj,pmtn|Lmax). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation.