Header menu link for other important links
Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs
Published in
Volume: 155
Issue: 2
Pages: 426 - 438
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 [Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT '98), vol. 3, Verlag Mainz, Aachen, Germany, 1998, p. 1560], called max-min ant system (MMAS), by incorporating the summation rule suggested by Merkle and Middendorf [Proceedings of the EvoWorkshops 2000, Lecture Notes in Computer Science No. 1803, Springer-Verlag, Berlin, 2000, p. 287] 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 [European Journal of Operational Research 64 (1993) 278]. 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 [European Journal of Operational Research 64 (1993) 278] 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 [European Journal of Operational Research 132 (2001) 439], 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. © 2003 Elsevier B.V. All rights reserved.
About the journal
JournalEuropean Journal of Operational Research
Open AccessNo
Concepts (11)
  •  related image
  •  related image
  •  related image
    Heuristic methods
  •  related image
    Operations research
  •  related image
  •  related image
    Problem solving
  •  related image
  •  related image
  •  related image
  •  related image
  •  related image