Dynamic Job-Shop Scheduling Problems Using Graph Neural Network and Deep Reinforcement Learning

The job-shop scheduling problem (JSSP) is one of the best-known combinatorial optimization problems and is also an essential task in various sectors. In most real-world environments, scheduling is complex, stochastic, and dynamic, with inevitable uncertainties. Therefore, this article proposes a novel framework based on graph neural networks (GNNs) and deep reinforcement learning (DRL) to deal with the dynamic JSSP (DJSSP) with stochastic job arrivals and random machine breakdowns by minimizing the makespan. In the proposed framework, JSSP is formulated as a Markov decision process (MDP) and is associated with a disjunctive graph to encode the information of jobs and machines as nodes and arcs. We propose a GNN architecture to perform representation learning by transforming graph states into node embeddings. Then, the agent takes actions using a parameterized policy in terms of policy learning. Operations are used as actions, and an effective reward is well designed to guide the agent. We train our proposed method using proximal policy optimization (PPO), which helps minimize the loss function while ensuring that the deviation is relatively small. Extensive experiments show that the proposed method can achieve excellent results considering different criteria: efficiency, effectiveness, robustness, and generalizability. Once the proposed method is trained, it can directly schedule new JSSPs of different sizes and distributions in static benchmark tests, showing its excellent generalizability and effectiveness compared to another DRL-based method. Furthermore, the proposed method simultaneously maintains the win rate (a quantitative metric) and the scheduling score (a qualitative metric) when scheduling in dynamic environments.