A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem

作者：Hsu Chia Yu; Chang Pei Chann^*; Chen Meng Hui

来源：Computers & Industrial Engineering, 2015, 83: 159-171.

DOI：10.1016/j.cie.2015.02.009

• Block
• Linkage
• Association rule
• Artificial chromosome
• Recombination
• Permutation flowshop scheduling problem

A genetic algorithm is a type of heuristic algorithm used to solve permutation flowshop scheduling problems (PFSPs). Producing an optimal offspring with a variety of genes is difficult because of the evolution of the gene selection and a crossover mechanism that leads to local optima. This study proposes a linkage mining in block-based evolutionary algorithm (LMBBEA) for solving the PFSP, in which the association rule extracts various good genes and increases gene diversity. These genes are used to generate various blocks for artificial chromosome combinations. The generated blocks not only improve the chance of finding optimal solutions but also enhance the efficiency of convergence. The proposed LMBBEA is compared with other algorithms through numerical experiments, namely the Taillard and Reeves experiments in the OR-Library. To compare with other algorithms, the solutions produced by the proposed LMBBEA are closest to the optimal solution. The LMBBEA has a high convergence speed and a better solution quality due to an increase in the diversity of solutions.

• 出版日期2015-5