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

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

Research output: Book/ReportReportAcademic

243 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