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

B.J. Lageweg; J.K. Lenstra; A.H.G. Rinnooy Kan

doi:10.1111/j.1467-9574.1976.tb00264.x

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

B.J. Lageweg, J.K. Lenstra, A.H.G. Rinnooy Kan

Research output: Contribution to journal › Article › Academic › peer-review

84 Citations (Scopus)

5 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	25-41
Number of pages	17
Journal	Statistica Neerlandica
Volume	30
Issue number	1
DOIs	https://doi.org/10.1111/j.1467-9574.1976.tb00264.x
Publication status	Published - 1976

Access to Document

10.1111/j.1467-9574.1976.tb00264.x

Cite this

@article{df4d1b701d284b37a9bf4dd1876c8a0f,

title = "Minimizing maximum lateness on one machine : computational experience and some applications",

abstract = "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.",

author = "B.J. Lageweg and J.K. Lenstra and {Rinnooy Kan}, A.H.G.",

year = "1976",

doi = "10.1111/j.1467-9574.1976.tb00264.x",

language = "English",

volume = "30",

pages = "25--41",

journal = "Statistica Neerlandica",

issn = "0039-0402",

publisher = "Wiley-Blackwell",

number = "1",

}

TY - JOUR

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

AU - Lageweg, B.J.

AU - Lenstra, J.K.

AU - Rinnooy Kan, A.H.G.

PY - 1976

Y1 - 1976

N2 - 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.

AB - 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.

U2 - 10.1111/j.1467-9574.1976.tb00264.x

DO - 10.1111/j.1467-9574.1976.tb00264.x

M3 - Article

SN - 0039-0402

VL - 30

SP - 25

EP - 41

JO - Statistica Neerlandica

JF - Statistica Neerlandica

IS - 1

ER -

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

Abstract

Access to Document

Fingerprint

Cite this