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

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

Research output: Contribution to journalArticleAcademicpeer-review

203 Citations (Scopus)
1 Downloads (Pure)


In 1954, Johnson gave an efficient algorithm for minimizing makespan in a two-machine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule of 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 problems. We show that preemptive scheduling in a two-stage flow shop with at least two identical parallel machines in one of the stages so as to minimize makespan is NP-hard in the strong sense.
Original languageEnglish
Pages (from-to)172-175
Number of pages4
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 1996


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