# An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming

**Authors:** Pierre Tassel, Martin Gebser, Konstantin Schekotihin  
**arXiv:** [2306.05747](https://arxiv.org/abs/2306.05747)  
**Date:** 2023-06-09  
**Summary page:** https://www.summarizepaper.com/en/paper/2306.05747v1/

## Key points

- End-to-end approach for solving the Job-Shop Scheduling Problem (JSSP) using Constraint Programming (CP) and Reinforcement Learning (RL)
- CP solvers struggle to scale to larger problems
- Proposed neural network architecture and training algorithm that only require a generic CP encoding and small instances
- RL agent learns a Priority Dispatching Rule (PDR) capable of generalizing well to large instances
- Evaluated on seven JSSP datasets, finds higher-quality solutions for very large instances compared to static PDRs and CP solvers within the same time limit
- Key contributions: introducing an RL environment based on a generic CP model, developing an efficient neural network architecture, proposing a novel training algorithm utilizing the CP nature by using a CP solver to generate training data
- Provides a promising solution for scalability issues in solving scheduling problems like JSSP by combining CP and RL

## Summary

This paper introduces an end-to-end approach for solving the Job-Shop Scheduling Problem (JSSP) using a combination of Constraint Programming (CP) and Reinforcement Learning (RL). CP solvers are effective for finding optimal or near-optimal solutions for small instances but struggle to scale to larger problems. To address this limitation, the authors propose a novel neural network architecture and training algorithm that only require a generic CP encoding of the scheduling problem and a set of small instances. The proposed approach leverages existing CP solvers to train an RL agent that learns a Priority Dispatching Rule (PDR) capable of generalizing well to large instances from separate datasets. This method is evaluated on seven JSSP datasets from the literature and demonstrates its ability to find higher-quality solutions for very large instances compared to static PDRs and CP solvers within the same time limit. The key contributions of this paper include introducing an RL environment based on a generic CP model of JSSP that enables fast propagation of constraints even for large instances; developing an efficient neural network architecture capable of extracting features directly from raw variables; and proposing a novel training algorithm that utilizes the CP nature by using a CP solver to generate training data. This end-to-end approach combining CP and RL provides a promising solution for addressing scalability issues in solving scheduling problems like JSSP. It leverages existing CP solvers and trains an RL agent with a generic encoding and small instance datasets, achieving higher-quality solutions for large instances compared to traditional approaches within similar time limits.