Deep reinforcement learning with dynamic graph pruning for scalable flexible job shop scheduling
提出一种动态图强化学习框架，通过剪枝无关节点和边来高效求解大规模柔性作业车间调度问题，在缩短计算时间的同时保持调度质量，适合工业应用。
The Flexible Job Shop Scheduling Problem (FJSP) is an NP-hard optimization challenge with significant industrial applications, especially for large-scale instances. Traditional approaches, such as Priority Dispatching Rules (PDRs), often struggle with time-intensive design processes and suboptimal performance as problem size increases. This paper proposes a scalable, dynamic graph-based reinforcement learning (DGRL) framework to efficiently solve large-scale FJSPs. By modeling FJSPs as a dynamic graph and pruning irrelevant nodes and edges, the scheduling task is reformulated as a Markov Decision Process (MDP). To capture complex task dependencies and machine constraints, we employ Heterogeneous Graph Neural Networks (HGNNs) for feature extraction, combined with reinforcement learning for policy optimization. Furthermore, a multi-action selection strategy is introduced to enhance computational efficiency, enabling faster decision-making without compromising solution quality. Experimental results demonstrate that the proposed framework improves the performance of state-of-the-art DRL methods and outperforms traditional heuristics and exact solvers, achieving competitive makespan performance with significantly reduced computational time. Overall, this approach provides a practical and scalable solution for real-world large-scale FJSPs.