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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Josip Hrvatić,
  • Marko Đurasević,
  • Francisco Javier Gil-Gala,
  • Domagoj Jakobović

摘要

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.