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

Zhongshan ZHANG  Yuning CHEN  Yuejin TAN  Jungang YAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.10   pp.1856-1862
Publication Date: 2016/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1856
Type of Manuscript: PAPER
Category: Mathematical Systems Science
non-crossover and multi-mutation genetic algorithm,  flexible job-shop scheduling,  variation operators,  makespan,  

Full Text: PDF(1.4MB)>>
Buy this Article

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.