<b>Evaluation of heuristics for a branch and bound algorithm to minimize the makespan in a flowshop with blocking
Abstract
This paper has the objective to evaluate the use of different methods to obtain an initial solution for the branch and bound algorithm with the objective of minimizing the makespan in a flowshop with zero buffer environment. As the problem is known to be NP-Hard, the branch and bound algorithm may take long computational time to find the best solution. The use of an initial solution may reduce the computational time, by providing an initial upper bound. In this work, the efficiency of the use of an initial solution to the Branch and Bound algorithm was evaluated by comparison of the algorithms. The branch and bound algorithm used, as well as the lower bound, was proposed by Ronconi (2005). Four heuristic methods (MM, PF, wPF, and PW) were tested using a 180 problems data. Results show that the use of an initial solution does considerably reduce the computational time.
Downloads
DECLARATION OF ORIGINALITY AND COPYRIGHTS
I Declare that current article is original and has not been submitted for publication, in part or in whole, to any other national or international journal.
The copyrights belong exclusively to the authors. Published content is licensed under Creative Commons Attribution 3.0 (CC BY 3.0) guidelines, which allows sharing (copy and distribution of the material in any medium or format) and adaptation (remix, transform, and build upon the material) for any purpose, even commercially, under the terms of attribution.
Read this link for further information on how to use CC BY 3.0 properly.