A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems

2006-10-01
Chung, Chia-Shin
Flynn, James
Kırca, Ömer
The m-machine permutation flowshop problem with the total tardiness objective is a common scheduling problem, which is known to be NP-hard. Here, we develop a branch and bound algorithm to solve this problem. Our algorithm incorporates a machine-based lower bound and a dominance test for pruning nodes. We undertake a numerical study that evaluates our algorithm and compares it with the best alternative existing algorithm. Extensive computational experiments indicate that our algorithm performs better and can handle test problems with n <= 20.

Citation Formats
C.-S. Chung, J. Flynn, and Ö. Kırca, “A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 174, no. 1, pp. 1–10, 2006, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41897.