A Graph-Based Reinforcement Learning Method for Flexible Job Shop Scheduling with Sequence Flexibility

The flexible job shop scheduling problem with sequence flexibility (FJSPSF) has a wide range of applications in various industries, including printing and semiconductor manufacturing. To effectively address the FJSPSF, we introduce a novel end-to-end deep reinforcement learning (DRL) framework. It is the first DRL method designed specifically to handle the challenges of sequence flexibility in this domain. Firstly, to capture the complex topological structure, which is given in the form of a directed acyclic graph (DAG), we design a DAG-based heterogeneous graph neural network (DAHGNN) to represent the shop state and obtain a high-quality state embedding. Based on the heterogeneous graph representation of scheduling states, the Proximal Policy Optimization (PPO) algorithm is adopted to learn an effective policy. Then, we propose a new Markov decision process (MDP) model for this problem, in which the state features are better designed and the action space is specially constructed for the characteristics of the FJSPSF. Finally, we conduct extensive experiments on two public datasets (DAFJS and YFJS), and the results demonstrate that the policy model outperforms all the priority dispatching rules (PDRs). Furthermore, it achieves solution qualities close to state-of-the-art metaheuristic and exact methods, while offering significantly faster solving speeds.