Minimizing maximum lateness on one machine : computational experience and some applications

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 BAKER and Su (Naval Res. Logist. Quart. 2] (1974) 171- 176) and of McMAHON and FLORIAN (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