Flowshop scheduling with identical jobs and uniform parallel machines

The single-stage scheduling problem to minimize the makespan of identical jobs on uniform parallel machines is known to be solvable in polynomial-time. We extend this work to consider multi-stage systems with flowshop configuration. We show that the 2-stage problem may also be solved in polynomial-time and for the number of stages greater than two, the problem is shown to be NP-hard. We present a branch and bound procedure which provides an optimal solution to the 3-stage problem, and a fast heuristic procedure that is shown to provide good approximate solutions on sample problems. This heuristic is a natural extension of the 2-stage polynomial-time procedure. We develop theoretical bounds showing that the maximum deviation between the solution derived by the heuristic procedure and the optimal solution is bounded by the maximum processing time of a machine at the second stage, independent of the number of jobs and the processing times at the first and third stages. We also show that the heuristic provides an approximate solution bounded by a ratio of 1.75 to the optimal solution. (C) 1998 Elsevier Science B.V. All rights reserved.