Short shop schedules
成果类型：
Article
署名作者：
Williamson, DP; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK; Sevastjanov, SV; Shmoys, DB
署名单位：
Johns Hopkins University; Eindhoven University of Technology; Cornell University; Centrum Wiskunde & Informatica (CWI)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.2.288
发表日期：
1997
页码：
288-294
关键词：
摘要：
We consider the open shop, job shop, and flow shop scheduling problems with integral processing times. We give polynomial-time algorithms to determine if an instance has a schedule of length at most 3, and show that deciding if there is a schedule of length at most 4 is NP-complete. The latter result implies that, unless P = NP. there does not exist a polynomial-time approximation algorithm for any of these problems that constructs a schedule with length guaranteed to be strictly less than 5/4 times the optimal length. This work constitutes the first nontrivial theoretical evidence that shop scheduling problems are hard to solve even approximately.