# An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 64 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Online Mixed-Integer Optimization in Milliseconds](https://mlsanity.com/paper/1907.02206/) (2019)
- [The Voice of Optimization](https://mlsanity.com/paper/1812.09991/) (2018)
- [Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem](https://mlsanity.com/paper/1709.09972/) (2017)
- [A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs](https://mlsanity.com/paper/1912.08112/) (2019)
- [Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control](https://mlsanity.com/paper/2004.03736/) (2020)

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

- [Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions](https://mlsanity.com/paper/2310.03195/) (2023)
- [schlably: A Python Framework for Deep Reinforcement Learning Based Scheduling Experiments](https://mlsanity.com/paper/2301.04182/) (2023)
- [Deep Reinforcement Learning for Traveling Purchaser Problems](https://mlsanity.com/paper/2404.02476/) (2024)
- [Minimizing the Weighted Number of Tardy Jobs: Data-Driven Heuristic for Single-Machine Scheduling](https://mlsanity.com/paper/2508.13703/) (2025)
- [Neural Architecture Search for global multi-step Forecasting of Energy Production Time Series](https://mlsanity.com/paper/2511.00035/) (2025)
- [Reinforcement Learning in Operational Research: A Technical Review and Practical Roadmap](https://mlsanity.com/paper/2609.24750/) (2026)

## Abstract (arXiv)

There is a growing interest in integrating machine learning techniques and optimization to solve challenging optimization problems. In this work, we propose a deep reinforcement learning methodology for the job shop scheduling problem (JSSP). The aim is to build up a greedy-like heuristic able to learn on some distribution of JSSP instances, different in the number of jobs and machines. The need for fast scheduling methods is well known, and it arises in many areas, from transportation to healthcare. We model the JSSP as a Markov Decision Process and then we exploit the efficacy of reinforcement learning to solve the problem. We adopt an actor-critic scheme, where the action taken by the agent is influenced by policy considerations on the state-value function. The procedures are adapted to take into account the challenging nature of JSSP, where the state and the action space change not only for every instance but also after each decision. To tackle the variability in the number of jobs and operations in the input, we modeled the agent using two incident LSTM models, a special type of deep neural network. Experiments show the algorithm reaches good solutions in a short time, proving that is possible to generate new greedy heuristics just from learning-based methodologies. Benchmarks have been generated in comparison with the commercial solver CPLEX. As expected, the model can generalize, to some extent, to larger problems or instances originated by a different distribution from the one used in training.