A Search Strategy With Graph Attention Networks and Neighborhood Search Features for Dynamic Flexible Job Shop Scheduling
针对动态柔性作业车间调度问题，提出一种结合图神经网络和邻域搜索特征的蒙特卡洛树搜索算法，在铝型材智能制造系统中实时生成高质量重调度方案，实验表明其计算效率和方案质量优于基线算法。
Addressing the dynamic flexible job shop scheduling (DFJSS) problem to generate a high-quality rescheduling scheme has gained increasing significance in various applications in recent years, such as the intelligent manufacturing system for aluminum profiles. In the intelligent manufacturing system for aluminum profiles, random events such as machine faults and variable processing times significantly affect production completion times. However, existing methods for solving DFJSS face challenges in generating high-quality rescheduling schemes in real time. To address these issues, a search strategy that combines graph neural networks (GNNs) and neighborhood search features is employed in the Monte Carlo tree search (MCTS) algorithm (GNS-MCTS) for real-time solving of the DFJSS. The search strategy in the GNS-MCTS aims to build a model that analyzes the scheduling disjunctive graph and predicts the searching probability, guiding the MCTS to important locations in the solution space rather than searching unimportant areas and wasting computing time. Specifically, the search strategy of GNS-MCTS incorporates encoders that fuse neighborhood search features and graph embedding vectors (GEVs) to improve the quality of the searching probability and make decisions about optimizing the scheduling disjunctive graph by breaking low-importance node pairs and reallocating low-importance nodes to other machines. Experimental results indicate that GNS-MCTS surpasses baseline algorithms across various problem sizes and real-time constraints, significantly enhancing computational efficiency and solution quality for the DFJSS. Further ablation studies and analysis reveal the impact of neighborhood search features on the enhancement of the learning-based search strategy when combined with neighborhood search for real-time DFJSS solutions.