arXiv:2404.01308v1 Announce Type: new
Abstract: 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.
The Job-Shop Scheduling Problem (JSSP) is a complex optimization problem that is applicable in various industries and sectors. It involves scheduling tasks on machines, taking into consideration different criteria such as minimizing the makespan or delay. However, in real-world scenarios, the duration of tasks may not be certain and can be subject to variability.
This research introduces a new approach to tackle JSSPs with uncertain durations by leveraging Deep Reinforcement Learning (DRL) techniques. DRL has gained significant attention in recent years due to its ability to learn from experience and make decisions in complex environments. By associating a probability distribution with the duration of each task, the objective is to generate a robust schedule that minimizes the average makespan.
The key contribution of this research lies in the advancements it brings to the application of DRL to JSSPs. The use of DRL enhances generalization and scalability, making it possible to apply the approach to larger and more complex problem instances. Additionally, this research presents a novel method for addressing JSSPs with uncertain durations, which adds a new dimension to the existing literature on JSSP optimization.
The Wheatley approach, a combination of Graph Neural Networks (GNNs) and DRL, is introduced as the methodology for addressing JSSPs with uncertain durations. GNNs are specialized neural networks that can effectively model and represent complex relationships in graph-like structures. By integrating GNNs with DRL, the Wheatley approach offers a powerful tool for solving JSSPs with uncertain durations.
This research holds significant implications for multiple disciplines. From a computer science perspective, it introduces advancements in the application of DRL techniques to combinatorial optimization problems. The integration of GNNs and DRL opens up new possibilities for solving complex scheduling problems in various domains.
Moreover, from an operations research standpoint, the ability to address JSSPs with uncertain durations is a critical step towards more realistic and robust scheduling solutions. By considering the probability distribution of task durations, decision-makers can make informed and resilient schedules that can adapt to uncertainties in real-world scenarios. This research bridges the gap between theoretical research in JSSP optimization and practical implementation in dynamic environments.
In conclusion, this research demonstrates the potential of Deep Reinforcement Learning in addressing the Job-Shop Scheduling Problem with uncertain durations. By introducing the Wheatley approach that integrates Graph Neural Networks and DRL, the research advances the field by enhancing generalization, scalability, and the ability to handle variability in task durations. This multi-disciplinary approach has the potential to revolutionize scheduling practices in various industries and contribute to more robust and efficient operations.