A Spatiotemporal Graph Neural Network Based Deep Reinforcement Learning Method for Online Distributed Job-Shop Scheduling Problem

The distributed shop scheduling problem is a hotspot in the shop scheduling field. Online scheduling requires making prompt decisions in response to environmental changes during ongoing production. This paper studies an Online Distributed Job-shop Scheduling Problem (ODJSP) with random job arrivals and machine breakdowns. The spatiotemporal Graph Neural Network (GNN) and Deep Reinforcement Learning (DRL) method are integrated, introducing a novel framework for efficiently solving online scheduling problems. First, a dynamic disjunctive graph with an adaptable topology is introduced. Building upon this foundation, a Markov Decision Process model is developed to formulate the ODJSP. A novel time-window-based state observation mechanism is designed, enhancing the agent's decision efficiency by curtailing redundant input information. Additionally, the Graph Convolutional Recurrent Network is employed to extract features during decision process, enabling effective feature capture across both spatial and temporal domains. The features across the temporal domain are crucial for online scheduling problems but have rarely been considered in existing research. Moreover, Proximal Policy Optimization is integrated with an actor-critic framework to train the decision agent. Comparative experiments are conducted across 972 simulation environments with different configurations. The comparison among 29 composite Priority Dispatch Rules, 3 GNN-based and Multi-Layer Perceptron-based DRL methods, and Deep Q-learning Network-based and Gene Expression Programming-based online scheduling methods demonstrates the effectiveness, stability, generalization, and real-time performance of the proposed method. The case study from a marine opto-mechanical structural component manufacturing company validates its practical value.