# Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 34 references that are in the map.
- First posted on arXiv 12 Oct 2021.

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

- [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)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods](https://mlsanity.com/paper/1909.10461/) (2019)
- [Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems](https://mlsanity.com/paper/1911.10092/) (2019)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Lagrangian Duality for Constrained Deep Learning](https://mlsanity.com/paper/2001.09394/) (2020)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints](https://mlsanity.com/paper/1807.00028/) (2018)
- [Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach](https://mlsanity.com/paper/2009.12562/) (2020)
- [Learning Hard Optimization Problems: A Data Generation Perspective](https://mlsanity.com/paper/2106.02601/) (2021)
- [Human-Machine Collaborative Optimization via Apprenticeship Scheduling](https://mlsanity.com/paper/1805.04220/) (2018)

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

- [Self-Supervised Primal-Dual Learning for Constrained Optimization](https://mlsanity.com/paper/2208.09046/) (2022)
- [Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models](https://mlsanity.com/paper/2502.03607/) (2025)
- [Self-Labeling the Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.11849/) (2024)
- [Learning Constrained Optimization with Deep Augmented Lagrangian Methods](https://mlsanity.com/paper/2403.03454/) (2024)
- [Metric Learning to Accelerate Convergence of Operator Splitting Methods for Differentiable Parametric Programming](https://mlsanity.com/paper/2404.00882/) (2024)
- [Two-Stage Learning For the Flexible Job Shop Scheduling Problem](https://mlsanity.com/paper/2301.09703/) (2023)
- [Data-driven decision-focused surrogate modeling](https://mlsanity.com/paper/2308.12161/) (2023)
- [Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization](https://mlsanity.com/paper/2311.13087/) (2023)
- [Self-Supervised Learning of Iterative Solvers for Constrained Optimization](https://mlsanity.com/paper/2409.08066/) (2024)
- [PROPEL: Supervised and Reinforcement Learning for Large-Scale Supply Chain Planning](https://mlsanity.com/paper/2504.07383/) (2025)
- [Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks](https://mlsanity.com/paper/2307.04050/) (2023)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Self-supervised Equality Embedded Deep Lagrange Dual for Approximate Constrained Optimization](https://mlsanity.com/paper/2306.06674/) (2023)
- [Compact Optimality Verification for Optimization Proxies](https://mlsanity.com/paper/2405.21023/) (2024)
- [Learning to Optimize Job Shop Scheduling Under Structural Uncertainty](https://mlsanity.com/paper/2601.21389/) (2026)
- [DSevolve: Enabling Real-Time Adaptive Scheduling on Dynamic Flexible Job Shop with LLM-Evolved Heuristic Portfolios](https://mlsanity.com/paper/2603.27628/) (2026)
- [Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework](https://mlsanity.com/paper/2312.03413/) (2023)
- [Instance Configuration for Sustainable Job Shop Scheduling](https://mlsanity.com/paper/2409.18972/) (2024)
- [Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs](https://mlsanity.com/paper/2606.21440/) (2026)
- [Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data](https://mlsanity.com/paper/2608.29690/) (2026)

## Abstract (arXiv)

The Jobs shop Scheduling Problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization to guarantee solution feasibility.The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.