Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem

📄 arXiv: 2409.02697v2 📥 PDF

作者: Constantin Waubert de Puiseau, Fabian Wolz, Merlin Montag, Jannik Peters, Hasan Tercan, Tobias Meisen

分类: cs.AI, cs.LG

发布日期: 2024-09-04 (更新: 2025-02-04)

💡 一句话要点

提出基于决策Transformer的神经局部搜索方法，提升Job Shop调度问题求解性能。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: Job Shop调度问题 决策Transformer 神经局部搜索 深度强化学习 组合优化

📋 核心要点

  1. Job Shop调度问题是工业界的经典难题，传统方法难以在短时间内找到高质量的解决方案。
  2. 本文利用决策Transformer学习神经局部搜索的搜索轨迹，从而改进局部搜索的决策过程。
  3. 实验表明，决策Transformer能够学习到更有效的局部搜索策略，并在可接受的计算时间内取得更好的结果。

📝 摘要（中文）

本文针对Job Shop调度问题(JSSP)，利用机器学习方法改进启发式算法。在现有先进的深度强化学习(DRL)智能体——神经局部搜索(NLS)的基础上，提出了一种训练决策Transformer(DT)算法的方法，该方法基于NLS智能体的搜索轨迹进行训练，以进一步改进学习到的决策序列。实验结果表明，DT成功学习到了与NLS智能体不同且通常更有效的局部搜索策略。在解决方案质量和可接受的计算时间之间的权衡方面，DT在可接受更长计算时间的场景中表现出优越性。通过每步更高质量的决策，弥补了较大神经网络架构导致的较长推理时间。因此，DT在利用机器学习增强搜索来解决JSSP问题方面取得了最先进的结果。

🔬 方法详解

问题定义：Job Shop调度问题(JSSP)旨在寻找最优的工件加工顺序，以最小化完工时间。现有的启发式算法和深度强化学习方法在求解JSSP时，面临着搜索效率和解质量之间的权衡问题，尤其是在复杂问题实例中，难以在有限时间内找到高质量的解。

核心思路：本文的核心思路是利用决策Transformer (DT) 学习现有神经局部搜索 (NLS) 智能体的搜索轨迹，从而模仿并改进 NLS 的决策过程。DT 能够捕捉 NLS 搜索过程中的长期依赖关系，并学习到更有效的局部搜索策略，从而在保证搜索效率的同时，提升解的质量。

技术框架：整体框架包含两个主要阶段：首先，训练一个基于深度强化学习的神经局部搜索 (NLS) 智能体。然后，收集 NLS 智能体在求解 JSSP 实例时的搜索轨迹数据。最后，使用收集到的搜索轨迹数据训练决策Transformer (DT)，使其能够模仿并改进 NLS 的决策过程。DT 在推理阶段，根据当前 JSSP 的状态，预测下一步应该采取的局部搜索动作。

关键创新：本文的关键创新在于将决策Transformer (DT) 应用于神经局部搜索 (NLS) 的改进。与传统的强化学习方法不同，DT 是一种序列建模方法，能够直接从历史轨迹数据中学习策略，避免了复杂的奖励函数设计和探索过程。此外，DT 能够捕捉 NLS 搜索过程中的长期依赖关系，从而学习到更有效的局部搜索策略。

关键设计：论文中，DT 的输入包括 JSSP 的状态表示、之前的搜索动作序列以及目标函数值。DT 的输出是下一步应该采取的局部搜索动作的概率分布。损失函数采用交叉熵损失，用于衡量 DT 预测的动作概率分布与 NLS 实际采取的动作之间的差异。网络结构采用标准的 Transformer 结构，包括多头自注意力机制和前馈神经网络。

📊 实验亮点

实验结果表明，基于决策Transformer的神经局部搜索方法在求解JSSP问题时取得了显著的性能提升。在可接受的计算时间内，该方法能够找到比原始神经局部搜索方法质量更高的解。具体而言，在某些问题实例上，该方法能够将解的质量提升超过5%。

🎯 应用场景

该研究成果可应用于各种实际生产调度场景，例如制造业、物流运输等。通过优化调度方案，可以提高生产效率、降低成本、缩短交货时间，从而提升企业的竞争力。此外，该方法还可以推广到其他组合优化问题，例如车辆路径问题、旅行商问题等。

📄 摘要（原文）

The job shop scheduling problem (JSSP) and its solution algorithms have been of enduring interest in both academia and industry for decades. In recent years, machine learning (ML) is playing an increasingly important role in advancing existing and building new heuristic solutions for the JSSP, aiming to find better solutions in shorter computation times. In this paper we build on top of a state-of-the-art deep reinforcement learning (DRL) agent, called Neural Local Search (NLS), which can efficiently and effectively control a large local neighborhood search on the JSSP. In particular, we develop a method for training the decision transformer (DT) algorithm on search trajectories taken by a trained NLS agent to further improve upon the learned decision-making sequences. Our experiments show that the DT successfully learns local search strategies that are different and, in many cases, more effective than those of the NLS agent itself. In terms of the tradeoff between solution quality and acceptable computational time needed for the search, the DT is particularly superior in application scenarios where longer computational times are acceptable. In this case, it makes up for the longer inference times required per search step, which are caused by the larger neural network architecture, through better quality decisions per step. Thereby, the DT achieves state-of-the-art results for solving the JSSP with ML-enhanced search.