Toward Evolving Dispatching Rules With Flow Control Operations By Grammar-Guided Linear Genetic Programming

Linear genetic programming (LGP) has been successfully applied to dynamic job shop scheduling (DJSS) to automatically evolve dispatching rules. Flow control operations are crucial in concisely describing complex knowledge of dispatching rules, such as different dispatching rules in different conditions. However, existing LGP methods for DJSS have not fully considered the use of flow control operations. They simply included flow control operations in their primitive set, which inevitably leads to a huge number of redundant and obscure solutions in LGP search spaces. To move one step toward evolving effective and interpretable dispatching rules, this paper explicitly considers the characteristics of flow control operations via grammar-guided linear genetic programming and focuses on IF operations as a starting point. Specifically, this paper designs a new set of normalized terminals to improve the interpretability of IF operations and proposes three restrictions by grammar rules on the usage of IF operations: specifying the available inputs, the maximum number, and the possible locations of IF operations. The experiment results verify that the proposed method can achieve significantly better test performance than state-of-the-art LGP methods and improves interpretability by IF-included dispatching rules. Further investigation confirms that the explicit introduction of IF operations helps effectively evolve different dispatching rules according to their decision situations.