考虑 AGV 充电约束的多目标柔性作业车间调度问题的机器与 AGV 集成调度

《Swarm and Evolutionary Computation》：Integrated scheduling of machines and AGVs for a multi-objective flexible job shop scheduling problem with AGV charging constraints

　　

•考虑 AGV 充电需求的柔性作业车间调度问题多目标集成优化模型。
•一种集成了三种新策略的改进 NSGA-II 算法：个体选择、自适应交叉和邻域搜索。
•计算实验和实际案例研究证明了所提出模型和算法的有效性和效率。

引言
在工业 5.0 的背景下，智能调度系统通过提高运营效率、优化资源配置和增强制造响应能力，在工业生产中发挥着关键作用 [1,2]。自动导引车（AGV）在现代柔性制造系统中被广泛部署，使得生产调度和运输调度具有内在的相互依赖性。例如，捷普集团（Jabil Group）是一家《财富》全球 500 强企业，也是总部位于美国的全球领先电子制造服务提供商，部署了 AGV 在生产机器之间运输印制电路板。同样，波音公司将其 777 飞机生产线整合了 AGV，用于将复合材料翼组件从热压罐固化站运送到后固化加工和检查站。在此类系统中，作业排序和机器分配决定了物料搬运任务的时间和目的地，而 AGV 的可用性直接影响后续操作的开始时间。因此，生产和运输决策应以集成的方式进行优化，而不是独立处理。Bilge 和 Ulusoy [3] 开创性地将 AGV 整合到作业车间调度问题中，制定了第一个集成生产 - 运输调度模型，称为 JSP-AGV。在 Bilge 和 Ulusoy 的基础工作之上，考虑自动导引车的柔性作业车间调度问题（FJSP-AGV）由 Deroussi 和 Norre [4] 正式引入。他们的公式在一个统一的生产框架内整合了三个相互依赖的决策层（即作业排序、机器分配和 AGV 任务分配），从而构成了一个高度复杂的组合优化问题。在 FJSP-AGV 中，每个作业由一系列工序组成，每个工序可以在几台替代机器之一上进行处理。AGV 用于执行各种物料搬运任务，包括将原材料从物料仓库运送到机器，在机器之间运输作业，以及将完工作业从最后处理机器运送到成品仓库 [5,6]。为了有效减少生产周期时间、提高运营效率并改善柔性作业车间的系统协调性，FJSP-AGV 及其变体已引起学术界和工业界的日益关注。

在这些变体中，多目标 FJSP-AGV 已成为一个重要的扩展。随着智能制造的发展，该问题越来越多地处于资源受限和动态变化的生产环境中，具有以下特征：（1）由有限电池容量驱动的频繁且非计划的 AGV 充电事件，可能在机加工调度和 AGV 路由计划中引发级联中断，从而损害包括吞吐量、调度稳定性和能源效率在内的系统级性能指标；（2）最大机器负荷（ML）已被越来越多的制造企业广泛采用为关键绩效指标（KPI），特别是电子制造（例如印制电路板（PCB）和半导体晶圆制造）和高端设备制造（例如航空航天、海洋和防御系统）中的高科技制造商。ML 表示在调度期内分配给任何机器的最大工作量。最小化 ML 是面向高价值、高精度和高可靠性生产资产的至关重要的保护性调度策略。该策略旨在通过同时缓解生产瓶颈、稳定工艺参数和防止由车间整体负荷不平衡引起的系统性运营中断，在柔性作业车间中产生可持续和稳定的输出。例如，PCB 组装车间通常部署有限数量的高价值检测系统（包括 5DX 自动 X 射线检测单元（380,000 美元）和在线测试（ICT）系统（400,000 美元）），以及高稳定性工艺设备，如压装机床（需要微米级力和位移控制）和波峰焊系统（需要精确调节焊波高度）。在高负荷条件下延长运行会降低测量精度和测试覆盖率，损害压装和波焊连接的互连完整性，并增加非计划生产中断的可能性。因此，ML 构成了高科技制造面临的 FJSP 中的一个关键 KPI；以及（3）为了应对日益激烈的市场竞争、受限的能源可用性和生产车间内多重并发的运营风险，越来越多的制造企业越来越多地采用一种集成优化策略，联合最小化出口时间（ET）、能耗（EC）和 ML，从而减少生产周期时间、降低能耗、缓解生产瓶颈并防止系统性运营中断。此处，ET 是处理所有作业并将其返回装卸（LU）区域所需的时间 [7]。该指标既包含机器处理时间，也包含 AGV 运输时间，而最大完工时间（用 Cmax 表示）仅指机器上所有处理操作的最大完成时间；因此，ET 是一个更现实且具有运营意义的性能指标；EC 汇总了所有机器和 AGV 的能耗。这三个优化目标本质上存在冲突，需要系统的、多目标的权衡策略，因为它们体现了根本不同的调度范式：运营效率、资源利用公平性和可持续能源管理。例如，最小化 ET 通常需要将工序分配给更高容量或更早可用的机器，并增加 AGV 调度频率。此类策略有可能使瓶颈资源过载，从而增加 ML。此外，减少 ET 通常需要密集利用机器和 AGV，导致处理、闲置和运输阶段能耗升高，进而增加 EC。同样，减轻 ML 需要将工序重新分配给多样化的替代机器集合，这一措施可能会延长生产最大完工时间，进而增加 ET。因此，单一调度通常无法同时优化三个关键绩效指标：ET、EC 和 ML。因此，需要帕累托最优多目标优化框架来识别明确平衡这些竞争目标的非支配解。上述三个特征在多目标 FJSP-AGV 中的共存给制造企业从业者和学术研究人员带来了重大挑战。这进一步强调了开发考虑 AGV 充电约束的多目标 FJSP-AGV 集成调度框架的必要性。

