Header menu link for other important links
X
Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs
Published in
2004
Volume: 155
   
Issue: 2
Pages: 426 - 438
Abstract
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
ISSN03772217
Open AccessNo
Concepts (11)
  •  related image
    Algorithms
  •  related image
    Benchmarking
  •  related image
    Heuristic methods
  •  related image
    Operations research
  •  related image
    Optimization
  •  related image
    Problem solving
  •  related image
    ANT-COLONY ALGORITHM
  •  related image
    FLOWSHOP
  •  related image
    MAKESPAN
  •  related image
    TOTAL FLOWTIME
  •  related image
    Scheduling