Flowshop scheduling with identical jobs and uniform parallel machines

Flowshop scheduling with identical jobs and uniform parallel machines

0.00 Avg rating0 Votes
Article ID: iaor19992908
Country: Netherlands
Volume: 109
Issue: 3
Start Page Number: 620
End Page Number: 631
Publication Date: Sep 1998
Journal: European Journal of Operational Research
Authors: , ,
Keywords: flowshop, parallel machines
Abstract:

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.

Reviews

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