Short shop schedules

D.P. Williamson, L.A. Hall, J.A. Hoogeveen, J.K. Lenstra, D.B. Shmoys

    Research output: Book/ReportReportAcademic

    67 Downloads (Pure)


    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.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages15
    Publication statusPublished - 1994

    Publication series

    NameMemorandum COSOR
    ISSN (Print)0926-4493


    Dive into the research topics of 'Short shop schedules'. Together they form a unique fingerprint.

    Cite this