# Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem

arXiv: https://arxiv.org/abs/2403.09249 · HTML: https://mlsanity.com/paper/2403.09249/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL for energy, networks and operations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 23 of its 52 references that are in the map.
- First posted on arXiv 14 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL for energy, networks and operations](https://mlsanity.com/deeprl/rl-for-energy-networks-and-operations/)

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Distilling Policy Distillation](https://mlsanity.com/paper/1902.02186/) (2019)
- [ABC-CNN: An Attention Based Convolutional Neural Network for Visual Question Answering](https://mlsanity.com/paper/1511.05960/) (2015)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning](https://mlsanity.com/paper/2305.05119/) (2023)
- [Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem](https://mlsanity.com/paper/2309.15517/) (2023)
- [An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming](https://mlsanity.com/paper/2306.05747/) (2023)
- [Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning](https://mlsanity.com/paper/2210.17178/) (2022)
- [Learning To Dive In Branch And Bound](https://mlsanity.com/paper/2301.09943/) (2023)
- [Two-Stage Learning For the Flexible Job Shop Scheduling Problem](https://mlsanity.com/paper/2301.09703/) (2023)
- [Google vs IBM: A Constraint Solving Challenge on the Job-Shop Scheduling Problem](https://mlsanity.com/paper/1909.08247/) (2019)

## Built on by (most cited first, 4 of 4)

- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [Offline reinforcement learning for job-shop scheduling problems](https://mlsanity.com/paper/2410.15714/) (2024)
- [REMoH: A Reflective Evolution of Multi-objective Heuristics approach via Large Language Models](https://mlsanity.com/paper/2506.07759/) (2025)
- [Solving Integrated Process Planning and Scheduling Problem via Graph Neural Network Based Deep Reinforcement Learning](https://mlsanity.com/paper/2409.00968/) (2024)

## Abstract (arXiv)

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, DRL approaches often fail to fully harness the strengths of existing techniques such as exact methods or constraint programming (CP), which can excel at finding optimal or near-optimal solutions for smaller instances. This paper aims to integrate 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.