Premium
Minimizing maximum lateness on one machine: computational experience and some applications
Author(s) -
Lageweg B. J.,
Lenstra J. K.,
Kan A. H. G. Rinnooy
Publication year - 1976
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.1976.tb00264.x
Subject(s) - scheduling (production processes) , mathematical optimization , computer science , job shop scheduling , due date , single machine scheduling , operations research , mathematics , schedule , operating system
Summary We consider the problem of scheduling jobs on a single machine subject to given release dates and precedence constraints, in order to minimize maximum lateness. The algorithms of B aker and S u (Naval Res. Logist. Quart. 21 (1974) 171–176) and of M c M ahon and F lorian (Operations Res. 23 (1975) 475–482) for the problem without precedence constraints are extended to the general case. An extensive computational comparison establishes the superiority of the latter algorithm. We describe applications to the theory of job‐shop scheduling and to a practical scheduling situation.