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

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. (c) 2005 Elsevier B.V. All rights reserved.