Complexity of machine scheduling problems

J.K. Lenstra; A.H.G. Rinnooy Kan; P. Brucker

doi:10.1016/S0167-5060(08)70743-X

Complexity of machine scheduling problems

J.K. Lenstra, A.H.G. Rinnooy Kan, P. Brucker

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

1698 Citations (Scopus)

31 Downloads (Pure)

Abstract

We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.

Original language	English
Pages (from-to)	343-362
Journal	Annals of Discrete Mathematics
Volume	1
DOIs	https://doi.org/10.1016/S0167-5060(08)70743-X
Publication status	Published - 1977

Access to Document

10.1016/S0167-5060(08)70743-X

Cite this

@article{7fab919cdfa9456db2b17d34ff2e26d1,

title = "Complexity of machine scheduling problems",

abstract = "We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.",

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

year = "1977",

doi = "10.1016/S0167-5060(08)70743-X",

language = "English",

volume = "1",

pages = "343--362",

journal = "Annals of Discrete Mathematics",

issn = "0167-5060",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Complexity of machine scheduling problems

AU - Lenstra, J.K.

AU - Rinnooy Kan, A.H.G.

AU - Brucker, P.

PY - 1977

Y1 - 1977

N2 - We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.

AB - We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.

U2 - 10.1016/S0167-5060(08)70743-X

DO - 10.1016/S0167-5060(08)70743-X

M3 - Article

SN - 0167-5060

VL - 1

SP - 343

EP - 362

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

ER -

Complexity of machine scheduling problems

Abstract

Access to Document

Fingerprint

Cite this