考虑运输资源限制的动态柔性车间调度问题及自适应竞争重构算法

Dynamic Flexible Job Shop Scheduling Problem Considering Transportation Resource Constraints and Adaptive Competitive Reconfiguration Algorithm

摘要

针对具有运输资源的动态柔性车间调度问题设计了两阶段自适应竞争重构算法（TACRA）。初始阶段，TACRA在静态环境中运行。一旦机器故障发生，TACRA进入重调度阶段。TACRA包含可增强算法探索与开发能力的删除算子和重构算子，以及基于算子历史性能的自适应选择机制。15个测试实例中，TACRA分别在反向世代距离、超体积和适应度上取得11、15和15个最优结果。

Abstract

This paper proposes a two-stage adaptive competitive reconfiguration algorithm （TACRA） for the dynamic flexible job shop scheduling problem with transportation resources. In the initial phase， TACRA operates in a static environment； once a machine breakdown occurs， it switches to a rescheduling phase. Deletion and reconstruction operators are designed to enhance the algorithm's exploration and exploitation capabilities， and an adaptive selection mechanism is introduced based on the historical performance of these operators. Experimental results on 15 test instances show that TACRA achieves the optimal inverted generational distance in eleven cases， the optimal hypervolume in fifteen cases， and the optimal fitness metric in fifteen cases.

Graphical abstract

关键词

柔性车间调度 / 多目标优化 / 运输资源 / 动态事件 / 自适应选择

Key words

flexible job shop scheduling / multi-objective optimization / transportation resource / dynamic event / adaptive selection

0 引言

现代制造业正经历智能制造的快速转型与多品种小批量生产模式的普及，这一趋势对生产调度的灵活性、响应速度和抗干扰能力提出更高要求^［1-2］。柔性作业车间调度问题（flexible job shop scheduling problem，FJSP）直接关系生产效率的提高和成本的降低，因此受到广泛关注。一般的FJSP包含两个子问题即机器分配和工序排序^［3］，但研究通常将优化重点放在子问题上，默认运输资源充足或运输时间可被忽略，即常采用假设自动引导车辆（AGV）的数量无限。实际上，工件需要被AGV运送到指定机器加工；机器没有释放工件，AGV也无法运输^［4］； AGV的选择直接影响运输路线和运输时间，从而影响最终完工时间。因此机器和AGV的协同调度对最大限度提高设备利用率和生产效率非常关键，具有运输资源的柔性作业车间调度问题（flexible job shop scheduling problem with transportation resources，FJSPT）具有重要的研究意义。

实际的调度会遇到很多的突发情况，如机器故障、新工作订单到来、交货期限改变^［5］，从而打乱最初设计的调度方案。为减小机器故障的不利影响，调度算法引入重调度策略，如基于知识的两阶段模因算法框架^［6］在重调度阶段采用知识驱动的可变邻域搜索策略，以快速找到最优解并深入探索解空间。WEN等^［7］设计了一种结合遗传算法和局部搜索算法的混合算法来处理机器故障下的动态调度。TANG等^［8］提出自适应调整参数和改进精英选择策略，以增强重调度的稳定性。一些使用集成强化学习的遗传算法可应对机器突发故障带来的生产调度优化难题^［3］，即产生高质量的解，但预训练耗时太长，难以满足算法的效率要求，尤其是在处理高维状态空间或大规模车间问题。

在具有运输资源的动态柔性作业车间调度问题（dynamic flexible job shop schedule problem with transportation resources，DFJSPT）中，机器故障影响机器与AGV。机器发生故障时，立即停止工作，受影响的工件必须及时分配给其他可用机器，空闲的AGV被迅速调用。因此，需要同步调度机器和AGV，以确保生产的顺利进行。

为提高调度系统的灵活性和应急响应能力，应对日益复杂和不断变化的挑战，本文针对DFJSPT设计了两阶段自适应竞争重构算法（two-stage adaptive competitive reconfiguration algorithm，TACRA）。

1 DFJSPT的描述与建模

1.1 问题描述

