A hybrid algorithm to minimize makespan for the permutation flow shop scheduling problem

DOI

10.2991/ijcis.2010.3.6.15How to use a DOI?

Keywords

Permutation flow shop; Makespan; Ant colony optimization; Gupta's heuristic; Local search.

Abstract

This paper deals with the permutation flow shop scheduling problem. The objective is to minimize the maximum completion time, or makespan. To solve this problem which has been proved to be strongly NP-hard, a combination between an ant colony algorithm, a heuristic algorithm and a local search procedure is proposed and presented. The hybrid approach is to use artificial ants to construct solutions by applying a stochastic greedy rule based on the Gupta’s heuristic and pheromone trails. A local search is then performed to improve the performance quality of constructed solutions. Once all ants have terminated their generations, the pheromone trails are modified according to a global updating rule. The proposed algorithm is applied to benchmark problems taken from the literature and compared with other metaheuristics. Computational experiments are given to demonstrate the superiority of the algorithm in the quality of solution and CPU time.

Copyright

© 2010, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - JOUR
AU  - Fardin Ahmadizar
AU  - Farnaz Barzinpour
PY  - 2010
DA  - 2010/12/01
TI  - A hybrid algorithm to minimize makespan for the permutation flow shop scheduling problem
JO  - International Journal of Computational Intelligence Systems
SP  - 853
EP  - 861
VL  - 3
IS  - 6
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.2010.3.6.15
DO  - 10.2991/ijcis.2010.3.6.15
ID  - Ahmadizar2010
ER  -