Sequencing and scheduling : algorithms and complexity

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

873 Citations (Scopus)

Abstract

Sequencing and scheduling as a research area is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. In this survey, we concentrate on the area of deterministic machine scheduling. We review complexity results and optimization and approximation algorithms for problems involving a single machine, parallel machines, open shops, flow shops and job shops. We also pay attention to two extensions of this area: resource-constrained project scheduling and stochastic machine scheduling.
Original languageEnglish
Title of host publicationLogistics of Production and Inventory
EditorsS.S. Graves, A.H.G. Rinnooy Kan, P. Zipkin
Place of PublicationAmsterdam
PublisherNorth-Holland Publishing Company
Pages445-522
ISBN (Print)0-444-87472-0
Publication statusPublished - 1993

Publication series

NameHandbooks in Operations Research and Management Science
Volume4
ISSN (Print)0927-0507

Fingerprint

Scheduling algorithms
Scheduling
Computer control
Approximation algorithms
Planning

Cite this

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling : algorithms and complexity. In S. S. Graves, A. H. G. Rinnooy Kan, & P. Zipkin (Eds.), Logistics of Production and Inventory (pp. 445-522). (Handbooks in Operations Research and Management Science; Vol. 4). Amsterdam: North-Holland Publishing Company.
Lawler, E.L. ; Lenstra, J.K. ; Rinnooy Kan, A.H.G. ; Shmoys, D.B. / Sequencing and scheduling : algorithms and complexity. Logistics of Production and Inventory. editor / S.S. Graves ; A.H.G. Rinnooy Kan ; P. Zipkin. Amsterdam : North-Holland Publishing Company, 1993. pp. 445-522 (Handbooks in Operations Research and Management Science).
@inbook{7bdd2b81119a4ef6b11de411241238a2,
title = "Sequencing and scheduling : algorithms and complexity",
abstract = "Sequencing and scheduling as a research area is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. In this survey, we concentrate on the area of deterministic machine scheduling. We review complexity results and optimization and approximation algorithms for problems involving a single machine, parallel machines, open shops, flow shops and job shops. We also pay attention to two extensions of this area: resource-constrained project scheduling and stochastic machine scheduling.",
author = "E.L. Lawler and J.K. Lenstra and {Rinnooy Kan}, A.H.G. and D.B. Shmoys",
year = "1993",
language = "English",
isbn = "0-444-87472-0",
series = "Handbooks in Operations Research and Management Science",
publisher = "North-Holland Publishing Company",
pages = "445--522",
editor = "S.S. Graves and {Rinnooy Kan}, A.H.G. and P. Zipkin",
booktitle = "Logistics of Production and Inventory",
address = "Netherlands",

}

Lawler, EL, Lenstra, JK, Rinnooy Kan, AHG & Shmoys, DB 1993, Sequencing and scheduling : algorithms and complexity. in SS Graves, AHG Rinnooy Kan & P Zipkin (eds), Logistics of Production and Inventory. Handbooks in Operations Research and Management Science, vol. 4, North-Holland Publishing Company, Amsterdam, pp. 445-522.

Sequencing and scheduling : algorithms and complexity. / Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B.

Logistics of Production and Inventory. ed. / S.S. Graves; A.H.G. Rinnooy Kan; P. Zipkin. Amsterdam : North-Holland Publishing Company, 1993. p. 445-522 (Handbooks in Operations Research and Management Science; Vol. 4).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

TY - CHAP

T1 - Sequencing and scheduling : algorithms and complexity

AU - Lawler, E.L.

AU - Lenstra, J.K.

AU - Rinnooy Kan, A.H.G.

AU - Shmoys, D.B.

PY - 1993

Y1 - 1993

N2 - Sequencing and scheduling as a research area is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. In this survey, we concentrate on the area of deterministic machine scheduling. We review complexity results and optimization and approximation algorithms for problems involving a single machine, parallel machines, open shops, flow shops and job shops. We also pay attention to two extensions of this area: resource-constrained project scheduling and stochastic machine scheduling.

AB - Sequencing and scheduling as a research area is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. In this survey, we concentrate on the area of deterministic machine scheduling. We review complexity results and optimization and approximation algorithms for problems involving a single machine, parallel machines, open shops, flow shops and job shops. We also pay attention to two extensions of this area: resource-constrained project scheduling and stochastic machine scheduling.

M3 - Chapter

SN - 0-444-87472-0

T3 - Handbooks in Operations Research and Management Science

SP - 445

EP - 522

BT - Logistics of Production and Inventory

A2 - Graves, S.S.

A2 - Rinnooy Kan, A.H.G.

A2 - Zipkin, P.

PB - North-Holland Publishing Company

CY - Amsterdam

ER -

Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. Sequencing and scheduling : algorithms and complexity. In Graves SS, Rinnooy Kan AHG, Zipkin P, editors, Logistics of Production and Inventory. Amsterdam: North-Holland Publishing Company. 1993. p. 445-522. (Handbooks in Operations Research and Management Science).