DFJSPT需要解决耦合的4个子问题：①确定工序的顺序；②为每个工序选择加工机器；③为每个工序分配一台AGV完成运输任务；④机器故障发生后重新调度。

假设有n个待加工工件、m台机器、a个AGV。工件J_i （i=1，2，…，n）的第j个工序O_ij 由可选机器集M_ij 中的一台机器完成。DFJSPT从数量有限的AGV（可运输任何工件）中选择一台分配给工序，并划分相应的运输时间。每个被分配的AGV在特定时间窗内只服务于特定工序^［9］。开始加工时，AGV将工件从装卸LU区运送到加工机器。工序O_ij 在机器M_k ∈M_ij 上完成后，AGV运输J_i 到下一台机器，最终完成的工件由AGV运送回装卸LU区。

DFJSPT由初始阶段、重调度阶段组成。初始阶段内，没有机器发生故障，所有资源都可用。机器发生故障时，重调度被触发。故障修复完成前，故障机器不能工作。机器故障包含3个关键因素：故障机器的索引k_B、机器故障的发生时间B_S和修复时间B_T。所有未处理和受故障影响的工序将根据重调度策略重新计划。DFJSPT模型包含如下约束和假设：①机器在同一时刻只能加工一个工件，AGV在同一时刻只能运输一个工件；②工序的顺序约束只对同一工件有效；③所选机器是工序的可选机器之一；④除机器故障外，加工不能中断；⑤故障发生后，故障机器不再工作，直到修复完成；⑥AGV沿最短路径行驶，运输过程中没有拥挤和中断；⑦AGV在机器之间的运输时间已知。DFJSPT数学模型中涉及的符号及其含义如表1所示。

1.2 数学模型

考虑生产对效率的要求，将最小化最大完工时间作为目标f₁。为防止设备长期过载、增加故障风险，将最小化负载不均衡度即每台机器和AGV的负载偏离平均负载的程度（比率）^［10］作为目标f₂。f₁与f₂的目标函数如下：

f_{\mathrm{1}}:\mathrm{m}\mathrm{i}\mathrm{n}{C}_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{m}\mathrm{a}\mathrm{x}\sum _{i\in J,j\in J_i}{t}_{E,ij}^{})（1）

f_{\mathrm{2}}:\mathrm{m}\mathrm{i}\mathrm{n}\{\frac{\mathrm{1}}{t_{AM}}|\sum _{k\in M}(\sum _{i\in J}\sum _{j\in J_i}{t}_{ijk}{x}_{ijk}-t_{AM})|+

\frac{\mathrm{1}}{t_{\mathrm{A}\mathrm{V}}}\sum _{v\in V}|\sum _{i\in J}\sum _{j\in J_i}\sum _{q\in M}\sum _{k\in M_{ij}}{t}_{ijqkv}^{}{\alpha }_{ijqkv}-t_{\mathrm{A}\mathrm{V}}|\}（2）

约束：

t_{\mathrm{E},hg}^{}\le t_{\mathrm{S},ij}^{}+(\mathrm{1}-z_{ijhgk})G

\forall i\in J,j\in J_i,h\in J\backslash \{i\},g\in J_h,k\in M_{ij}\bigcap M_{hg}（3）

