A New Representation in Genetic Programming for Evolving Dispatching Rules for Dynamic Flexible Job Shop Scheduling.

Dynamic flexible job shop scheduling (DFJSS) is a very important problem with a wide range of real-world applications such as cloud computing and manufacturing. In DFJSS, it is critical to make two kinds of real-time decisions (i.e. the routing decision that assigns machine to each job and the sequencing decision that prioritises the jobs in a machine’s queue) effectively in the dynamic environment with unpredicted events such as new job arrivals and machine breakdowns. Dispatching rule is an ideal technique for this purpose. In DFJSS, one has to design a routing rule and a sequencing rule for making the two kinds of decisions. Manually designing these rules is time consuming and requires human expertise which is not always available. Genetic programming (GP) has been applied to automatically evolve more effective rules than the manually designed ones. In GP for DFJSS, different features in the terminal set have different contributions to the decision making. However, the current GP approaches cannot perfectly find proper combinations between the features in accordance with their contributions. In this paper, we propose a new representation for GP that better considers the different contributions of different features and combines them in a sophisticated way, thus to evolve more effective rules. The results show that the proposed GP approach can achieve significantly better performance than the baseline GP in a range of job shop scenarios.