大多数现有关于 FJSP-AGV 的研究忽略了 AGV 充电约束 [6,[8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18]]。相比之下，越来越多关于考虑 AGV 的作业车间调度问题（JSP-AGV）的研究明确纳入了这些约束 [[19], [20], [21], [22], [23]]。考虑 AGV 充电约束的 JSP-AGV 是考虑 AGV 充电约束的 FJSP-AGV 的一种特殊变体，其中机器分配是预定的，且消除了路由灵活性。尽管如此，为考虑 AGV 充电约束的 JSP-AGV 开发的解决方案方法不能直接应用于具有相同约束的 FJSP-AGV，这是由于决策范围的根本差异。具体而言，JSP-AGV 仅涉及作业排序和感知充电的运输调度；相比之下，FJSP-AGV 需要对机器分配、作业排序和时空 AGV 路由（包括调度、路径规划和电池充电调度）进行集成优化。迄今为止，只有少数近期研究解决了在 AGV 电池充电约束下的 FJSP-AGV [[24], [25], [26]]。然而，这些研究仅关注优化最大完工时间（用 Cmax 表示）和 EC，而忽略了 ET 和 ML，这是缓解生产瓶颈、稳定工艺参数和防止系统性运营中断的两个关键性能指标。在 FJSP-AGV 中，两个性能指标（ET 和 ML）的优化以及 AGV 充电决策共同对机加工工序到机器的分配和 AGV 运输任务的分配产生重大影响，同时也增加了机器和 AGV 之间实时运营协调的复杂性，从而导致两个关键目标（最大完工时间和 EC）的恶化。为了弥合这一差距，必须解决两个基本挑战：（1）制定考虑 AGV 充电约束的 FJSP–AGV 集成多目标数学模型，同时联合优化机器调度、AGV 路由和充电决策；（2）开发一种高效的、定制的多目标进化算法，能够解决这种高度复杂的、紧密耦合的组合优化问题，以最小化 ET、EC 和 ML。

本研究通过严谨制定的集成 FJSP-AGV 系统多目标优化模型解决了上述挑战，其中 AGV 充电约束被明确嵌入到调度公式中。随后制定了混合整数线性规划（MILP）模型，以同时优化三个运营关键目标：最小化 ET、EC 和 ML。为了解决提出的多目标模型，通常采用几种成熟的多目标进化算法，包括强度帕累托进化算法 2（SPEA2）、多目标差分进化（MODE）和非支配排序遗传算法 II（NSGA-II）。与 SPEA2 和 MODE 相比，NSGA-II 具有几个独特的优势：（i）优越的计算效率，由其快速非支配排序过程实现；（ii）架构简单，通过其精英选择和群体合并机制消除了对外部存档的需求；（iii）稳健的多样性保持，通过自适应拥挤距离算子实现，该算子对参数设置表现出低敏感性；以及（iv）在快速收敛和分布良好的高质量帕累托最优解方面表现出色。因此，本研究提出了一种改进的 NSGA-II 算法，旨在解决所制定的多目标 MILP 模型。本工作的主要贡献总结如下：（1）本研究调查了受现实 AGV 充电约束的 FJSP-AGV 系统的集成生产 - 运输调度问题。该公式解决了智能制造系统中一个实际关键但相对探索较少的挑战：在能源和时间限制下，联合优化作业排序、机器分配、AGV 任务分配和动态充电调度。（2）本研究使制造企业能够系统地确定四个关键 AGV 运行参数的最佳配置：最大电池容量、充电速率、充电启动阈值和车队规模。通过这样做，它为制造运营经理做出了基于数据的最佳决策提供了严谨的、基于证据的基础。

