International Journal of Computational Intelligence Systems

Volume 4, Issue 4, June 2011, Pages 497 - 508

A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem

Authors
Jian Gao, Rong Chen
Corresponding Author
Rong Chen
Received 12 December 2010, Accepted 31 January 2011, Available Online 1 June 2011.
DOI
10.2991/ijcis.2011.4.4.9How to use a DOI?
Keywords
Distributed scheduling; Permutation flowshop; Genetic algorithm; Local search
Abstract

Distributed Permutation Flowshop Scheduling Problem (DPFSP) is a newly proposed scheduling problem, which is a generalization of classical permutation flow shop scheduling problem. The DPFSP is NP-hard in general. It is in the early stages of studies on algorithms for solving this problem. In this paper, we propose a GA-based algorithm, denoted by GA_LS, for solving this problem with objective to minimize the maximum completion time. In the proposed GA_LS, crossover and mutation operators are designed to make it suitable for the representation of DPFSP solutions, where the set of partial job sequences is employed. Furthermore, GA_LS utilizes an efficient local search method to explore neighboring solutions. The local search method uses three proposed rules that move jobs within a factory or between two factories. Intensive experiments on the benchmark instances, extended from Taillard instances, are carried out. The results indicate that the proposed hybrid genetic algorithm can obtain better solutions than all the existing algorithms for the DPFSP, since it obtains better relative percentage deviation and differences of the results are also statistically significant. It is also seen that best-known solutions for most instances are updated by our algorithm. Moreover, we also show the efficiency of the GA_LS by comparing with similar genetic algorithms with the existing local search methods.

Copyright
© 2011, 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
4 - 4
Pages
497 - 508
Publication Date
2011/06/01
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.2011.4.4.9How to use a DOI?
Copyright
© 2011, 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  - Jian Gao
AU  - Rong Chen
PY  - 2011
DA  - 2011/06/01
TI  - A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem
JO  - International Journal of Computational Intelligence Systems
SP  - 497
EP  - 508
VL  - 4
IS  - 4
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.2011.4.4.9
DO  - 10.2991/ijcis.2011.4.4.9
ID  - Gao2011
ER  -