zhang-2021-correlation.pdf (4.8 MB)
Download fileCorrelation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling
journal contribution
posted on 2022-05-04, 09:42 authored by Fangfang ZhangFangfang Zhang, Yi MeiYi Mei, S Nguyen, Mengjie ZhangMengjie ZhangDynamic 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.3056143Publisher DOI
Journal title
IEEE Transactions on Evolutionary ComputationVolume
25Issue
3Publication date
2021-06-01Pagination
552-566Publisher
Institute of Electrical and Electronics Engineers (IEEE)Publication status
PublishedISSN
1089-778XeISSN
1941-0026Usage metrics
Categories
Keywords
Dynamic schedulingJob shop schedulingSequential analysisProcessor schedulingRoutingGenetic programmingHeuristic algorithmsCorrelation coefficientdynamic flexible job shop scheduling (JSS)genetic programming (GP)hyperheuristicsrecombinative guidanceArtificial Intelligence & Image ProcessingInformation SystemsArtificial Intelligence and Image ProcessingElectrical and Electronic Engineering not elsewhere classified