Surrogate-Assisted Automatic Evolving of Dispatching Rules for Multi-Objective Dynamic Job Shop Scheduling Using Genetic Programming

Dispatching rules are simple but efficient heuristics to solve multi-objective job shop scheduling problems, particularly useful to face the challenges of dynamic shop environments. A promising method to automatically evolve such rules represents genetic programming based hyper-heuristic (GP-HH). However, one of the main drawbacks of existing approaches is the computational demanding simulation-based fitness evaluation of the evolving rules. To efficiently allocate the computational budget, surrogate models can be employed to approximate the fitness. Two possible ways, that estimate the fitness either based on a simplified problem or based on samples of fully evaluated individuals making use of machine learning techniques are investigated in this paper. Several representatives of both categories are first examined with regard to their selection accuracy and execution time. Furthermore, we developed a surrogate-assisted multi-objective GP-HH framework, incorporating a pre-selection task in the NSGA-II algorithm. The most promising candidate of the two surrogate categories is consequently implemented in the framework. Using a dynamic job shop scenario, the two proposed algorithms are compared to the original one without using surrogates. With the aim to minimize the mean flowtime and maximum tardiness, experimental results demonstrate that the proposed algorithms outperform the former. Another interesting finding shows that the enhanced ability to identify duplicates based on the phenotypic characterization of individuals is particularly helpful in increasing diversity within a population. This study illustrates the positive effect of this mechanism on the exploration of the entire Pareto front