A branch-and-bound-based local search method for the flow shop problem

A branch-and-bound-based local search method for the flow shop problem

0.00 Avg rating0 Votes
Article ID: iaor20041559
Country: United Kingdom
Volume: 54
Issue: 10
Start Page Number: 1076
End Page Number: 1084
Publication Date: Oct 2003
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: production, combinatorial analysis, programming: branch and bound
Abstract:

It is well-known that exact branch and bound methods can only solve small or moderately sized NP-hard combinatorial optimization problems. In this paper, we address the issue of embedding an approximate branch and bound algorithm into a local search framework. The resulting heuristic has been applied to the problem of finding a minimum makespan in the permutation flow shop problem. Computational experiments carried out on a large set of benchmark problems show that the proposed method consistently yields optimal or near-optimal solutions for instances with up to 200 jobs and 10 machines. In particular, for 19 instances, the heuristic produces solutions that outperform the best known ones.

Reviews

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