Improving job shop dispatching rules via terminal weighting and adaptive mutation in genetic programming
Michael Waltermier Riley, Yi Mei, Mengjie Zhang · 2016
Automatic design of dispatching rules with Genetic Programming (GP) in job shop scheduling has become more prevalent in recent years. When evolving dispatching rules, choosing a proper terminal set is an important issue. There are a large number of attributes in the job shop that can be taken into account as terminals. However, not all of them are useful to be included. It is not a trivial task to identify the most important attributes out of the entire attribute pool. On the other hand, including all the attributes in the terminal set leads to a huge search space for GP, and makes it hard to find the promising regions of the search space. In this paper, we first demonstrate the differences in importance of attributes by frequency analysis. Then, we propose a terminal weighting algorithm to learn the importance of the terminals on-the-fly, and an adaptive mutation scheme to guide the search to concentrate on the more important terminals. The experimental studies show that the proposed algorithm outperformed its counterpart without terminal weighting and adaptive mutation, in the tested dynamic job shop scheduling, while optimising the mean weighted tardiness. This verifies that focusing on the important terminals will help to search inside more promising regions and lead to better solutions.