此外，本研究在概念和方法上做出了创新：（1）它提出了一种用于 FJSP-AGV 的新型多目标 MILP 公式，明确纳入了 AGV 充电约束。与先前的公式不同，该模型引入了两个基于经验的优化目标：即最小化 ET 和 ML。这两个新目标反映了一种旨在减少生产周期时间、平衡机器工作量分布和缓解生产瓶颈的主动策略，从而符合高科技制造企业的运营要求；（2）它引入了一种专门针对解决上述 MILP 模型而设计的 NSGA-II 算法改进变体。为了同时提高帕累托最优解集的收敛性和多样性，以及集成调度框架的计算效率，该算法集成了一种基于染色体的个体选择机制，旨在加速算法收敛并提高帕累托最优解集的收敛精度；一种自适应交叉策略，根据实时群体多样性指标动态调节重组强度；以及一种包含两个专用搜索算子的邻域搜索策略：机器负荷平衡算子和 AGV 重新分配算子。前者专门旨在缓解生产瓶颈，从而减少两个关键性能指标：ML 和 ET；后者旨在减少不必要的充电事件并降低 AGV 车队的总运输时间，从而降低 ET 和 EC。所提出的算法在 90 个包含 AGV 充电约束的多目标 FJSP-AGV 基准实例中，始终优于现有的最先进方法。

本文的其余部分组织如下：第 2 节全面回顾了以前关于具有 AGV 电池补充策略的 FJSP-AGV 的研究，并确定了关键的研究空白。第 3 节介绍了一种结合 AGV 充电约束的新型多目标 FJSP-AGV，并制定了一个具有三个优化目标（最小化 ET、EC 和 ML）的 MILP 调度模型。为了解决提出的模型，第 4 节开发了一种包含三种改进策略的改进 NSGA-II 算法，以生成机器、AGV 和 AGV 充电活动集成调度的高质量帕累托最优解集。第 5 节展示了在充电约束下对九十个修改后的多目标 FJSP-AGV 基准实例和十个多目标 FJSP 基准实例进行的数值实验结果，以及一个现实世界的电子制造案例，从而验证了所提出模型和算法的有效性。此外，研究了四个关键 AGV 运行参数对三个优化目标的影响，并确定了相应的最佳参数配置。最后，第 6 节总结了本研究的主要结论，并强调了未来研究的可能方向。

章节片段
文献综述
大多数现有研究在解决单目标和多目标 FJSP-AGV 时，忽略了将电池充电约束纳入其数学公式中。

据我们所知，只有少数近期研究在多目标 FJSP-AGV 优化框架中明确建模了这些约束。因此，本节综述了两个密切相关的研究流：(1) 具有电池补充约束的 JSP-AGV，它是……的特化变体

问题描述与建模

在本节中，首先简要描述多目标 FJSP-AGV。随后，建立了该问题的 MILP 数学模型。

一种融合新策略的增强型 NSGA-II 算法

在多目标 FJSP-AGV 中，必须考虑分配给 AGV 的运输任务，这表明我们的研究专注于集成框架内工件、机器和 AGV 的协同调度。为应对这一挑战，提出了一种集成三种创新策略的增强型 NSGA-II 算法。首先，引入了一种双层编码方案，以有效表示工件、机器和 AGV 的集成调度。其次，一种染色体……

计算实验与结果

为了验证所提出的模型和增强型 NSGA-II 算法在处理考虑 AGV 充电需求和每个工件 ET 的多目标 FJSP-AGV 时的有效性，利用了一百九十二个改进的多目标 FJSP-AGV 基准实例、十个经典的多目标 FJSP 基准实例和一个实际案例研究，以评估其相对于几种最先进算法的性能。为了公平比较，每种算法均独立……

结论与未来工作

具有 AGV 充电约束的 FJSP-AGV 已成为一个重要且充满挑战的研究领域。为解决这一复杂的集成调度问题，本研究提出了一种多目标 MILP 模型，旨在同时最小化三个冲突的性能目标：即 ET、EC 和 ML，制造企业均将这三者视为关键优先事项，以缩短生产周期时间、提高资源利用效率和延长设备使用寿命。

CRediT 作者贡献声明

Xiaoxiao Lin：写作 – 初稿，调查，概念化。Wenjie Liu：写作 – 审阅与编辑，验证，监督，项目管理，方法论。Jian Chen：资源，资金获取。Jianfu Chen：可视化，软件，资金获取。Liang Liu：形式分析，数据整理。
Xiaoxiao Lin|Wenjie Liu|Jian Chen|Jianfu Chen|Liang Liu