A computational study of the permutation flow shop problem based on a tight lower bound

A computational study of the permutation flow shop problem based on a tight lower bound

0.00 Avg rating0 Votes
Article ID: iaor2006792
Country: United Kingdom
Volume: 32
Issue: 7
Start Page Number: 1831
End Page Number: 1847
Publication Date: Jul 2005
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

We consider the classical permutation flow shop problem which requires scheduling n jobs through m machines which are placed in series so as to minimize the makespan. This problem is known to be NP-hard. We describe a branch-and-bound algorithm with a lower bounding procedure based on the so-called two-machine flow shop problem with time lags, ready times, and delivery times. We present extensive computational results on both random instances, with up to 8000 operations, and well-known benchmarks, with up to 2000 operations, which show that the proposed algorithm solves large-scale instances in moderate CPU time. In particular, we report proven optimal solutions for benchmark problems which have been open for some time.

Reviews

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