Short shop schedules
- D.P. Williamson,
- L.A. Hall,
- J.A. Hoogeveen,
- J.K. Lenstra,
- D.B. Shmoys
Output:
Book/Report
Report
Academic
Open access
Information
Output type
Output:
Book/Report
Report
Academic
Original language
EnglishPublication milestones
- Published - 1994
Publication status
Published - 1994
Place of publication
EindhovenPublisher
Technische Universiteit EindhovenPublication series
- Publication series name: Memorandum COSOR
ISSN (Print): 0926-4493
Volume: 9406
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 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.
Documents and Links
Final published version, 801.55 KB
Metrics
Metrics
Download statistics
Download count
247
