Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning
Authors: Wen Song; Xinyang Chen; Qiqiang Li; Zhiguang Cao
Abstract:
Scheduling problems are ubiquitous in real-world manufacturing. Flexible Job-shop Scheduling Problem (FJSP) is of particular interest, since it allows a job to be processed on one of its compatible machine, which offers more flexibility than the standard Job-shop Scheduling Problem (JSP). In reality, complex scheduling problems are often solved by priority dispatching rules (PDR), which is fast, intuitive, and easy to implement. However, the solution quality delivered by traditional manual PDRs is often poor. Recently, deep reinforcement learning (DRL) has been applied to learn PDRs for solving scheduling problems. However, the existing works face challenges in dealing with flexibility, which allows an operation to be scheduled on one out of multiple machines and is often required in practice. Such one-to-many relationship brings additional complexity in both decision making and state representation. This article considers the well-known FJSP, and addresses these issues by proposing a novel DRL method to learn high-quality PDRs end to end. The DRL agent takes a scheduling state as input, and outputs an action where the operation selection and the machine assignment are combined as a composite decision. Moreover, based on a novel heterogeneous graph representation of scheduling states, a heterogeneous-graph-neural-network-based architecture is proposed to capture complex relationships among operations and machines. Experiments show that the proposed method outperforms traditional PDRs and is computationally efficient, even on instances of larger scales and different properties unseen in training.
