Solving the flexible job-shop scheduling problem through an enhanced deep reinforcement learning approach
Preprint
Abstract
In scheduling problems common in the industry and various real-world scenarios, responding in real-time to disruptive events is essential. Recent methods propose the use of deep reinforcement learning (DRL) to learn policies capable of generating solutions under this constraint. The objective of this paper is to introduce a new DRL method for solving the flexible job-shop scheduling problem, particularly for large instances. The approach is based on the use of heterogeneous graph neural networks to a more informative graph representation of the problem. This novel modeling of the problem enhances the policy's ability to capture state information and improve its decision-making capacity. Additionally, we introduce two novel approaches to enhance the performance of the DRL approach: the first involves generating a diverse set of scheduling policies, while the second combines DRL with dispatching rules (DRs) constraining the action space. Experimental results on two public benchmarks show that our approach outperforms DRs and achieves superior results compared to three state-of-the-art DRL methods, particularly for large instances.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problemComputers & Industrial Engineering, 2022
- Dynamic multi-objective scheduling for flexible job shop by deep reinforcement learningComputers & Industrial Engineering, 2021
- A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problemComputers & Industrial Engineering, 2020
- Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learningApplied Soft Computing, 2020
- Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problemComputers & Industrial Engineering, 2020
- Graph neural networks: A review of methods and applicationsAI Open, 2020
- A research survey: review of AI solution strategies of job shop scheduling problemJournal of Intelligent Manufacturing, 2013
- Job shop scheduling techniques in semiconductor manufacturingThe International Journal of Advanced Manufacturing Technology, 2004
- Tabu search for the job-shop scheduling problem with multi-purpose machinesOR Spectrum, 1994
- Routing and scheduling in a flexible job shop by tabu searchAnnals of Operations Research, 1993