用Transformer学习调度策略,小规模训练可解决大规模车间调度问题。
A Deep Reinforcement Learning (DRL)-Based Transformer Method for Solving the Open Shop Scheduling Problem
- 用Transformer编码器-解码器结构,仅凭加工时间矩阵生成调度方案。
- 在40×40到100×100的大规模实例上,平均完成时间差距为12.89%-15.12%。
- 无需重训练即可泛化,比传统规则更优,适合工业调度场景。
开放车间调度问题(OSSP)广泛存在于工业与服务领域,但随着作业和机器数量增加,求解变得极为困难。精确方法很快不可行,传统调度规则和元启发式算法在大规模下需大量调参以维持性能。本文提出一种基于Transformer的调度策略,采用编码器-解码器架构结合多头注意力机制。模型在Taillard基准实例(4×4、5×5、7×7、10×10)上训练,仅使用加工时间矩阵作为输入,生成的可行调度完成时间通常在最优已知值的15%-30%以内。为评估可扩展性,该训练好的策略直接应用于40×40至100×100的随机生成实例,对比经典调度启发式(SPT、LPT、MWKR、EST)。在这些大规模实例上,该Transformer模型相对于标准下界平均差距为12.89%-15.12%。相比EST,其表现具有竞争力,显著优于SPT和LPT。结果表明,基于小规模实例训练的Transformer策略可有效泛化至更大规模问题,提供一种特征少、基于学习的替代传统调度规则的新方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。