# Scalable Production Scheduling: Linear Complexity via Unified Homogeneous Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 18 references that are in the map.
- First posted on arXiv 26 Apr 2026.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [TorchRL: A data-driven decision-making library for PyTorch](https://mlsanity.com/paper/2306.00577/) (2023)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [A Reinforcement Learning Environment For Job-Shop Scheduling](https://mlsanity.com/paper/2104.03760/) (2021)
- [Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning](https://mlsanity.com/paper/2305.05119/) (2023)
- [Graph neural networks-based Scheduler for Production planning problems using Reinforcement Learning](https://mlsanity.com/paper/2009.03836/) (2020)
- [Enabling Homogeneous GNNs to Handle Heterogeneous Graphs via Relation Embedding](https://mlsanity.com/paper/2209.11414/) (2022)

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

- [Bridging the Sim-to-Real Gap in Reinforcement Learning-Based Industrial Dispatching through Execution Semantics](https://mlsanity.com/paper/2605.29078/) (2026)
- [Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling](https://mlsanity.com/paper/2609.28085/) (2026)
- [PORL: Pretrained Offline Reinforcement Learning for the Job Shop Scheduling Problem](https://mlsanity.com/paper/2609.30948/) (2026)

## Abstract (arXiv)

Efficiently solving the Job Shop Scheduling Problem in real-world industrial applications requires policies that are both computationally lean and topologically robust. While Reinforcement Learning has shown potential in automating dispatching rules, existing models often struggle with a scalability bottleneck caused by quadratic graph complexity or the architectural overhead of heterogeneous layers. We introduce a unified graph framework that employs feature-based homogenization to project distinct node roles into a shared latent space. This allows a standard homogeneous Graph Isomorphism Network to capture complex resource contention with linear complexity, ensuring low-latency inference for large-scale industrial applications. Our empirical results demonstrate that our framework achieves state-of-the-art performance while exhibiting consistent zero-shot generalization. We identify the job-to-machine ratio as the primary driver of policy effectiveness, rather than absolute problem size. Based on this, we propose a hypothesis of structural saturation, demonstrating that policies trained on critically congested instances (J ≈ M) learn scale-invariant resolution strategies. Agents trained at this saturation point internalize invariant conflict-resolution logic, allowing them to treat massive rectangular instances as a sequential concatenation of saturated sub-problems. This approach eliminates the need for expensive scale-specific retraining and prevents overfitting to statistical shortcuts, providing a robust and efficient pathway for deploying RL solutions in dynamic production environments.