# Self-Labeling the Job Shop Scheduling Problem

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 59 references that are in the map.
- First posted on arXiv 22 Jan 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Clustering for Unsupervised Learning of Visual Features](https://mlsanity.com/paper/1807.05520/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Self-supervised Learning: Generative or Contrastive](https://mlsanity.com/paper/2006.08218/) (2020)
- [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)
- [Self-labelling via simultaneous clustering and representation learning](https://mlsanity.com/paper/1911.05371/) (2019)
- [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)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method](https://mlsanity.com/paper/2110.06365/) (2021)
- [Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling](https://mlsanity.com/paper/2211.10936/) (2022)
- [Learning to Control Local Search for Combinatorial Optimization](https://mlsanity.com/paper/2206.13181/) (2022)
- [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 generalize Dispatching rules on the Job Shop Scheduling](https://mlsanity.com/paper/2206.04423/) (2022)
- [A Simple Decentralized Cross-Entropy Method](https://mlsanity.com/paper/2212.08235/) (2022)
- [Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization](https://mlsanity.com/paper/2202.05423/) (2022)
- [Learning the Quality of Machine Permutations in Job Shop Scheduling](https://mlsanity.com/paper/2207.03244/) (2022)

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

- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [OptimAI: Optimization from Natural Language Using LLM-Powered AI Agents](https://mlsanity.com/paper/2504.16918/) (2025)
- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [Starjob: Dataset for LLM-Driven Job Shop Scheduling](https://mlsanity.com/paper/2503.01877/) (2025)
- [LLMs can Schedule](https://mlsanity.com/paper/2408.06993/) (2024)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [GraphXForm: Graph transformer for computer-aided molecular design](https://mlsanity.com/paper/2411.01667/) (2024)
- [Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization](https://mlsanity.com/paper/2407.17206/) (2024)
- [Offline reinforcement learning for job-shop scheduling problems](https://mlsanity.com/paper/2410.15714/) (2024)
- [Learning to Solve the Min-Max Mixed-Shelves Picker-Routing Problem via Hierarchical and Parallel Decoding](https://mlsanity.com/paper/2502.10233/) (2025)
- [Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem](https://mlsanity.com/paper/2409.02697/) (2024)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)
- [Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions](https://mlsanity.com/paper/2509.10303/) (2025)
- [Multi-Action Self-Improvement for Neural Combinatorial Optimization](https://mlsanity.com/paper/2510.12273/) (2025)
- [Variational Approach for Job Shop Scheduling](https://mlsanity.com/paper/2602.00408/) (2026)
- [Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework](https://mlsanity.com/paper/2605.18454/) (2026)
- [GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization](https://mlsanity.com/paper/2605.19119/) (2026)
- [Self-Improvement Imitation with Biologically Guided Search for Protein Design Under Oracle Budgets](https://mlsanity.com/paper/2605.26690/) (2026)
- [DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents](https://mlsanity.com/paper/2605.27566/) (2026)
- [Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement](https://mlsanity.com/paper/2608.24859/) (2026)
- [Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data](https://mlsanity.com/paper/2608.29690/) (2026)

## Abstract (arXiv)

This work proposes a self-supervised training strategy designed for combinatorial problems. An obstacle in applying supervised paradigms to such problems is the need for costly target solutions often produced with exact solvers. Inspired by semi- and self-supervised learning, we show that generative models can be trained by sampling multiple solutions and using the best one according to the problem objective as a pseudo-label. In this way, we iteratively improve the model generation capability by relying only on its self-supervision, eliminating the need for optimality information. We validate this Self-Labeling Improvement Method (SLIM) on the Job Shop Scheduling (JSP), a complex combinatorial problem that is receiving much attention from the neural combinatorial community. We propose a generative model based on the well-known Pointer Network and train it with SLIM. Experiments on popular benchmarks demonstrate the potential of this approach as the resulting models outperform constructive heuristics and state-of-the-art learning proposals for the JSP. Lastly, we prove the robustness of SLIM to various parameters and its generality by applying it to the Traveling Salesman Problem.