Enhancing Genetic Programming based Hyper-Heuristics for Dynamic Multi-objective Job Shop Scheduling Problems

Genetic programming based hyper-heuristics have been an suitable approach to designing powerful dispatching rules for dynamic job shop scheduling. However, most current methods only focus on a single objective while practical problems almost always involve multiple conflicting objectives. Some efforts have been made to design non-dominated dispatching rules but using genetic programming to deal with multiple objectives is still very challenging because of the large search space and the stochastic characteristics of job shops. This paper investigates different strategies to utilise computational budgets when evolving dispatching rules with genetic programming. The results suggest that using local search heuristics can enhance the quality of evolved dispatching rules. Moreover, the results show that there are some differences in evolving rules for single objectives and for multiple objectives and that it is difficult to efficiently estimate the Pareto dominance of rules.