Leveraging constraint programming in a deep learning approach for dynamically solving the flexible job-shop scheduling problem
Imanol Echeverria, Maialen Murua, Roberto Santana
Abstract
Recent advancements in the flexible job-shop scheduling problem (FJSSP) are primarily based on deep reinforcement learning (DRL) due to its ability to generate high-quality, real-time solutions. However, many DRL approaches struggle with large action spaces, making the search for optimal solutions computationally intensive and impacting performance. Moreover, established techniques like exact methods and constraint programming (CP) often achieve better results for smaller instances. This paper aims to fully harness the strengths of these existing techniques by integrating CP within a deep learning (DL)-based methodology, leveraging the benefits of both. In this paper, we introduce a method that involves training a DL model using optimal solutions generated by CP, ensuring the model learns from high-quality data, thereby eliminating the need for the extensive exploration typical in DRL and enhancing overall performance. Further, we integrate CP into our DL framework to jointly construct solutions, utilizing DL for the initial complex stages and transitioning to CP for optimal resolution as the problem is simplified. Our hybrid approach has been extensively tested on three public FJSSP benchmarks, demonstrating superior performance over five state-of-the-art DRL approaches and a widely-used CP solver. Additionally, with the objective of exploring the application to other combinatorial optimization problems, promising preliminary results are presented on applying our hybrid approach to the traveling salesman problem, combining an exact method with a well-known DRL method. • Real-time approach for Flexible Job Shop Scheduling via Behavioral Cloning. • Joint solution strategy, hybridizing constraint programming and deep learning. • Outperforms five DRL methods and a renowned solver across five datasets. • Extended to the traveling salesman problem with promising results.