TY - JOUR
T1 - Optimization and approximation in deterministic sequencing and scheduling : a survey
AU - Graham, R.L.
AU - Lawler, E.L.
AU - Lenstra, J.K.
AU - Rinnooy Kan, A.H.G.
PY - 1979
Y1 - 1979
N2 - The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
AB - The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
U2 - 10.1016/S0167-5060(08)70356-X
DO - 10.1016/S0167-5060(08)70356-X
M3 - Article
SN - 0167-5060
VL - 5
SP - 287
EP - 326
JO - Annals of Discrete Mathematics
JF - Annals of Discrete Mathematics
ER -