Article ID: | iaor2001220 |
Country: | Netherlands |
Volume: | 64 |
Start Page Number: | 113 |
End Page Number: | 125 |
Publication Date: | Jan 2000 |
Journal: | International Journal of Production Economics |
Authors: | Moursli O., Pochet Y. |
Keywords: | programming: branch and bound |
This paper introduces a branch-and-bound algorithm for the hybrid flowshop scheduling problem to minimize makespan. The algorithm can also cope with problems with release dates and tails. Several heuristics are used to compute upper bounds. Lower bounds are based upon the single-stage subproblem relaxation. Several upper and lower bounding strategies are considered. Numerical tests show that, in a few minutes of running time, and even for the hardest (i.e. without a bottleneck stage) and mid-size problems, the algorithm has reduced the initial gap between upper and lower bounds by 50% on average.