Flexible Job Shop Scheduling Problem with Job Insertions Based on Graph Neural Networks and Deep Reinforcement Learning

The flexible job shop scheduling problem with job insertions (FJSP-JI) poses significant challenges in real-time industrial environments, where minimizing the maximum completion time (makespan) is critical. To address this, we propose a novel approach that combines heterogeneous graph neural networks (HGNN) and deep reinforcement learning (DRL). A heterogeneous graph is designed to model the complex relationships between machines and operations, capturing both topological and temporal dependencies. The joint decision of operation selection and machine assignment is formulated as a Markov decision process (MDP) and optimized via proximal policy optimization (PPO). Experiments demonstrate that our method has a smaller makespan in addressing the dynamic challenge compared to the classical prioritized scheduling rule. Furthermore, the algorithm exhibits strong generalization capabilities, achieving comparable efficiency on large-scale instances without additional training.