基于DDQN-MCTS混合算法的多负载AGV和FJSP生产调度的集成优化方法

《Exploratory Research in Clinical and Social Pharmacy》：An integrated optimization method for multi-load AGVs and FJSP production scheduling based on DDQN-MCTS hybrid algorithm

AGV协同优化与生产调度研究提出DDQN-MCTS混合算法，通过构建多约束MDP模型整合双深度Q网络与蒙特卡洛树搜索，解决柔性车间中多负载AGV的调度冲突与动态场景适应问题。实验验证其具有更强的泛化能力与复杂环境调度性能。

　　

Jian Zhang|Hongbing Yang|Yaping Zhu|Xinyu Zhang|Yuchen Gao|Yingying Tian

苏州大学机械与电气工程学院，中国苏州215137

摘要

自动化引导车辆（AGVs）在智能工厂中的物料搬运应用日益广泛，而AGV物料搬运与生产调度的联合优化对于提高制造效率至关重要。为了解决灵活作业车间中多负载AGV集成优化的挑战，本研究提出了一种混合DDQN-MCTS优化算法。通过构建多约束马尔可夫决策过程（MDP）模型，该方法创新地将双深度Q网络（DDQN）的价值评估能力与蒙特卡洛树搜索（MCTS）的动态搜索能力相结合，从而通过MCTS优化DDQN的价值评估。此外，MCTS中引入了工件标识符替换机制，以增强模型的潜在表示能力，有效解决了数学规划、启发式方法和元启发式方法在动态生产场景下的有限泛化能力问题。在多个数据集上的实验结果表明，所提出的算法在复杂生产环境中具有出色的调度性能和强大的泛化能力。

引言

深度强化学习（DRL）在高效表征复杂状态和动作空间方面表现出显著的能力。通过代理与环境之间的持续交互，DRL能够适应高度动态、不确定且难以建模的环境，展现出强大的泛化能力和鲁棒性（Ladosz等人，2022年）。近年来，随着计算能力和算法创新的飞跃，研究人员开始将DRL应用于传统方法难以解决的挑战。其中，灵活作业车间调度问题（FJSP）作为一个经典的NP难题（Gao等人，2016年），由于其固有的计算复杂性和在工业制造系统中的实际价值，已成为深度强化学习应用的重点研究领域。在智能制造的背景下，自动化引导车辆（AGVs）的调度成为平衡生产效率和运营成本的关键挑战。传统的调度方法往往无法在动态灵活作业车间环境中协调资源利用效率与敏捷响应性。多负载AGVs与FJSP生产调度的集成优化问题（Homayouni & Fontes，2021年）不仅需要优化作业序列和机器分配，还需要考虑机器的灵活性和作业间的约束。此外，还需要为AGVs分配运输任务并确定每辆车的任务序列，进一步增加了问题的计算复杂性。

本文提出了一种名为DDQN-MCTS的融合算法，它将双深度Q网络（DDQN）与蒙特卡洛树搜索（MCTS）相结合，以解决带有自动化引导车辆的灵活作业车间调度问题（FJSP-AGV）。该方法构建了一个多约束马尔可夫决策过程（MDP）模型，并利用蒙特卡洛树搜索（MCTS）来评估联合动作价值函数，有效解决了独立DDQN代理倾向于追求自身局部最优解的问题，这些局部最优解可能与系统的全局最优解发生冲突。

本研究的主要贡献如下：（1）构建了一个用于多AGV调度和灵活作业车间生产协同优化的集成模型，考虑了路径冲突和多负载AGVs之间的功率限制等复杂约束；（2）将FJSP-AGV调度问题转化为马尔可夫决策过程（MDP），并设计了一个端到端的双代理系统来协同决策作业选择和资源分配；（3）提出了一种新颖的DDQN-MCTS混合算法，该算法利用蒙特卡洛树搜索来优化DDQN的价值评估机制，实现了多AGVs和生产调度的协同优化。从理论角度分析了该算法在FJSP-AGV场景中的收敛性；（4）广泛的对比实验验证了所提算法在灵活作业车间多负载运输场景中的优越性，通过蒙特卡洛树搜索的零件符号替换机制显著提升了训练有素的DDQN-MCTS算法在不同场景下的泛化能力和鲁棒性。

本文的其余部分组织如下：第2节回顾了FJSP-AGV的相关文献；第3节开发了FJSP-AGV问题的集成优化模型；第4节详细介绍了DDQN-MCTS混合算法的设计；第5节展示了实验结果；第6节总结了研究成果并提出了未来工作的建议。

章节摘录

使用深度强化学习解决FJSP

FJSP是作业车间调度问题（JSP）的一个特例，它引入了基于JSP的机器选择问题。Wan等人（2024年）提出了一个双MDP框架，将FJSP分解为两个协同子任务：操作选择和机器分配。该框架采用多头图神经网络作为状态编码器来提取作业和机器之间的拓扑特征，并利用软双演员评论家算法作为决策者来实现

问题描述与假设

FJSP的特点在于机器的灵活性：每个操作可以在具有不同处理时间的多个候选机器上执行。这为在实际生产中平衡机器负载提供了适应性。FJSP-AGV通过引入AGV运输，演变为一个集成优化问题。除了排序和机器分配之外，它还考虑了AGV路径规划、任务分配和车辆调度，使得优化更加复杂

FJSP-AGV问题的MDP

FJSP-AGV中的调度过程可以表述为一个MDP，通常由五元组（S, A, P, γ, R）定义，其中：S表示状态空间，包含所有可能的状态；A表示动作空间，涵盖所有可执行的动作；P是状态转移概率，描述在执行状态S_t中的动作后转移到下一个状态S_t+1的概率；γ是折扣因子，用于调整未来奖励对

案例描述

由于缺乏FJSP和多负载AGVs集成优化问题的标准化基准数据集，本研究通过随机生成构建了九个实验数据集。根据数据集的问题规模，将它们分为三类：大型、中型和小型。实验环境设置在一个30 × 30的网格地图上，包括三辆AGV和八台加工机器，其具体空间分布如图4所示。在表4中，cs

结论与未来工作

为了解决灵活作业车间和自动化引导车辆生产调度的集成调度挑战，本研究提出了一种基于深度强化学习的端到端调度方法。为了有效管理FJSP的复杂性，问题被分解为两个子任务：工件选择和资源分配。这些子任务被构建为一个MDP，该MDP整合了状态表示、动作空间设计和奖励机制。

CRediT作者贡献声明

Jian Zhang：方法论、软件、撰写——原始草稿、撰写——审阅与编辑。Hongbing Yang：概念化、方法论、撰写——原始草稿、撰写——审阅与编辑、调查、监督。Yaping Zhu：形式分析、数据整理、撰写——审阅与编辑、验证。Xinyu Zhang：软件、验证。Yuchen Gao：数据整理、验证。Yingying Tian：数据整理、可视化。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。

致谢

本研究得到了国家自然科学基金（项目编号52575587）的支持。