Branch and bound crossed with GA to solve hybrid flowshops

Branch and bound crossed with GA to solve hybrid flowshops

0.00 Avg rating0 Votes
Article ID: iaor19992329
Country: Netherlands
Volume: 107
Issue: 2
Start Page Number: 389
End Page Number: 400
Publication Date: Jun 1998
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: programming: branch and bound
Abstract:

This article deals with an optimal method for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation shows that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.

Reviews

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