t_{\mathrm{E},ij}^{}-t_{\mathrm{S},ij}^{}=\left\{\begin{array}{ll}G& t_{\mathrm{S},ij}^{}\le B_{\mathrm{S}}\le t_{\mathrm{E},ij}^{}\mathrm{且}k=k_{\mathrm{B}}\\ t_{ijk}{x}_{ijk}& \mathrm{其他}\end{array}\right.（4）

B_{\mathrm{S}}+B_{\mathrm{T}}\le t_{\mathrm{S},ij}^{}+(\mathrm{1}-x_{ijk})G

B_{\mathrm{S}}\le t_{\mathrm{S},ij}^{}\le B_{\mathrm{S}}+B_{\mathrm{T}}\mathrm{且}k=k_{\mathrm{B}}（5）

\begin{array}{cc}{t}_{\mathrm{S},ij}^{}\ge t_{\mathrm{E},i(j-\mathrm{1})}^{}& \forall i\in J,j\in J_i\end{array}（6）

\begin{array}{cc}{C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\ge t_{\mathrm{E},ij}^{}& \forall i\in J,j\in J_i\end{array}（7）

\begin{array}{cc}\sum _{k\in M_{ij}}{x}_{ijk}=\mathrm{1}& \forall i\in J,j\in J_i\end{array}（8）

t_{\mathrm{A}\mathrm{M}}=\frac{\mathrm{1}}{m}\sum _{k\in M}\sum _{i\in J}\sum _{j\in J_i}{t}_{ijk}{x}_{ijk}（9）

t_{\mathrm{A}\mathrm{V}}=\frac{\mathrm{1}}{a}\sum _{v\in V}\sum _{i\in J}\sum _{j\in J_i}\sum _{q\in M}\sum _{k\in M_{ij}}{t}_{ijqkv}^{}{\alpha }_{ijqkv}（10）

\begin{array}{cc}\sum _{v\in V}\sum _{q\in M_{ij-\mathrm{1}}}\sum _{k\in M_{ij}}{\alpha }_{ijqkv}=\mathrm{1}& \forall i\in J,j\in J_i\end{array}（11）

\begin{array}{cc}\sum _{v\in V}\sum _{q\in M_{i(j-\mathrm{1})}}\sum _{k\in M_{ij}}{x}_{ijk}{\alpha }_{ijqkv}=\mathrm{1}& \forall i\in J,j\in J_i\end{array}（12）

t_{\mathrm{E},ij}^{},t_{S,ij}^{},t_{ijk},t_{ijqkv}^{}\ge \mathrm{0},

\forall i\in J,j\in J_i,q\in M_{ij-\mathrm{1}},k\in M_{ij},v\in V（13）

z_{ijhgk}\in \{\mathrm{0,1}\},

\forall i\in J,j\in J_i,h\in J\backslash i,g\in J_h,k\in M_{ij}\bigcap M_{hg}（14）

式（3）表示一台机器同时只能处理一个工序，其中，J为工件集合，J\｛i｝为剔除工件i的工件集合。式（4）表示机器M_{k_B}发生故障，导致工序O_ij 中断，工序结束时间t_E，ij 被无限延迟，其他机器则不受影响，满足加工不中断的常规约束。式（5）表示在故障机器M_{k_B}正在加工且开始时间位于故障修复窗口内的工序O_ij，开始加工时间t_S，ij 必须被延迟到修复完成时间B_S+B_T之后。由式（6）可知，同一工件的工序存在先后约束。式（7）表示任何工序的完成时间都不能超过最大完工时间。式（8）表示一个工序只能在一台机器上完成。式（11）表示运输操作仅由一个AGV完成。式（12）表示机器和AGV的耦合关系。

1.3 确定重调度阶段的资源可用性

重调度阶段需要更新所有受故障影响和未处理工序的状态，而确定这些工序是重调度面临的第一个问题。由图1所示的初始调度可知，M₃的故障发生时间T_b=5.5 h，O₁₂是正在处理的工序。由于O₂₂、O₃₂的AGV运输过程M₁→M₂和M₃→M₁已经开始，因此将O₂₂和O₃₂归类为处理中的工序。值得注意的是，即使O₂₂和O₃₂尚未完成，也会被取消，并在重调度时被新的工序取代，以保证生产过程尽快恢复正常。O₁₃、O₃₃是未开始的工序，重新安排未开始的工序时，相应的运输工序也会发生变化。

2 两阶段自适应竞争重构算法

TACRA在初始阶段和重调度阶段的处理方法不同。初始阶段时，TACRA利用NSGA-Ⅱ^［11］优化种群。当检测到机器故障时，TACRA进入重调度阶段。为增强算法的探索和开发能力，设计出竞争的删除算子和重构算子，以及依赖算子历史性能的自适应选择机制。删除算子从解中删除性能差的工序、机器和AGV。重构算子利用精英解的知识生成新的解。因此，TACRA能探索更大的解空间，找到更好的解决方案。图2为TACRA流程图。

2.1 编码和解码

对解进行编码涉及3个子问题：工序排序（OS）、机器选择（MS）和AGV调度（VS），因此使用三层编码方法。如图3所示，首先生成OS向量，然后根据OS和相应的约束确定MS向量和VS向量。OS、MS、VS组合的三层编码构成问题的一个解决方案，每层的长度L为所有工件包含的加工工序总数。OS、MS、VS三层编码的具体含义：

（1）OS层编码。OS层编码中的元素为工件编号，第一次出现i表示为工序O_i1，第二次出现i表示为工序O_i2，依此类推。

（2）MS层编码。MS层编码中的元素为可选机器集合中的机器索引。如图3所示，MS层编码中的第一个元素2表示工序O₁₁选择可选机器集｛M₁， M₃｝中的机器M₃。

（3）VS层编码。VS层编码的元素为被选AGV的索引。如图3所示，VS层编码第二个元素2表示工序O₂₁对应的工件J₂ 由V₂运输。

2.2 删除操作

删除操作从当前解X∈P_t的编码中删除指定数量的元素，并返回X剩余的元素作为编码X_d。删除时暂时忽略工序之间的约束关系。第t代删除元素的数量计算公式为

N_d，t =L（Q₁-（Q₁-Q₀）t/T）（15）

式中：L为X的长度；Q₀为初始删除率；Q₁为最终删除率；T为进化总代数。

删除操作包括4个删除算子：

（1）随机删除算子（RD）。从OS层中随机删除N_d，t 个元素后，MS和VS相应位置的元素也被删除，将删除的元素保存在集合φ中，以用于随后的重构操作。

（2）基于完成时间的删除算子（CD）。对于OS，按照完成时间

t_E，ij = t_S，ij + t_ijk （16）

ij=X_{\mathrm{o}\mathrm{s}}[l],k=X_{\mathrm{m}\mathrm{s}}[l],l\in \{\mathrm{1,2},\dots ,L\}

式中：ij表示工序索引；l表示编码位置索引。

从晚到早依次删除N_d，t 个元素，同时删除MS和VS中相应位置的元素。

（3）基于机器运行时间和AGV负载时间的删除算子（RL）。RL用于平衡机器和AGV的工作压力，减小故障概率。对MS和VS删除工作时间较长的N_d，t 个元素。机器运行时间t_run，k 和AGV负载时间t_laod，v 分别为

t_{\mathrm{r}\mathrm{u}\mathrm{n},k}=t_{ijk}（17）

t_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d},v}=t_{\mathrm{c}l,ijv}^{}-t_{\mathrm{s}l,ijv}^{}v=X_{vs}[l]（18）

