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

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

0.00 Avg rating0 Votes
Article ID: iaor19982215
Country: Netherlands
Volume: 89
Issue: 1
Start Page Number: 172
End Page Number: 175
Publication Date: Feb 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: parallel machines, complexity, flowshop
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.