Can Mutations Replace Local Search? Studying the Effect of Repeated Genetic Programming Operators in the Unrelated Machines Environment

Dispatching rules are simple heuristics primarily used for solving dynamic scheduling problems. Since designing such rules manually is time-consuming and requires expert knowledge, genetic programming is employed to develop them automatically. However, the quality of those automatically developed rules is limited and must therefore be further improved by integrating genetic programming with more sophisticated methods, most notably local search. This paper explores the potential of substituting local search algorithms with repeated applications of genetic operators, specifically mutation and crossover, within genetic programming to obtain better performing dispatching rules for the unrelated machines scheduling environment. Experimental results indicate that certain configurations of repeated genetic operators significantly outperform the baseline genetic programming approach and can be comparable or, at times, superior to the variants enhanced by local search. This finding indicates a significant advancement in evolutionary algorithm design for scheduling problems, proposing the strategic repetition of genetic operators as a potentially simpler yet effective alternative to more complex local search strategies.