A Search Strategy With Graph Attention Networks and Neighborhood Search Features for Dynamic Flexible Job Shop Scheduling

doi:10.1109/TSMC.2025.3649526

A Search Strategy With Graph Attention Networks and Neighborhood Search Features for Dynamic Flexible Job Shop Scheduling

2026-01-14

0

PRE

AI

DOI：10.1109/TSMC.2025.3649526

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Graph attention mechanism

graph residual network

Monte Carlo tree search (MCTS)

neighborhood search

reinforcement learning (RL)

A Search Strategy With Graph Attention Networks and Neighborhood Search Features for Dynamic Flexible Job Shop Scheduling

Abstract

Journal

Organization