zhang-2021-correlation.pdf (4.8 MB)
Download file

Correlation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling

Download (4.8 MB)
journal contribution
posted on 04.05.2022, 09:42 by Fangfang ZhangFangfang Zhang, Yi MeiYi Mei, S Nguyen, Mengjie ZhangMengjie Zhang
Dynamic flexible job shop scheduling (JSS) is a challenging combinatorial optimization problem due to its complex environment. In this problem, machine assignment and operation sequencing decisions need to be made simultaneously under the dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully used to evolve scheduling heuristics for dynamic flexible JSS. However, in traditional GP, recombination between parents may disrupt the beneficial building blocks by choosing the crossover points randomly. This article proposes a recombinative mechanism to provide guidance for GP to realize effective and adaptive recombination for parents to produce offspring. Specifically, we define a novel measure for the importance of each subtree of an individual, and the importance information is utilized to decide the crossover points. The proposed recombinative guidance mechanism attempts to improve the quality of offspring by preserving the promising building blocks of one parent and incorporating good building blocks from the other. The proposed algorithm is examined on six scenarios with different configurations. The results show that the proposed algorithm significantly outperforms the state-of-the-art algorithms on most tested scenarios, in terms of both final test performance and convergence speed. In addition, the rules obtained by the proposed algorithm have good interpretability.

History

Preferred citation

Zhang, F., Mei, Y., Nguyen, S. & Zhang, M. (2021). Correlation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation, 25(3), 552-566. https://doi.org/10.1109/TEVC.2021.3056143

Journal title

IEEE Transactions on Evolutionary Computation

Volume

25

Issue

3

Publication date

01/06/2021

Pagination

552-566

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Publication status

Published

ISSN

1089-778X

eISSN

1941-0026