Short Shop Schedules

D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov and D. B. Shmoys
Additional contact information
D. P. Williamson: IBM Watson, Yorktown Heights, New York
L. A. Hall: The Johns Hopkins University, Baltimore, Maryland
J. A. Hoogeveen: Eindhoven University of Technology, Amsterdam, The Netherlands
C. A. J. Hurkens: Eindhoven University of Technology, Amsterdam, The Netherlands
J. K. Lenstra: Eindhoven University of Technology, Eindhoven, The Netherlands, and CWI, Amsterdam, The Netherlands
S. V. Sevast'janov: Institute of Mathematics, Novosibirsk, Russia
D. B. Shmoys: Cornell University, Ithaca, New York

Operations Research, 1997, vol. 45, issue 2, 288-294

Abstract: 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 (N-script)(P-script)-complete. The latter result implies that, unless (P-script) = (N-script)(P-script), 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.

Keywords: analysis of algorithms; computational complexity; NP-completeness results; production/scheduling; approximations; impossibility results; production/scheduling; multiple machine deterministic scheduling; nonpreemptive shop scheduling (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.2.288 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:2:p:288-294

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().