A low-node-density disjunctive graph model for flexible job shop scheduling

Abstract

Designing Priority-Based Dispatching Rules (PDRs) to solve scheduling decision problems often leads to unbalanced resource allocation and can even cause deadlocks during the decision-making process. To handle dynamic changes more effectively, PDRs trained using Deep Reinforcement Learning (DRL) have been successfully applied. However, DRL training typically requires integrating large-scale graph structures, facing challenges such as slow convergence and limited search space. To mitigate these issues, we aim to reduce the node density of the graph structure, making the disjunctive graph model more sensitive to critical paths. In this study, we focus on the classic Flexible Job Shop Scheduling Problem (FJSP). We propose a structurally simple, low-node-density disjunctive graph model, then perform feature extraction using Graph Neural Networks (GNNs), and finally optimize convergence using the Migrating Birds Optimization (MBO)—an intelligent optimization algorithm proven effective for scheduling decision problems. Experiments demonstrate that the proposed disjunctive graph model significantly reduces computational complexity and achieves remarkable improvements in finding optimal solutions for scheduling problems. This success is attributed to the simple disjunctive graph model’s ability to extract latent constraint relationships more effectively.