Genetic Programming with Multi-tree Representation for Dynamic Flexible Job Shop Scheduling

Flexible job shop scheduling (FJSS) can be regarded as an optimization problem in production scheduling that captures practical and challenging issues in real-world scheduling tasks such as order picking in manufacturing and cloud computing. Given a set of machines and jobs, FJSS aims to determine which machine to process a particular job (by routing rule) and which job will be chosen to process next by a particular machine (by sequencing rule). In addition, dynamic changes are unavoidable in the real-world applications. These features lead to difficulties in real-time scheduling. Genetic programming (GP) is well-known for the flexibility of its representation and tree-based GP is widely and typically used to evolve priority functions for different decisions. However, a key issue for the tree-based representation is how it can capture both the routing and sequencing rules simultaneously. To address this issue, we proposed to use multi-tree GP (MTGP) to evolve both routing and sequencing rules together. In order to enhance the performance of MTGP algorithm, a novel tree swapping crossover operator is proposed and embedded into MTGP. The results suggest that the multi-tree representation can achieve much better performance with smaller rules and less training time than cooperative co-evolution for GP in solving dynamic FJSS problems. Furthermore, the proposed tree swapping crossover operator can greatly improve the performance of MTGP.