A novel feature selection for evolving compact dispatching rules using genetic programming for dynamic job shop scheduling

Because of advances in computational power and machine learning algorithms, the automated design of scheduling rules using Genetic Programming (GP) is successfully applied to solve dynamic job shop scheduling problems. Although GP-evolved rules usually outperform dispatching rules reported in the literature, intensive computational costs and rule interpretability persist as important limitations. Furthermore, the importance of features in the terminal set varies greatly among scenarios. The inclusion of irrelevant features broadens the search space. Therefore, proper selection of features is necessary to increase the convergence speed and to improve rule understandability using fewer features. In this paper, we propose a new representation of the GP rules that abstracts the importance of each terminal. Moreover, an adaptive feature selection mechanism is developed to estimate terminals' weights from earlier generations in restricting the search space of the current generation. The proposed approach is compared with three GP algorithms from the literature and 30 human-made rules from the literature under different job shop configurations and scheduling objectives, including total weighted tardiness, mean tardiness, and mean flow time. Experimentally obtained results demonstrate that the proposed approach outperforms methods from the literature in generating more interpretable rules in a shorter computational time without sacrificing solution quality.

Automated summary

Thanks to advances in computational power and machine learning algorithms, Genetic Programming (GP) can be used to automatically design scheduling rules for dynamic job shop scheduling problems. However, the computational costs and interpretability of the rules remain significant limitations. In this paper, a new representation of GP rules and an adaptive feature selection mechanism are proposed to improve solution quality by limiting the search space and generating more interpretable rules.