Non-Crossover and Multi-Mutation Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem

Zhongshan ZHANG; Yuning CHEN; Yuejin TAN; Jungang YAN

doi:10.1587/transfun.E99.A.1856

Non-Crossover and Multi-Mutation Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem

Zhongshan ZHANG, Yuning CHEN, Yuejin TAN, Jungang YAN

Full Text Views

0

Share
Cite this

Summary :

This paper presents a non-crossover and multi-mutation based genetic algorithm (NMGA) for the Flexible Job-shop Scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). Aiming at the characteristics of FJSP, three mutation operators based on operation sequence coding and machine assignment coding are proposed: flip, slide, and swap. Meanwhile, the NMGA framework, coding scheme, as well as the decoding algorithm are also specially designed for the FJSP. In the framework, recombination operator crossover is not included and a special selection strategy is employed. Computational results based on a set of representative benchmark problems were provided. The evidence indicates that the proposed algorithm is superior to several recently published genetic algorithms in terms of solution quality and convergence ability.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.10 pp.1856-1862

Publication Date: 2016/10/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E99.A.1856

Type of Manuscript: PAPER

Category: Mathematical Systems Science

Authors

Zhongshan ZHANG
  National University of Defense Technology
Yuning CHEN
  University d'Angers
Yuejin TAN
  National University of Defense Technology
Jungang YAN
  National University of Defense Technology

Keyword

non-crossover and multi-mutation genetic algorithm, flexible job-shop scheduling, variation operators, makespan

Cite this

Copy

Zhongshan ZHANG, Yuning CHEN, Yuejin TAN, Jungang YAN, "Non-Crossover and Multi-Mutation Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E99-A, no. 10, pp. 1856-1862, October 2016, doi: 10.1587/transfun.E99.A.1856.
Abstract: This paper presents a non-crossover and multi-mutation based genetic algorithm (NMGA) for the Flexible Job-shop Scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). Aiming at the characteristics of FJSP, three mutation operators based on operation sequence coding and machine assignment coding are proposed: flip, slide, and swap. Meanwhile, the NMGA framework, coding scheme, as well as the decoding algorithm are also specially designed for the FJSP. In the framework, recombination operator crossover is not included and a special selection strategy is employed. Computational results based on a set of representative benchmark problems were provided. The evidence indicates that the proposed algorithm is superior to several recently published genetic algorithms in terms of solution quality and convergence ability.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1856/_p

Copy

@ARTICLE{e99-a_10_1856,
author={Zhongshan ZHANG, Yuning CHEN, Yuejin TAN, Jungang YAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Non-Crossover and Multi-Mutation Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem},
year={2016},
volume={E99-A},
number={10},
pages={1856-1862},
abstract={This paper presents a non-crossover and multi-mutation based genetic algorithm (NMGA) for the Flexible Job-shop Scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). Aiming at the characteristics of FJSP, three mutation operators based on operation sequence coding and machine assignment coding are proposed: flip, slide, and swap. Meanwhile, the NMGA framework, coding scheme, as well as the decoding algorithm are also specially designed for the FJSP. In the framework, recombination operator crossover is not included and a special selection strategy is employed. Computational results based on a set of representative benchmark problems were provided. The evidence indicates that the proposed algorithm is superior to several recently published genetic algorithms in terms of solution quality and convergence ability.},
keywords={},
doi={10.1587/transfun.E99.A.1856},
ISSN={1745-1337},
month={October},}

Copy

TY - JOUR
TI - Non-Crossover and Multi-Mutation Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1856
EP - 1862
AU - Zhongshan ZHANG
AU - Yuning CHEN
AU - Yuejin TAN
AU - Jungang YAN
PY - 2016
DO - 10.1587/transfun.E99.A.1856
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2016
AB - This paper presents a non-crossover and multi-mutation based genetic algorithm (NMGA) for the Flexible Job-shop Scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). Aiming at the characteristics of FJSP, three mutation operators based on operation sequence coding and machine assignment coding are proposed: flip, slide, and swap. Meanwhile, the NMGA framework, coding scheme, as well as the decoding algorithm are also specially designed for the FJSP. In the framework, recombination operator crossover is not included and a special selection strategy is employed. Computational results based on a set of representative benchmark problems were provided. The evidence indicates that the proposed algorithm is superior to several recently published genetic algorithms in terms of solution quality and convergence ability.
ER -