Scheduling a two-stage hybrid flow shop with parallel machines at the first stage

Scheduling a two-stage hybrid flow shop with parallel machines at the first stage

0.00 Avg rating0 Votes
Article ID: iaor19971866
Country: Netherlands
Volume: 69
Issue: 1
Start Page Number: 171
End Page Number: 191
Publication Date: Jan 1997
Journal: Annals of Operations Research
Authors: , ,
Abstract:

This paper considers a non-preemptive two-stage hybrid flow shop problem in which the first stage contains several identical machines, and the second stage contains a single machine. Each job is to be processed on one of the first-stage machines, and then on the second-stage machine. The objective is to find a schedule which minimizes the maximum completion time or makespan. The problem is NP-hard in the strong sense, even when there are two machines at the first stage. Several lower bounds are derived and are tested in a branch and bound algorithm. Also, constructive heuristics are presented, and a descent algorithm is proposed. Extensive computational tests with up to 250 jobs, and up to 10 machines in the first stage, indicate that some of the heuristics consistently generate optimal or near-optimal solutions.

Reviews

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