A Deep Reinforcement Learning (DRL)-Based Transformer Method for Solving the Open Shop Scheduling Problem
Summary
Presents a Transformer-based scheduling policy trained with reinforcement learning for the open shop scheduling problem, showing that a model trained on small instances can generalize to much larger problems and compete with classical dispatching heuristics.
View Cached Full Text
Cached at: 06/15/26, 09:08 AM
# A Deep Reinforcement Learning (DRL)-Based Transformer Method for Solving the Open Shop Scheduling Problem Source: [https://arxiv.org/abs/2606.13682](https://arxiv.org/abs/2606.13682) [View PDF](https://arxiv.org/pdf/2606.13682) > Abstract:The open shop scheduling problem \(OSSP\) arises in many industrial and service settings but remains computationally challenging as the number of jobs and machines increases\. While exact methods quickly become intractable, classical dispatching rules and metaheuristics may require substantial tuning to maintain solution quality at large scales\. This study develops a Transformer\-based scheduling policy for OSSP using an encoder\-decoder architecture with multi\-head attention\. The model is trained on Taillard benchmark instances \(4x4, 5x5, 7x7, and 10x10\) using only the processing\-time matrix as input and produces feasible schedules with makespans typically within 15\-30% of best\-known values\. To evaluate scalability, the trained policy is applied without retraining to randomly generated instances from 40x40 to 100x100 and compared against classical dispatching heuristics, including SPT, LPT, MWKR, and EST\. Across these large instances, the Transformer achieved average gaps of 12\.89\-15\.12% relative to a standard lower bound\. Compared with EST, the Transformer remained competitive, typically within a modest margin, while substantially outperforming SPT and LPT\. These results indicate that a Transformer policy trained on small OSSP instances can generalize to substantially larger problems and provide a feature\-light, learning\-based alternative to classical dispatching rules\. ## Submission history From: Faezeh Ardali \[[view email](https://arxiv.org/show-email/a1cde39c/2606.13682)\] **\[v1\]**Wed, 25 Mar 2026 15:19:19 UTC \(496 KB\)
Similar Articles
Towards Scalable Multi-Task Reinforcement Learning with Large Decision Models
This paper introduces LDM-v0, a large decision model trained offline on trajectories from thousands of diverse reinforcement learning environments, demonstrating that a single transformer policy can match the performance of task-specific policies across robotics, autonomous driving, inventory management, cybersecurity, trading, and video games.
Agentic Transformers Provably Learn to Search via Reinforcement Learning
This paper theoretically studies how transformer-based policies acquire search capabilities from reinforcement learning training dynamics in a stochastic tree environment. It shows that a two-head transformer can implement depth-first search and that this mechanism emerges naturally from sparse reward signals under a depth-wise curriculum.
Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning
Researchers from the University of Amsterdam propose a tabular reinforcement learning approach to the Metro Network Expansion Problem, showing it achieves comparable performance to Deep RL while reducing training episodes by 18x and carbon emissions by 12x on average. The method also incorporates social equity criteria and is evaluated on real-world metro networks in Xi'an and Amsterdam.
MechRL: Reinforcement Learning Agents Perform Circuit Discovery for Mechanistic Interpretability
Proposes MechRL, a reinforcement learning approach to automate circuit discovery in transformer language models. A PPO agent trained on multiple tasks discovers attention head circuits that match known canonical circuits and generalizes to a held-out task.
SCALE: Scalable Cross-Attention Learning with Extrapolation for Agentic Workflow Scheduling
This paper proposes SCALE, a deep reinforcement learning scheduler for agentic LLM workflow DAGs that generalizes to unseen cluster sizes using cross-attention and structured representation regularization, reducing response time without retraining.