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

The m-machine permutation flowshop problem with the total flow-time objective is a common scheduling problem, which is known to be NP-hard for m greater than or equal to 2. In this article, we develop a branch and bound algorithm to solve both the weighted and unweighted version of this problem. Our algorithm incorporates a new machine-based lower bound and a dominance test for pruning nodes. Computational experiments suggest that the algorithm can handle test problems with n less than or equal to 15. It also seems capable of dealing with larger problems for the unweighted objective, especially when the processing times are correlated. (C) 2002 Elsevier Science B.V. All rights reserved.