Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs

The problem of scheduling in permutation flowshops is considered with the objective of minimizing the makespan followed by the consideration of minimization of total flowtime of jobs. Two ant-colony optimization algorithms are proposed and analyzed for solving the permutation flowshop scheduling problem. The first algorithm extends the ideas of the ant-colony algorithm by Stuetzle, called max–min ant system (MMAS), by incorporating the summation rule suggested by Merkle and Middendorf and a newly proposed local search technique. The second ant-colony algorithm is newly developed. The proposed ant-colony algorithms have been applied to 90 benchmark problems taken from Taillard. First, a comparison of the solutions yielded by the MMAS and the two ant-colony algorithms developed in this paper, with the heuristic solutions given by Taillard is undertaken with respect to the minimization of makespan. The comparison shows that the two proposed ant-colony algorithms perform better, on an average, than the MMAS. Subsequently, by considering the objective of minimizing the total flowtime of jobs, a comparison of solutions yielded by the proposed ant-colony algorithms with the best heuristic solutions known for the benchmark problems, as published in an extensive study by Liu and Reeves, is carried out. The comparison shows that the proposed ant-colony algorithms are clearly superior to the heuristics analyzed by Liu and Reeves. For 83 out of 90 problems considered, better solutions have been found by the two proposed ant-colony algorithms, as compared to the solutions reported by Liu and Reeves.