Skip to search boxSkip to navigationSkip to main content

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

English

Publication milestones

  • Published - 1994

Publication status

Published - 1994

Place of publication

Eindhoven

Publisher

Technische Universiteit Eindhoven

Publication 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