International Journal of Computational Intelligence Systems

Volume 3, Issue 6, December 2010, Pages 853 - 861

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

Authors
Fardin Ahmadizar, Farnaz Barzinpour
Corresponding Author
Fardin Ahmadizar
Received 15 June 2010, Accepted 27 October 2010, Available Online 1 December 2010.
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)

Journal
International Journal of Computational Intelligence Systems
Volume-Issue
3 - 6
Pages
853 - 861
Publication Date
2010/12/01
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.2010.3.6.15How to use a DOI?
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/).

Cite this article

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  -