Effective reinforcement learning-based dynamic flexible job shop scheduling using two-stage dispatching

Deep Reinforcement Learning (DRL) has been recognized as a promising means for solving the Dynamic Flexible Job Shop Scheduling Problem (DFJSP), where involved jobs have both distinct start time and due dates. However, due to the improper DRL modeling of scheduling components, it is hard to guarantee the quality (e.g., makespan, resource utilization) of job-to-machine dispatching solutions for DFJSP. This is mainly because (i) most existing DRL-based methods design actions as composite rules by combining both the processes of operation sequencing and machine assignment together, which will inevitably limit their adaptability to ever-changing scheduling scenarios; and (ii) without considering knowledge sharing among DRL network nodes, the learned policy networks with bounded sizes cannot be applied to complex large-scale scheduling problems. To address this problem, this paper introduces a novel DRL-based two-stage dispatching method that can effectively solve the DFJSP to achieve scheduling solutions of better quality. In our approach, the first stage utilizes a graph neural network-based policy network to facilitate optimal operation selection at each dispatching point. Since the policy network is size-agnostic and can share knowledge among DRL network nodes through graph embedding, it can handle DFJSP instances of varying scales. For the second stage, by decoupling the dependencies between operations and machines, we propose an effective machine selection heuristic that can derive more dispatching rules to improve the adaptability of DRL to various complex dynamic scheduling scenarios. Comprehensive experimental results demonstrate the superiority of our approach over state-of-the-art methods from both the perspective of scheduling solution quality and the adaptability of learned DRL models.