Total flow time minimization in a flowshop sequence-dependent group scheduling problem

We have developed a mathematical programming model for minimizing total flow time of the flow shop sequence dependent group scheduling (FSDGS) problem, typically classified as F-m|fmls, S-plk, prmu|Sigma C-j. As the problem is shown to be strongly NP-hard, a tabu search (TS) algorithm as well as a hybrid ant colony optimization (HACO) algorithm have been developed to heuristically solve the problem. A lower bounding (LB) method based on the Branch-and-Price algorithm is also developed to evaluate the quality of the metaheuristic algorithms. In order to compare the performance of metaheuristic algorithms, random test problems, ranging in size from small, medium, to large are created and solved by both the TS and the HACO algorithms. A comparison shows that the HACO algorithm has a better performance than the TS algorithm. The results of the heuristic algorithms are also compared with the results of the LB method to evaluate the quality of the solutions. The LB method presented in this paper can be generalized to solve the FSDGS problem with other objective functions. (C) 2009 Elsevier Ltd. All rights reserved.