深度强化学习Transformer求解开放车间调度问题

开放车间调度问题（OSSP）是工业和服务业中常见的组合优化难题，随着作业和机器数量的增加，其计算复杂性急剧上升。传统精确方法在大规模场景下往往难以在合理时间内求得最优解，而经典调度规则和元启发式算法虽然可行，却需要大量调参才能维持解的质量。针对这一挑战，近期一项来自arXiv的研究提出了一种基于深度强化学习（DRL）的Transformer方法，旨在以数据驱动的方式高效求解OSSP。

该研究构建了一个编码器-解码器架构的Transformer模型，其中编码器利用多头注意力机制处理作业的加工时间矩阵，从而学习作业之间的复杂依赖关系；解码器则逐步生成可行的调度序列。模型仅在Taillard基准实例（包括4x4、5x5、7x7和10x10规模）上进行训练，输入仅包含加工时间矩阵，不依赖任何人工设计的特征或领域知识。训练完成后，模型生成的调度方案其最大完工时间（makespan）与已知最优值的偏差通常在15%至30%之间。

为了评估模型的泛化能力，研究者将训练好的策略直接应用于随机生成的更大规模实例（从40x40到100x100），无需任何重新训练或微调。对比的基线方法包括最短加工时间优先（SPT）、最长加工时间优先（LPT）、最大剩余工作量优先（MWKR）和最早开始时间优先（EST）等经典调度启发式规则。实验结果显示，Transformer策略在这些大规模实例上的平均相对偏差（相对于标准下界）为12.89%至15.12%。与EST相比，Transformer仅存在微小的性能差距，但显著优于SPT和LPT，尤其是在问题规模增大时，Transformer的优势更为明显。

这一成果表明，基于Transformer的调度策略具备从“小数据”到“大问题”的迁移学习能力。模型在小型基准实例上习得的调度知识，能够有效地泛化至未见过的、规模更大的OSSP实例，且无需针对新问题重新设计特征或调整超参数。这种“特征精简、学习驱动”的方法为传统调度规则提供了一种有竞争力的替代方案，尤其适合那些加工时间矩阵已知、但难以手动设计高效规则的工业场景。

从技术角度看，该研究将深度强化学习与Transformer架构相结合，解决了组合优化领域的一个经典难题。Transformer的自注意力机制天然适合捕捉作业与机器之间的全局交互，而强化学习框架则使模型能够通过试错探索更优的调度策略。未来，该方法有望进一步扩展至更复杂的调度变体，如带约束的OSSP或动态调度场景，为智能制造和自动化排程提供新的技术路径。