Selection of dispatching rules evolved by genetic programming in dynamic unrelated machines scheduling based on problem characteristics

Dispatching rules are fast and simple procedures for creating schedules for various kinds of scheduling problems. However, manually designing DRs for all possible scheduling conditions and scheduling criteria is practically infeasible. For this reason, much of the research has focused on the automatic design of DRs using various methods, especially genetic programming. However, even if genetic programming is used to design new DRs to optimise a particular criterion, it will not give good results for all possible problem instances to which it can be applied. Due to the stochastic nature of genetic programming, the evolution of DRs must be performed several times to ensure that good DRs have been obtained. However, in the end, usually only one rule is selected from the set of evolved DRs and used to solve new scheduling problems. In this paper, a DR selection procedure is proposed to select the appropriate DR from the set of evolved DRs based on the features of the problem instances to be solved. The proposed procedure is executed simultaneously with the execution of the system, approximating the properties of the problem instances and selecting the appropriate DR for the current conditions. The obtained results show that the proposed approach achieves better results than those obtained when only a single DR is selected and used for all problem instances.

Automated summary

Dispatching rules are efficient tools for creating schedules, but manually designing rules for all possible conditions is impractical. Research has focused on automatic design using genetic programming, but evolving rules multiple times may be needed for optimal results. A selection procedure based on problem features has shown to outperform selecting a single rule for all instances.