Importance-Aware Genetic Programming for Automated Scheduling Heuristics Learning in Dynamic Flexible Job Shop Scheduling

Dynamic flexible job shop scheduling (DFJSS) is a critical and challenging problem in production scheduling such as order picking in the warehouse. Given a set of machines and a number of jobs with a sequence of operations, DFJSS aims to generate schedules for completing jobs to minimise total costs while reacting effectively to dynamic changes. Genetic programming, as a hyper-heuristic approach, has been widely used to learn scheduling heuristics for DFJSS automatically. A scheduling heuristic in DFJSS includes a routing rule for machine assignment and a sequencing rule for operation sequencing. However, existing studies assume that the routing and sequencing are equally important, which may not be true in real-world applications. This paper aims to propose an importance-aware GP algorithm for automated scheduling heuristics learning in DFJSS. Specifically, we first design a rule importance measure based on the fitness improvement achieved by the routing rule and the sequencing rule across generations. Then, we develop an adaptive resource allocation strategy to give more resources for learning the more important rules. The results show that the proposed importance-aware GP algorithm can learn significantly better scheduling heuristics than the compared algorithms. The effectiveness of the proposed algorithm is realised by the proposed strategies for detecting rule importance and allocating resources. Particularly, the routing rules play a more important role than the sequencing rules in the examined DFJSS scenarios.