Two ant-colony algorithms for minimizing total flowtime in permutation flowshops

The problem of scheduling in flowshops with the objective of minimizing total flowtime is studied. For solving the problem two ant-colony algorithms are proposed and analyzed. The first algorithm refers to some extent to ideas by Stuetzle [Stuetzle, T. (1998). An ant approach for the flow shop problem. In: Proceedings of the sixth European Congress on intelligent techniques and soft computing (EUFIT '98) (Vol. 3) (pp. 1560-1564). Aachen: Verlag Mainz] and Merkle and Middendorf [Merkle, D., & Middendorf, M. (2000). An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Proceedings of the EvoWorkshops 2000, lecture notes in computer science 1803 (pp. 287-296). Berlin: Springer]. The second algorithm is newly developed. The proposed ant-colony algorithms have been applied to 90 benchmark problems taken from Taillard [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278-285]. A comparison of the solutions yielded by the ant-colony algorithms with the best heuristic solutions known for the benchmark problems up to now, as published in extensive studies by Liu and Reeves [Liu, J., & Reeves, C.R. (2001)]. Constructive and composite heuristic solutions to the P//Sigma C-i scheduling problem. European Journal of Operational Research, 132, 439-452, and Rajendran and Ziegler [Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155, 426-438], shows that the presented ant-colony algorithms are better, on an average, than the heuristics analyzed by Liu and Reeves and Rajendran and Ziegler. (c) 2004 Elsevier Ltd. All rights reserved.