式中：t_sl，ijv 、t_cl，ijv 分别为AGV运输O_ij 的开始和结束时间。

（4）基于机器空闲时间和AGV空载时间的删除算子（IN）。从MS和VS 中删除N_d，t 个空闲时间和空载时间较长的元素。MS每个元素的空闲时间为

t_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e},k}=t_{\mathrm{S},ij}^{}-\mathrm{m}\mathrm{a}\mathrm{x}(t_{\mathrm{E},ij-\mathrm{1}}^{},t_{\mathrm{E},hg}^{}{z}_{ijhgk})（19）

hg=X_{\mathrm{o}\mathrm{s}}[l^{\text{'}}],k=X_{\mathrm{m}\mathrm{s}}[l],l,l^{\text{'}}\in \{\mathrm{1,2},\dots ,L\}

式中：t_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e},k}为机器M_k 的空闲时间；t_{\mathrm{E},ij-\mathrm{1}}^{}为O_ij-1 的结束时间；hg表示X_os中的一个元素；l和l^{\text{'}}表示编码位置索引。

对于VS每个元素的空载时间为

t_{\mathrm{n}\mathrm{o}\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d},v}=t_{\mathrm{c}\mathrm{e},ijv}^{}-t_{\mathrm{s}\mathrm{e},ijv}^{}（20）

式中：t_se，ijv 、t_ce，ijv 分别为AGV运输O_ij 前的空载运输的开始和结束时间；v为机器索引。

2.3 重构操作

应用删除算子后，一些表现不佳的元素被删除，因此须设计重构算子来重建被破坏的解X_d，生成新解X_r。重构生成新解X_r的首要目标是增强解的探索能力，其次是提高种群的多样性。为实现这些目标，迭代过程中将保留的非支配解集P_e作为精英解集来指导重构过程。删除算子对应的重构算子如下。

（1）随机插入重构算子（RI）。RI针对删除算子RD设计。对于OS层编码，删除元素随机插入X_d，然后同样，按照OS插入元素的位置向MS层编码和VS层编码插入对应元素。因此RI可加解的多样性。

（2）基于完成时间的重构算子（CR）。CR针对删除算子CD设计。由于最小化最大完工时间是目标f₁，因此选择P_e中最小化最大完工时间最小的精英解X_e重构X_d，即将X_e中X_d的空位置对应的元素插入X_d的空位，填充被删除的元素，得到新解X_r。

（3）基于负载不均衡度的重构算子（LI）。LI针对删除算子RL设计。最小化负载不均衡度是目标f₂，选择P_e中最小化负载不均衡度最小的精英解X_e来重构X_d。与CR相同，X_e对应X_d的空位置对应的元素被插入X_d的空位置。

（4）基于加权目标的重构算子（WR）。WR针对删除算子IN设计。为进一步挖掘平衡目标f₁和f₂的高质量解，使用加权目标值最小的精英解X_e来重构X_d，目标f₁、f₂的加权目标权重均为0.5。

图4给出了重构操作的两个例子。由于选择的重构算子不同，图4a、图4b所示的重构过程略有不同。图4a中，原始解X首先执行RD，随机移除元素O₁₂、O₂₂，获得X_d。RI将被移除元素随机插入X_d、得到新解X_r。在图4b中，X使用RL移除较差的O₁₁、O₂₂。图4b中的LI利用精英解X_e将O₁₂、O₂₂放在X_d的空位、得到新解X_r，new。

2.4 修正操作

重构算子生成新解X_r后，部分元素的分配可能违反约束，导致X_r不可行，须修正不可行的解。OS不可行解含有重复、缺失或错误排序的元素。如图4a所示，解X经过RD和RI处理后，新解X_r出现O₁₂先于O₁₁的错误。修正操作调整O₁₂、O₁₁的顺序，使新解X_r成为可行的解决方案。如图4b例子所示，利用精英解X_e重构后，新解X_r，new的OS中重复出现O₁₂，但缺少O₁₁。修正操作保留第一次出现的O₁₂，删除多余的重复元素，并用缺少的元素O₁₁替换重复元素。MS不可行解的某些元素即机器不在工序对应的可选机器集M_ij 中。如果工序对应的机器不属于M_ij，则随机选择一台属于M_ij 的机器来替换不属于M_ij 的机器。由于工件可由任一AGV运输，因此不需要修正VS。经过修正操作逐一检查和纠正编码后，新解X_r为可行解。

2.5 算子权重更新

重构算子与删除算子匹配，因此删除算子的权重就是删除算子下次被选择的概率：

w_{i,t+\mathrm{1}}=(\mathrm{1}-\lambda )w_{i,t}+\lambda S_i/N_{\mathrm{d}\mathrm{e},i}（21）

式中：系数λ控制对w_i，t 变化的灵敏度，0≤λ≤1；w_i，t 为t代时第i个删除算子的权重，i=1，2，3，4；S_i 为第i个删除算子的得分；N_de，i 为第i个删除算子被选择的次数。

新解X_r支配原始解X时，S_i =3；X_r与X互不支配时，S_i =2；X_r被X支配时，S_i =1。这种更新方法使较差的解也有机会被保留，并在一定程度上增加种群的多样性。

2.6 算法流程

算法在重调度阶段的具体流程如下：

输入：t代种群P_t，种群大小N，最大迭代次数T。

输出：t+1代新种群P_t+1。

Step1 初始化删除算子权重 W =（w₁， w₂， w₃， w₄）和算子的使用次数N_u =（0，0，0，0），设置P_t 解的索引i=1。

Step2 根据N_d，t =L（Q₁-（Q₁-Q₀）t/T）计算删除元素的数量。

Step3 根据算子的权重w_t，使用轮盘赌方法选择删除算子d_j， 其中，j为删除算子的索引，j=1，2，3，4。

Step4 使用d_j 删除X_i ∈P_t 中较差的元素得到X_d，设置N_de，i ←N_de，i +1。

Step5 通过d_j 对应的重构算子的重建X_d，得到X_r。

Step6 修正X_r得到可行的新解。

Step7 基于X_r和X_i 的支配关系，利用w_{i,t+\mathrm{1}}=(\mathrm{1}-\lambda )w_{i,t}+\lambda S_i/N_{de,i}更新d_j 的权重w_j。

Step8i←i+1，对下一个解优化，若i>N，执行Step9，否则返回Step2。

Step9 若算法达到终止条件t>T，结束并返回新一代种群P_t+1，否则返回Step1，进行下一代优化，设置t←t+1。

本文算法的计算复杂度。初始阶段的计算复杂度主要由NSGA-Ⅱ决定，NSGA-Ⅱ的计算复杂度是O（TN²）。重调度阶段的复杂度主要来自Step1~9，Step1~9步骤与X的长度L线性相关。由于T代中每代处理N个解，因此重调度阶段的总复杂度为O（TNL）。

3 仿真结果及分析

为全面评估TACRA的竞争力，在MB测试集上比较TACRA与4种常用算法。所有算法都使用Python 3.8.0编程，测试在配备i5-10400 CPU和8GB RAM的计算机上进行。

3.1 测试函数

MB测试集模拟了AGV运输的车间发生机器故障的场景。每个测试算例均预先定义故障机器的索引k_B、机器故障的发生时间B_S和修复时间B_T。设计3种生产规模的车间，其中，小规模（MB1-5）车间生产5~15个工件，中等规模（MB6-10）车间生产20~35个工件，大规模（MB11-15）车间生产40~50个工件。更具体的参数设置如表2所示，其中，n_o 为工件包含工序数量；n_m 为每道工序的可选机器数量；t_p为每道工序的加工时间。

3.2 性能评价指标

为避免目标f₁和f₂的量纲与数量级的差异影响优化方向，先归一化处理目标值，再计算指标。此外，20次重复实验后，将不同算法获得的非支配解集合作为真实Pareto前沿。三个评价指标具体含义如下：

（1）反向世代距离（inverse generation distance，IGD）^［12］是衡量解集收敛性和分布性的综合度量，IGD越小，算法得到解集的综合性能越好。

（2）超体积（hypervolume，HV）^［13］衡量计算解集收敛性的算法性能，HV越大，算法得到解集的收敛性越好。

（3）适应度f_c直观表示算法的目标值结果，计算的公式为

f_{\mathrm{c}}=\mathrm{0.5}(f_{\mathrm{1}}^{\text{'}}+f_{\mathrm{2}}^{\text{'}})（22）

f_{\mathrm{1}}^{\text{'}}=\frac{f_{\mathrm{1}}-\mathrm{m}\mathrm{i}\mathrm{n}{f}_{\mathrm{1}}}{\mathrm{m}\mathrm{a}\mathrm{x}{f}_{\mathrm{1}}-\mathrm{m}\mathrm{i}\mathrm{n}{f}_{\mathrm{1}}}（23）

f_{\mathrm{2}}^{\text{'}}=\frac{f_{\mathrm{2}}-\mathrm{m}\mathrm{i}\mathrm{n}{f}_{\mathrm{2}}}{\mathrm{m}\mathrm{a}\mathrm{x}{f}_{\mathrm{2}}-\mathrm{m}\mathrm{i}\mathrm{n}{f}_{\mathrm{2}}}（24）

f_c越小，算法得到解集的性能越好。

3.3 算法参数设置

为评估TACRA的竞争力，选择双种群协作遗传算法DCGA^［14］、采用精英保留策略和邻域搜索的方法EGANS^［15］、基于博弈论的候鸟优化算法GT-MBO^［5］、经典的非支配排序算法NSGA-Ⅱ^［11］进行对比。对比算法根据DFJSPT的模型和目标函数调整相关操作。算法的基本参数设置如表3所示，对比算法的参数设置按照对应文献。

3.4 实验结果及分析

表4~表6列出了5种算法的IGD、HV和f_c的均值与标准差。每种算法在MB实例重复20次实验，最佳值以粗体突出显示。分析IGD、HV和f_c的结果可以发现：

（1）IGD可评估算法的收敛性和多样性。如表4所示，TACRA在15个测试实例中获得11个最优值。由于删除、重构、修正操作相互弥补，TACRA在大多数实例都得到最佳性能。GT-MBO在MB1上的性能明显优于TACRA的原因是，GT-MBO采用混合驱动重调度策略，利用领导者引导进化，更适合小规模问题。EGANS在MB3、MB8上的性能更好，这是由于EGANS包含精英保留策略，得到良好的多样性解。TACRA在MB11-15的整体性能优于其他算法。

（2）大规模车间调度和机器故障对算法提出挑战。如表6所示，TACRA对所有问题都具有最好的适应度。NSGA-Ⅱ和DCGA在f_c上的性能较差是由于它们缺少处理动态事件的策略。DCGA是一种群体协作的方法，更适合小规模、低复杂度的问题。大规模问题上，TACRA的f_c明显优于其他算法，说明它能有效解决DFJSPT。

结合IGD、HV和f_c可知，TACRA具有较好的收敛性，但是种群多样性还有提升的空间，须给出解决这一问题。

图5为8个测试实例的适应度演化曲线。GT-MBO优化较慢是因为它没有利用历史精英解提高优化效率。TACRA采用精英解和算子的历史性能指导进化方向，在大多数问题上收敛更快且适应度更小，能很好处理大规模实例MB13和MB15。

图6所示为6个MB测试实例的Pareto前沿，可以看出，TACRA获得的大多数解位于目标空间中目标值较小区域，优于其他算法。从Pareto解集中，工厂可根据自己的偏好选择满足需求的解，如偏好最短完工时间时，可选择f₁最小的解，而偏好最小负载不均衡度时，可选择f₂最小的解。

4 结论

针对具有运输资源约束的动态车间问题，提出一种两阶段自适应竞争重构算法。为增强算法的探索和开发能力，设计了包含多个删除算子和重构算子的算法，并提出自适应选择算子的机制。与对比算法相比，TACRA在大多数测试实例上表现出更好的优化能力和计算效率。未来将在DFJSPT的基础上考虑分布式车间运输资源约束的调度问题，并将TACRA用于实际的车间生产。

参考文献

[1] 张国辉， 蔡翌豪， 李志霄， 等. 考虑有限AGV运输资源的柔性作业车间调度研究［J］. 中国机械工程， 2025， 36（8）： 1811-1823.

[2] ZHANG Guohui， CAI Yihao， LI Zhixiao， et al. Research on Flexible Job Shop Scheduling Problems Considering Limited AGV Transportation Resources［J］. China Mechanical Engineering， 2025， 36（8）： 1811-1823.

[3] 呼子宇， 李紫晗， 孙浩， 等. 基于决策变量关系的动态多目标优化算法［J］. 控制与决策， 2024， 39（1）： 78-86.

[4] HU Ziyu， LI Zihan， SUN Hao， et al. A Dynamic Multi-objective Optimization Algorithm Based on the Relationship of Decision Variables［J］. Control and Decision， 2024， 39（1）： 78-86.

[5] 徐新胜，吴松泽，杜文，等.考虑低碳的柔性作业车间分批调度方法［EB/OL］. 中国机械工程， 2025， 1-16. （2025-03-25）［2026-06-12］.

[6] XUXinsheng， WUSongze， DUWen， et al. Consideration of Low-Carbon Flexible Job Shop Batch Scheduling Methods［EB/OL］. China Mechanical Engineering， 2025， 1-16. （2025-03-25）［2026-06-12］.

[7] XU Gongjie， BAO Qiang， ZHANG Hongliang. Multi-objective Green Scheduling of Integrated Flexible Job Shop and Automated Guided Vehicles［J］. Engineering Applications of Artificial Intelligence， 2023， 126： 106864.

[8] WEI Lixin， HE Jinxian， GUO Zeyin， et al. A Multi-objective Migrating Birds Optimization Algorithm Based on Game Theory for Dynamic Flexible Job Shop Scheduling Problem［J］. Expert Systems with Applications， 2023， 227： 120268.

[9] LUO Cong， GONG Wenyin， LU Chao. Knowledge-driven Two-stage Memetic Algorithm for Energy-efficient Flexible Job Shop Scheduling with Machine Breakdowns［J］.Expert Systems with Applications，2024，235：121149.

[10] WEN Xiaoyu， LIAN Xiaonan， QIAN Yunjie， et al. Dynamic Scheduling Method for Integrated Process Planning and Scheduling Problem with Machine Fault［J］. Robotics and Computer-Integrated Manufacturing，2022，77：102334.

[11] TANG Hongtao， XIAO Yu， ZHANG Wei， et al. A DQL-NSGA-III Algorithm for Solving the Flexible Job Shop Dynamic Scheduling Problem［J］. Expert Systems with Applications， 2024， 237： 121723.

[12] 方遒， 宋豪杰， 卢弘， 等. 集成工人和AGV的多要素柔性作业车间调度方法［J］. 机械工程学报， 2025， 61（18）： 330-343.

[13] FANG Qiu， SONG Haojie， LU Hong， et al. Research on Multi-factors Flexible Job Shop Scheduling Problem with Workers and AGVs［J］. Journal of Mechanical Engineering， 2025， 61（18）： 330-343.

[14] LIU Jiaojiao， SUN Baofeng， LI Gendao， et al. Multi-objective Adaptive Large Neighbourhood Search Algorithm for Dynamic Flexible Job Shop Schedule Problem with Transportation Resource［J］. Engineering Applications of Artificial Intelligence， 2024， 132： 107917.

[15] DEB K， PRATAP A， AGARWAL S， et al. A Fast and Elitist Multiobjective Genetic Algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[16] 张国辉， 李志霄， 张利平， 等. 基于强化学习协同进化算法求解柔性作业车间节能调度问题［J］. 计算机应用研究， 2025， 42（7）： 2039-2047.

[17] ZHANG Guohui， LI Zhixiao， ZHANG Liping， et al. Reinforcement Learning Based Co-evolutionary Algorithm for Solving Flexible Job Shop Energy Efficient Scheduling Problem［J］. Application Research of Computers， 2025， 42（7）： 2039-2047.

[18] 马训德， 毕利， 王俊杰. 基于群体免疫算法的绿色车间调度研究［J］. 系统仿真学报， 2024， 36（11）： 2578-2591.

[19] MA Xunde， BI Li， WANG Junjie. Research on Green Job Shop Scheduling Based on Herd Immunity Optimizer［J］. Journal of System Simulation， 2024， 36（11）： 2578-2591.

[20] HAN Xiaoqing， CHENG Weiyao， MENG Leilei， et al. A Dual Population Collaborative Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem with AGV［J］. Swarm and Evolutionary Computation， 2024， 86： 101538.

[21] CHEN Nanlei， XIE Naiming， WANG Yuquan. An Elite Genetic Algorithm for Flexible Job Shop Scheduling Problem with Extracted Grey Processing Time［J］. Applied Soft Computing， 2022， 131： 109783.

基金资助

国家重点研发计划(2022YFB3705504)

国家自然科学基金(62273295)

河北省自然科学基金(F2024203089)

河北省重点研发计划(21310301D)

河北省重点实验室项目(22567612H)