Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness |
| |
Authors: | Patchrawat “Patch” Uthaisombut |
| |
Affiliation: | (1) Department of Computer Science, University of Pittsburgh, Pittsburgh, USA |
| |
Abstract: | It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) 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|r
j
,pmtn|L
max ). 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. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived. |
| |
Keywords: | Machine scheduling Scheduling algorithms Online algorithms Compound laxity Laxity EDF Earliest deadline first Maximum lateness |
本文献已被 SpringerLink 等数据库收录! |