Article ID: | iaor20021172 |
Country: | United States |
Volume: | 31 |
Issue: | 8 |
Start Page Number: | 721 |
End Page Number: | 731 |
Publication Date: | Aug 1999 |
Journal: | IIE Transactions |
Authors: | Bard J.F., Rio-Mercado R.Z. |
Keywords: | programming: branch and bound |
This paper presents a branch-and-bound enumeration scheme for the makespan minimization of the permutation flowshop scheduling problem with sequence-dependent setup times. The algorithm includes the implementation of both lower and upper bounding procedures, a dominance elimination criterion, and special features such as a partial enumeration strategy. A computational evaluation of the overall scheme demonstrates the effectiveness of each component. Test results are provided for a wide range of problem instances.