A Deep Reinforcement Learning (DRL)-Based Transformer Method for Solving the Open Shop Scheduling Problem
Transformer-based DRL policy achieves 12.89-15.12% gap on large OSSP instances, generalizing from small training data.
Key Findings
Methodology
This work integrates a Transformer encoder-decoder architecture with Proximal Policy Optimization (PPO) reinforcement learning for OSSP. The model encodes each job-machine operation node using processing time matrices, employing multi-head self-attention to capture global dependencies. The decoder sequentially generates scheduling decisions by attending to encoded representations, selecting next operations and machines. During training, the Transformer acts as the policy network (actor), producing actions, while a separate Critic network estimates value functions. The training process involves sampling trajectories, computing rewards based on negative makespan, and updating the policy via PPO’s clipped objective. The approach is trained on small Taillard instances (4×4 to 10×10) and applied directly to larger, unseen instances (40×40 to 100×100), demonstrating strong generalization without retraining.
Key Results
- On Taillard benchmarks, the model produces feasible schedules with an average gap of 15% or less, with the gap decreasing from 28.8% at 7×7 to 15.59% at 20×20. In large-scale experiments, the policy maintains a stable average gap of 12.89%-15.12% relative to a workload lower bound, outperforming simple heuristics like SPT and LPT, and closely matching EST. The results confirm the model’s ability to generalize across instance sizes and complexities, providing high-quality solutions efficiently.
- The model’s transferability to large instances without retraining highlights its robustness. It captures global scheduling patterns effectively, reducing reliance on handcrafted rules. The experiments also show that the Transformer’s attention mechanism enables the model to understand complex relationships among operations, leading to improved solution quality in diverse scenarios.
- Furthermore, the approach significantly reduces tuning effort compared to traditional heuristics, offering a scalable, learning-based alternative suitable for real-world industrial applications where quick, reliable scheduling is critical.
Significance
This research advances the application of deep reinforcement learning in combinatorial optimization, specifically in complex, large-scale OSSP. By leveraging Transformer architectures, it overcomes limitations of previous methods that relied heavily on handcrafted features or limited attention mechanisms. The ability to generalize from small training instances to large, real-world problems marks a significant step toward autonomous, adaptive scheduling systems. Such systems can dynamically respond to changing production environments, reducing operational costs and increasing efficiency. The work also bridges the gap between theoretical AI models and practical industrial deployment, offering a scalable, data-driven solution that complements traditional optimization techniques.
Technical Contribution
The paper’s core contribution lies in pioneering the use of full Transformer architectures within a reinforcement learning framework for OSSP. It introduces a novel combination of multi-head attention with PPO, enabling end-to-end learning of scheduling policies based solely on processing time matrices. The model architecture simplifies feature engineering, enhances global dependency modeling, and achieves superior generalization. The training methodology, leveraging small instances, demonstrates effective transfer to larger problems, setting a new benchmark for learning-based scheduling. The approach also opens avenues for integrating more complex constraints and multi-objective optimization in future work.
Novelty
This is the first application of a complete Transformer encoder-decoder model for open shop scheduling, addressing the challenge of operation order flexibility. Unlike prior work using graph neural networks or single-head attention, this study employs multi-head attention to improve relational modeling. The minimal input requirement—processing time matrices—combined with successful transfer to large, unseen instances, distinguishes this work from existing methods. It demonstrates that attention mechanisms can effectively learn complex scheduling policies without explicit feature engineering, marking a significant innovation in the field.
Limitations
- The current model’s scalability is limited by the quadratic complexity of full self-attention, restricting application to very large instances (e.g., thousands of jobs/machines). Future work should explore sparse or hierarchical attention mechanisms.
- The training process is computationally intensive, requiring high-performance hardware, which may limit accessibility for some users.
- The model assumes static, deterministic processing times and does not account for dynamic or stochastic environments, which are common in real-world manufacturing settings. Incorporating online learning or adaptive mechanisms remains a future challenge.
Future Work
Future research will focus on developing scalable attention variants, such as sparse or local attention, to handle larger instances efficiently. Integrating dynamic data streams and real-time feedback will enable adaptive, online scheduling. Combining the Transformer-based approach with multi-objective optimization and constraint handling will broaden its industrial applicability. Additionally, exploring hybrid models that incorporate classical optimization techniques could further improve solution quality and robustness in complex, real-world scenarios.
AI Executive Summary
Scheduling in manufacturing and logistics is a fundamental challenge that directly impacts productivity and operational costs. Traditional algorithms, such as dispatching rules and metaheuristics, often struggle to scale efficiently while maintaining solution quality. Recent advances in artificial intelligence, particularly deep reinforcement learning, have opened new avenues for tackling these complex problems. This study introduces a novel Transformer-based reinforcement learning framework that learns effective scheduling policies solely from processing time matrices.
The core innovation lies in employing a full Transformer encoder-decoder architecture combined with the Proximal Policy Optimization algorithm. The encoder captures global relationships among job-machine operations through multi-head self-attention, while the decoder sequentially constructs feasible schedules by attending to encoded representations. During training on small Taillard instances, the model learns to produce schedules with makespans within 15% of the best-known solutions. Remarkably, without retraining, the policy generalizes to large, randomly generated instances up to 100×100, maintaining an average gap of around 13-15% relative to a workload lower bound.
This approach surpasses traditional heuristics like SPT and LPT and closely matches EST in large-scale scenarios. Its ability to generalize across instance sizes demonstrates the potential of attention-based models to revolutionize industrial scheduling. The lightweight input requirement and end-to-end learning make it suitable for real-time applications, reducing reliance on handcrafted rules and extensive parameter tuning. Future enhancements will focus on improving scalability, incorporating dynamic environment adaptation, and integrating multi-objective constraints, paving the way for intelligent, autonomous manufacturing systems.
Deep Dive
Key Concepts
Transformer (变换器)
一种基于注意力机制的深度学习架构，能有效捕获全局关系，广泛应用于序列建模。在调度中，它用来学习操作间的复杂依赖关系。
Proximal Policy Optimization (PPO)
一种强化学习算法，通过限制策略更新幅度，确保训练稳定性。用于优化调度策略的性能，提升学习效率。
Makespan (工期)
完成所有作业所需的总时间，是调度优化的关键目标。模型旨在最小化该指标。
多头注意力机制
Transformer中的核心技术，允许模型同时关注输入的多个不同部分，增强表达能力。
泛化能力
模型在未见过的实例或更大规模问题上保持良好性能的能力，是衡量模型实用性的关键指标。
Open Questions Unanswered questions from this research
- 1 如何在极大规模（如千级规模）实例中保持高效性仍未解决，尤其在注意力机制计算复杂度方面。未来需探索稀疏或分层注意力机制以提升效率。
- 2 模型未考虑动态变化环境，实时调度和在线学习仍是挑战。如何结合实时数据进行自适应调整，是未来研究方向。
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.