Genetic programming with diverse partner selection for dynamic flexible job shop scheduling
Meng Ran Xu, Yi Mei, Fangfang Zhang, Mengjie Zhang · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2022
Dynamic flexible job shop scheduling (DFJSS) aims to make decisions for machine assignment and operation sequencing simultaneously to get an effective schedule under dynamic environments. Genetic programming hyper-heuristic (GPHH) has been successfully applied to evolve scheduling heuristics for the DFJSS problem. Parent selection plays an important role in GPHH for generating high-quality offspring. Traditional GPHHs select parents for crossover purely based on fitness (e.g., tournament selection). This might be too greedy to get good offspring and the selected parents might have similar structures/behaviours. In this paper, a GPHH method with a new diverse partner selection (DPS) scheme is proposed, namely GPDPS, for DFJSS. Specifically, we first define a new multi-case fitness to characterise the behaviour of each scheduling heuristic for DFJSS. Then, the newly proposed DPS method selects a pair of complementary high-quality parents for crossover to generate offspring. The experimental results show that GPDPS significantly outperforms the GPHH method on most of the DFJSS scenarios, in terms of both test performance and convergence speed.