Learning to Solve Job Shop Scheduling under Uncertainty
This addresses robust scheduling for manufacturing or logistics under uncertain task durations, but appears incremental as it builds on existing DRL and GNN techniques.
The paper tackles the Job-Shop Scheduling Problem under uncertainty by introducing a Deep Reinforcement Learning approach to generate robust schedules that minimize average makespan, with the Wheatley method integrating Graph Neural Networks and DRL made publicly available.
Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem where tasks need to be scheduled on machines in order to minimize criteria such as makespan or delay. To address more realistic scenarios, we associate a probability distribution with the duration of each task. Our objective is to generate a robust schedule, i.e. that minimizes the average makespan. This paper introduces a new approach that leverages Deep Reinforcement Learning (DRL) techniques to search for robust solutions, emphasizing JSSPs with uncertain durations. Key contributions of this research include: (1) advancements in DRL applications to JSSPs, enhancing generalization and scalability, (2) a novel method for addressing JSSPs with uncertain durations. The Wheatley approach, which integrates Graph Neural Networks (GNNs) and DRL, is made publicly available for further research and applications.