关键词: 柔性作业车间调度, 图神经网络, 强化学习

Abstract: The flexible job shop scheduling problem (FJSP), characterized by its NP-hard nature, complex resource constraints, and strong coupling of operations, presents significant challenges in large-scale instances in terms of both solution quality and computational efficiency. Traditional heuristic methods often suffer from limited scalability and poor generalization. To address these limitations, this paper proposes the SMG-DRL scheduling framework, which integrates graph neural networks (GNNs) with deep reinforcement learning (DRL), and incorporates three key designs: state load awareness, mask-guided action selection, and graph structural enhancement. Specifically, SMG-DRL embeds both global and local state features via load-aware mechanisms, improves action selection efficiency through a masking strategy, and utilizes sparse graph modeling combined with graph isomorphism networks (GIN) to extract structural features and reduce graph density. Experimental results on the Brandimarte benchmark dataset demonstrate that SMG-DRL achieves approximately 42% reduction in average relative error (Gap) compared to three classic dispatching rules (SPT, MWKR, and LWKR), with the latter yielding an average Gap of 35.55%, while the proposed framework achieves 20.55% on the 10×5 and 20×10 training instances. Moreover, compared with the DRL-based methods proposed by Zhang and Lei, SMG-DRL exhibits superior performance in both Gap levels and solution stability, reflecting stronger convergence and robustness. In terms of computational efficiency, SMG-DRL reduces the average solving time from 978 seconds (OR-Tools) to approximately 3 seconds, achieving a nearly 300-fold speed-up. Furthermore, on large-scale instances (30×10 and 40×10), the framework maintains low Gap values between 6.23% and 8.76%, showcasing its excellent scalability and generalization capability.

Key words: flexible work vehicle workshop scheduling, graph neural network, reinforcement learning