A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem

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)

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  -