用决策变压器优化神经局部搜索,提升作业车间调度求解质量。
Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem
- 用决策变压器学习神经局部搜索的决策轨迹,改进搜索策略。
- 在允许较长计算时间场景下,决策质量显著优于原模型。
- 适合对求解精度要求高、可接受较长推理时间的应用场景。
作业车间调度问题(JSSP)及其求解算法多年来在学术界和工业界持续受到关注。近年来,机器学习(ML)在推动现有启发式方法改进及新方法构建方面发挥越来越重要作用,旨在更短时间内获得更优解。本文基于先进的深度强化学习代理神经局部搜索(NLS),该代理能高效控制大规模局部邻域搜索。我们提出一种方法,利用训练好的NLS代理产生的搜索轨迹来训练决策变压器(DT)算法,以进一步优化其决策序列。实验表明,DT成功学习到与原NLS不同且在多数情况下更有效的局部搜索策略。在解的质量与可接受计算时间的权衡中,当允许更长计算时间时,DT表现尤为出色:尽管单步推理时间因更大网络结构而增加,但每步决策质量更高,最终实现基于机器学习增强搜索的当前最优结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。