Reproduce “An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming” on OpenResearch

About this paper

Pierre Tassel, Martin Gebser, Konstantin Schekotihin

This research develops an end-to-end Reinforcement Learning approach that directly integrates with Constraint Programming to solve Job-Shop Scheduling Problems. The method leverages a generic CP model as the RL environment and a hybrid training strategy to learn priority dispatching rules, consistently outperforming static heuristics and often state-of-the-art CP solvers on large instances while demonstrating strong generalization capabilities to unseen problem sizes.

Key insights

• Integrating a generic Constraint Programming (CP) model directly as the Reinforcement Learning (RL) environment eliminates the need for problem-specific simulations, extensive feature engineering, and handcrafted reward functions in scheduling problems.
• A size-agnostic neural network architecture combined with a hybrid training strategy (leveraging CP expert demonstrations and policy gradients) enables a learned policy to generalize effectively from small training instances to much larger, unseen instances across diverse datasets.
• The use of episodic rewards (makespan at completion) with expert feedback from a CP solver is sufficient for training, simplifying the reward design often problematic in RL for combinatorial optimization.

Summary by alphaXiv.