Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard

J.A. Hoogeveen, J.K. Lenstra, B. Veltman

    Research output: Book/ReportReportAcademic

    200 Downloads (Pure)


    Johnson [1954] gave an efficient algorithm for minimizing makespan in a two-rnachine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule [1959] finds a shortest preemptive schedule on identical parallel machines in linear time. A similarly efficient algorithm is unlikely to exist for the simplest common generalization of these prblems. We show that preemptive scheduling in a two-stage flow shop with at least two identical parallel machines in oneofthe stages so as to minimize makespan is NP-hard in the strong sense. Key Words & Phrases: flow shop, parallel machines, complexity, NP-hardness.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages5
    Publication statusPublished - 1993

    Publication series

    NameMemorandum COSOR
    ISSN (Print)0926-4493


    Dive into the research topics of 'Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard'. Together they form a unique fingerprint.

    Cite this