具有双资源约束的分布式装配混合流水车间调度

Distributed Assembly Hybrid Flow Shop Scheduling with Dual Resource Constraints

摘要

针对具有双资源约束的分布式装配混合流水车间调度问题，提出一种基于知识驱动的迭代贪婪（KDIG）算法。采用基于知识的NEH（Nawaz-Enscore-Ham）初始化策略，生成初始解决方案。基于问题特征设计了4种局部搜索算子。局部搜索算子与Q学习机制的结合使个体在迭代更新时动态选择最优的局部搜索算子，从而显著提升个体在搜索过程中的效率。KDIG算法与5种主流算法在81个大型实例上的测试结果表明，KDIG算法优于其他对比算法。

Abstract

This paper proposes a knowledge-driven iterative greedy （KDIG） algorithm for the distributed assembly hybrid flow shop scheduling problem with dual resource constraints. The algorithm adopts a knowledge-based NEH （Nawaz-Enscore-Ham） initialization strategy to generate the initial solution. Based on the problem characteristics， four local search operators are designed. Combined with a Q-learning mechanism， these operators enable individuals to dynamically select the optimal local search operator during iterative updates， thereby significantly improving search efficiency. Experimental results on 81 large-scale instances， comparing the KDIG algorithm with five other mainstream algorithms， demonstrate that the proposed KDIG algorithm outperforms all benchmark algorithms.

Graphical abstract

关键词

分布式装配混合流车间调度 / 知识驱动 / 迭代贪婪算法 / Q学习

Key words

distributed assembly hybrid flow shop scheduling / knowledge-driven / iterative greedy algorithm / Q-learning

0 引言

以提高生产灵活性并降低大规模定制复杂性为目标的分布式制造已成为一种流行的生产模式^［1］。分布式混合流水车间调度已在汽车、钢铁、电子、半导体、纺织和食品等行业应用广泛，相关研究倍受关注。ZHANG等^［2］提出一种结合粒子群优化和Q-learning局部搜索的多目标模因算法。DI等^［3］提出一种多智能体强化学习方法来最小化完工时间和总能耗。LIU等^［4］针对具有阻塞约束的分布式混合流水车间调度问题（distributed hybrid flow shop scheduling problem，DHFSSP），提出一种改进迭代贪婪算法。CUI等^［5］研究了具有不相关并行机器的多目标DHFSSP，提出一种改进的多种群遗传算法。SHAO等^［6］提出一种能量和劳动感知的网络模因算法解决DHFSSP。

虽然DHFSSP的研究已取得丰硕成果，但大多数研究聚焦于机器资源的优化配置。生产调度不仅受限于机器资源，还需综合考虑人力资源配置。不同客户在产品规格、订单批量、交货周期等方面的定制化需求也应满足。这使得生产过程必须灵活调整以适应每个生产订单的独有特征。因此，研究DHFSSP必须全面考虑复杂的生产场景^［7-9］和生产资源的约束条件^［10-11］。

工作未能在最后期限内完成不仅会引发合同处罚，还会造成声誉损害，故研究具有生产装配与工人资源约束，以最小化总延迟（total tardiness， TTD）为目标的具有双资源约束的分布式装配混合流车间调度问题（distributed assembly hybrid flow shop scheduling problem with dual resource constraints，DAHFSSP-DRC）很有意义。

迭代贪婪（iterative greedy，IG）算法算法是一种高效简单的算法，起初用于解决求解流水车间调度问题^［12］，后被广泛用于解决各类调度问题。JING等^［13］提出不确定处理时间的分布式置换流水车间调度问题，并通过IG算法进行求解。ZOU等^［14］采用自适应IG算法解决制造车间中的自动引导车辆调度问题。为处理阻塞混合流水车间问题，QIN等^［15］提出利用交换策略的IG算法。ZHAO等^［16］利用基于种群的IG算法解决了分布式装配无等待流水车间调度问题，通过新的构造启发式方法初始化起始种群。对于分布式阻塞流水车间调度问题，KARIMI-MAMAGHAN 等^［17］ 在搜索过程中加入Q-Learning来选择合适的扰动算子，提出一种基于Q-Learning的IG算法来解决置换流水车间调度问题。

知识驱动的迭代贪婪（knowledge-driven iterative greedy，KDIG）算法被提出并用于求解DAHFSSP-DRC。本文采用基于知识的NEH （Nawaz-Enscore-Ham）初始化策略生成初始解决方案。结合4种局部搜索算子与Q-learning机制，使个体在迭代更新时动态选择最优的局部搜索算子。81个大型实例的算法对比验证了KDIG算法的优越性。

1 问题描述和数学模型

1.1 DAHFSSP-DRC的描述

根据文献［18］，DAHFSSP-DRC具体描述如下：每个产品的生产分为加工和装配。加工在具有双资源约束的分布式混合流水车间内完成。每个工件都在提前指定的工厂内加工。工件一旦分配到某个工厂，就不能转移到其他工厂。具有相同生产流程的N个工件有连续的N_S个加工阶段。每个阶段由一组机器K_i，j，f 和能加工工件O_i，j 的一组工人W_i，j，f 组成。工件O_i，j 的加工时间提前确定，且不受加工工人的影响。工件O_i，j 加工完毕后，进入装配阶段，即在有一台机器的装配车间逐个组装每个产品。本文用到的量符号及其含义如表1所示。

1.2 数学模型

DAHFSSP-DRC的数学模型如下：

\mathrm{m}\mathrm{i}\mathrm{n}{T}_{\mathrm{T}\mathrm{D}}=\sum _{p\in P}{T}_p（1）

\begin{array}{cc}{T}_p=\mathrm{m}\mathrm{a}\mathrm{x}\{C_p-D_p,\mathrm{0}\}& p\in P\end{array}（2）

\begin{array}{cc}\sum _{f\in F}{Z}_{i,f}=\mathrm{1}& \forall i\in I\end{array}（3）

\begin{array}{cc}{Z}_{i,f}=\sum _{k\in K_{i,j,f}}\sum _{w\in W_{i,j,f}}{V}_{i,j,f,k,w}& \forall i\in I,j\in S,f\in F\end{array}（4）

\begin{array}{cc}{Z}_{i,f}=\sum _{i^{\text{'}}\in I-i}\sum _{k\in K_{i,j,f}}{X}_{i,i^{\text{'}},j,f,k}& \forall i\in I,j\in S,f\in F\end{array}（5）

\begin{array}{cc}{Z}_{i,f}=\sum _{i^{\text{'}}\in I-i}\sum _{w\in W_{i,j,f}}{Y}_{i,i^{\text{'}},j,f,w}& \forall i\in I,j\in S,f\in F\end{array}（6）

\begin{array}{cc}\sum _{i^{\text{'}}\in I-i}\sum _{f\in F}\sum _{k\in K_{i,j,f}}{X}_{i,i^{\text{'}},j,f,k}=\mathrm{1}& \forall i\in I,j\in S\end{array}（7）

\begin{array}{cc}\sum _{i^{\text{'}}\in I-i}\sum _{f\in F}\sum _{k\in K_{i,j,f}}{Y}_{i,i^{\text{'}},j,f,k}=\mathrm{1}& \forall i\in I,j\in S\end{array}（8）

\begin{array}{cc}{S}_{i,j}+\sum _{f\in F}\sum _{k\in K_{i,j,f}}\sum _{w\in W_{i,j,f}}P{T}_{i,j,f,k,w}{V}_{i,j,f,k,w}\le S_{i,j+\mathrm{1}}& \forall i\in I,j\in S\end{array}（9）

C_{i^{\text{'}},j}-\sum _{f\in F}\sum _{k\in K_{i,j,f}}\sum _{w\in W_{i,j,f}}P{T}_{i,j,k,w,f}{V}_{i,j,k,w,f}+L(\mathrm{1}-\sum _{f\in F}\sum _{k\in K_{i,j,f}}{X}_{i,i^{\text{'}},j,f,k})\ge C_{i,j}　　 \forall i\in I,i^{\text{'}}\in I,j\in S（10）

C_{i^{\text{'}},j}-\sum _{f\in F}\sum _{k\in K_{i,j,f}}\sum _{w\in W_{i,j,f}}P{T}_{i,j,k,w,f}{V}_{i,j,k,w,f}+L(\mathrm{1}-\sum _{f\in F}\sum _{k\in K_{i,j,f}}{Y}_{i,i^{\text{'}},j,f,k})\ge C_{i,j}　　 \forall i\in I,i^{\text{'}}\in I,j\in S（11）

\begin{array}{cc}\sum _{i^{\text{'}}\in I-i}{X}_{i.i^{\text{'}},j,f,k}=\sum _{i^{\text{'}}\in I-i}{X}_{i^{\text{'}},i,j,f,k}& \forall i\in I,j\in S,f\in F,k\in K_{i,j,f}\end{array}（12）

\begin{array}{cc}\sum _{i^{\text{'}}\in I-i}{Y}_{i.i^{\text{'}},j,f,w}=\sum _{i^{\text{'}}\in I-i}{Y}_{i^{\text{'}},i,j,f,k}& \forall i\in I,j\in S,f\in F,w\in W_{i,j,f}\end{array}（13）

\begin{array}{cc}\sum _{i^{\text{'}}\in I-i}{X}_{i.i^{\text{'}},j,f,k}=\sum _{w\in W_{i,j,f}}{V}_{i,j,f,k,w}& \forall i\in I,j\in S,f\in F,k\in K_{i,j,f}\end{array}（14）

\begin{array}{cc}\sum _{i^{\text{'}}\in I-i}{Y}_{i.i^{\text{'}},j,f,w}=\sum _{k\in K_{i,j,f}}{V}_{{}^{i,j,f,k,w}}& \forall i\in I,j\in S,f\in F,w\in W_{i,j,f}\end{array}（15）

\begin{array}{cc}\sum _{P^{\text{'}}\in P-p}{H}_{p,p^{\text{'}}}=\mathrm{1}& \forall p\in P\end{array}（16）

\sum _{P\in P-p^{\text{'}}}{H}_{p,p^{\text{'}}}=\mathrm{1}\forall p^{\text{'}}\in P（17）

\begin{array}{cc}{H}_{p,p^{\text{'}}}+H_{p^{\text{'}},p}\le \mathrm{1}& \forall p\in P,p\in P\end{array}（18）

\begin{array}{cc}{C}_p\ge C_{i,N^S}{G}_{i,p}+A{T}_p& \forall i\in I,p\in P\end{array}（19）

\begin{array}{cc}{C}_{p^{\text{'}}}\ge C_p+A{T}_{p^{\text{'}}}+L(\mathrm{1}-H_{p,p^{\text{'}}})& \forall i\in I,p\in P,p^{\text{'}}\in P\end{array}（20）

\begin{array}{cc}{S}_{i,j}\ge \mathrm{0},C_{i,j}\ge \mathrm{0}& \forall i\in I,j\in J\end{array}（21）

\begin{array}{cc}{S}_p\ge \mathrm{0},C_p\ge \mathrm{0}& \forall p\in P\end{array}（22）

式（3）为工件绑定约束，确保每个工件严格在指定工厂加工；式（4）～式（6）为工序完整性约束，确保每个工件所有加工阶段在同一个工厂连续加工完成；式（7）、式（8）为单资源分配约束，限定每个工件的所有工序阶段只能由单一工人—机器组成；式（9）表示所有阶段的每个工件需按照给定顺序加工；式（10）为机器冲突规避约束，保证同时段单台机器仅加工一个工件；式（11）保证一个工人一次仅加工一个工件；式（12）、式（13）确保机器中有紧前和紧后的工件，防止出现加工时间浪费；式（15）确保任何时间段的工人均只能加工一个工件；式（16）～式（18）为产品时序约束，维护装配线产品的先后关系并保证每个产品都有紧前和紧后的产品；式（19）表示装配触发条件，要求产品所有组件完工后方可启动装配；式（20）保证任意两个产品之间的装配时间不重叠。

1.3 DAHFSSP-DRC问题的知识

引用文献［19］提出的两种知识设计KDIG算法。

知识1（K1）：将属于同一产品的工件分配到不同的工厂，有助于提前产品的开始装配时间。

知识2（K2）：如果属于同一产品的工件在每个工厂中一起分配，则该产品的组装可更早开始。

2 KDIG算法求解DAHFSSP-DRC

IG算法是一种简单的迭代搜索方法，易于编码和理解。本文以IG算法为主体框架，并结合问题知识设计高效的策略，从而提出KDIG算法。KDIG算法主要由基于知识的初始化策略、破坏和重构，以及基于Q-learning的变邻域局部搜索、验收准则组成。图1给出KDIG算法的主要流程。

2.1 编码方式

DAHFSSP-DRC的加工部分包含4个子问题：①工件的工厂分配；②工件的加工顺序；③工件的机器分配；④工人分配。组装阶段只涉及产品的装配顺序。采用完整编码结构即每个编码对应一个子问题导致解空间过大。因此，采用部分编码结构表示每个解^［18］。具体而言，编码由N_F个部分组成，每个部分对应一个工厂并包含表示该工厂在加工阶段的工件加工顺序。\mathit{\pi }=({\mathit{\pi }}_{\mathrm{1}},{\mathit{\pi }}_{\mathrm{2}},\cdots ,{\mathit{\pi }}_{N_{\mathrm{F}}})为DAHFSSP-DRC的一个可行解，其中，π_f 为加工阶段分配给工厂f的部分工件加工编码（排序见图2），其中，F₁、F₂分别表示工厂1和工厂2。虽然 π 只能表示所有工件在加工阶段的工厂分配和工件加工排序，但能降低解空间的复杂度，避免无效搜索。

2.2 解码方式

优秀的解码可保证解的质量，将解码分为加工和装配两部分。在加工部分，每个阶段所有工件的加工顺序采用最早完工时间规则^［20］。在第一阶段，所有工件都按照解决方案 π 中的顺序加工。在后续阶段，所有工件将根据上一阶段的完成时间按升序排序。每个阶段采用机器负载平衡规则分配机器，采用工人负载平衡规则分配工人。每个阶段的工件采用左移解码策略对解进行解码^［18］。通过这种策略，能尽早加工满足机器约束和工人约束的工件。左移解码策略解码的步骤如下：

1）根据最早完工时间规则获取每个阶段的工件加工顺序后，根据加工顺序对所有工件采用基于机器负载平衡规则，对所有工人采用工人负载平衡规则，得到加工机器k和工人w。

2）在机器k和工人w上从左到右依次求出空闲时间，然后根据下式

\left.\begin{array}{l}\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\{B_{f,k}^{(u_{\mathrm{1}})},B_{f,w}^{(u_{\mathrm{2}})},\mathrm{0}\}+T_{i,j,f,k,w}\le \\ \mathrm{m}\mathrm{i}\mathrm{n}\{E_{f,k}^{(u_{\mathrm{1}})},E_{f,w}^{(u_{\mathrm{2}})}\}j=\mathrm{1}\end{array}\\ \begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\{B_{f,k}^{(u_{\mathrm{1}})},B_{f,w}^{(u_{\mathrm{2}})},C_{i,j-\mathrm{1}}\}+T_{i,j,f,k,w}\le \\ \mathrm{m}\mathrm{i}\mathrm{n}\{E_{f,k}^{(u_{\mathrm{1}})},E_{f,w}^{(u_{\mathrm{2}})}\}j=\mathrm{2,3},\cdots \end{array}\end{array}\right\}（23）

式中：B_{f,k}^{(u_{\mathrm{1}})}、E_{f,k}^{(u_{\mathrm{1}})}分别为工厂f中机器k的第u₁个空闲时段的开始时间和结束时间；B_{f,w}^{(u_{\mathrm{2}})}、E_{f,w}^{(u_{\mathrm{2}})}分别为工厂f中工人w的第u₂个空闲时段的开始时间和结束时间。

确定判断是否可以将工件O_i，j 插入空闲。因此，工件O_i，j 的加工起始时间为

S_{i,j}=\left\{\begin{array}{ll}\mathrm{m}\mathrm{a}\mathrm{x}\{B_{f,k}^{(u_{\mathrm{1}}^{\mathrm{\text{'}}})},B_{f,w}^{(u_{\mathrm{2}}^{\mathrm{\text{'}}})},\mathrm{0}\}& j=\mathrm{1}\\ \mathrm{m}\mathrm{a}\mathrm{x}\{B_{f,k}^{(u_{\mathrm{1}}^{\mathrm{\text{'}}})},B_{f,w}^{(u_{\mathrm{2}}^{\mathrm{\text{'}}})},C_{i,j-\mathrm{1}}\}& j=\mathrm{2,3},\cdots \end{array}\right.（24）

式中：u{}_{\mathrm{1}}^{\text{'}}、u{}_{\mathrm{2}}^{\text{'}}分别为机器k和工人w的第一个空闲时段，并满足式（23）。

装配部分同样采用最早完工时间规则确定所有产品的装配顺序。图3所示为一个解码示例。

2.3 基于知识的初始化策略

基于上述编码，在NEH^［21］的框架中使用K1和K2，设计了KD-NEH策略生成初始解^［18］。为反映知识K1、K2对解决方案的重要性差异，定义重要性权重：

\lambda =N_{f,p}^a{(\sum _{j,j_{\mathrm{1}}\in I_p}{D}_{j,j_{\mathrm{1}}})}^b（25）

式中：N_f，p 为工厂f加工产品p的工件数；D_{j,j_{\mathrm{1}}}为产品I_p 的工件j与工件j₁的距离；a、b分别为K1和K2的权重因子。

N_f，p 越小，同一产品在各个工厂的加工越分散；D_{j,j_{\mathrm{1}}}越小，同一产品在一个工厂内的分配越集中。

NEH的主要目的是将工件分配到完工时间最短的“位置”，KD-NEH的主要目的是将工件分配到权重与完工时间乘积最小的“位置”。图4展示了基于知识的初始化策略，其中假设a、b为1，找出权重与完工时间乘积最小的“位置”依次插入工件。

2.4 基于知识的破坏和重构

破坏和重构是传统IG算法的一个重要组成部分，即从一个完整的解决方案先移除部分工件，再通过NEH重新插入到新的解决方案。为增强KDIG的探索能力，在重新插入工件时采用KB-NEH方法而不是NEH方法^［18］。算法1给出了基于知识的破坏和重构伪代码：

2.5 基于Q-learning的变邻域局部搜索

2.5.1 基于关键产品的局部搜索

考虑到问题特征，设计了4种基于产品的局部搜索算子（N1~N4）。为更好地表述局部搜索，定义关键产品P_c即所有产品中具有最大T_TD的产品。

N1：随机互换P_c中的2个工件，为减少计算，将生成解中的N_c-1个解作为最佳解，其中，N_c为关键产品P_c的工件总数。

N2：从P_c中随机选择一个工件，并插入P_c中的其他位置，从生成的N_c-1个解中选择最佳解。

N3：在P_c中随机选择一个工件与P_c外的工件交换，从生成的N-N_c个解中选择最佳解。

N4：从P_c外随机选择一个工件，并插入P_c所有可能的位置，从生成的N-N_c个解中选择最佳解。

2.5.2 Q-Learning策略

采用Q-Learning机制使个体在更新时选择最合适的搜索算子，以克服随机选择的缺点^［22］。对于单目标问题，最直观的评价指标为解 π 的质量，根据解的质量判断局部搜索前后的个体优劣。

状态集合：KDIG算法中，状态空间的定义是选择动作的关键。不同时间的状态集不同对行动的选择有很大影响。令s_υ 表示第υ种状态，如果个体在执行局部搜索后的解得到改进，则s_υ =1，否则s_υ =0。

动作集合：令a_ψ 表示第ψ个动作。调度过程中，智能体根据当前状态选择动作。KDIG算法中，动作集为N1~N4。

选择策略：在采用ε贪婪策略选择动作，对应数学表达式为

ε=1-0.9C_URT/M_AXT（26）

式中：C_URT为当前的CPU运行时间；M_AXT为最长的CPU运行时间。

奖励函数：在执行动作（N1～N4）后，个体可获得奖励。KDIG算法中，奖励R根据最大TTD计算：

（27）

式中：{\pi }^{\mathrm{*}}、{\pi }^{\text{'}}分别为搜索前后的解质量。

Q值最后的更新公式为

Q_t+1（s_t， a_t ）= （1-β）Q_t （s_t， a_t ）+α（R_t+1+Γmax（s₊₁， a））（28）

式中：β为学习因子，β∈［0，1］；R_t+1为t+1时刻的奖励；Γ为衰减因子，Γ∈［0，1］；Q_t （s_t，a_t ）表示t时刻、状态s_t 下执行动作a_t 的所获得的Q值。

Q-learning算法有助于个体在进化时自适应选择合适的搜索算子，充分利用各搜索算子的性能，引导种群个体向更好的方向搜索，加快收敛。算法2给出了基于Q-learning的变邻域局部搜索伪代码：

2.6 接收准则

采用模拟退火接受准则^［23］决定是否接受新的解决方案。模拟退火算法中的温度为

T=\frac{T_{\mathrm{0}}}{\mathrm{10}N{N}_{\mathrm{S}}}\sum _{i\in I}\sum _{j\in S}{\overline{t}}_{i,j}^{\mathrm{p}}（29）

式中：T₀为温度系数；{\overline{t}}_{i,j}^{\mathrm{p}}为工件i在阶段j的平均处理时间。

提出策略：如果0～1之间的随机数r满足r\le \mathrm{e}\mathrm{x}\mathrm{p}(T_{\mathrm{T}\mathrm{D}}(\mathit{\pi })-T_{\mathrm{T}\mathrm{D}}({\mathit{\pi }}^{\text{'}}))/T，则将较差解 π′代替当前解 π （对应概率为r），从而帮助KDIG算法跳出局部最优。

3 实验比较与分析

3.1 实验设置

为评估KDIG算法解决DAHFSSP-DRC的性能，使用实例进行测试，其中，N∈｛20，40，60｝，N_P∈｛2，4，6｝，N_S∈｛2，4，6｝，N_F∈｛2，4，6｝。4个参数不同组合可生成81个大型实例。实例的加工时间是区间［1，200］内的随机数。每个产品中的组成工件随机选择。每个阶段（生产中的一个特定工序或加工步骤）的工人固定为2人。每个阶段使用的机器编号均从2、3中随机抽取。产品的装配时间T_{\mathrm{A}}={\overline{T}}_{\mathrm{m}}{R}_{\mathrm{1}}，其中，{\overline{T}}_{\mathrm{m}}为加工部分的平均加工时间，R₁为［0.1，0.2］内随机数。每个产品的交货日期T_{\mathrm{D}}={\overline{T}}_{\mathrm{m}}{R}_{\mathrm{2}}/N_{\mathrm{F}}，其中，R₂为［0.5，0.6］内随机数。算例已上传，通过链接https：∥github.com/CUGYU/DAHFSSP DRCdata可获取。

所有实例的每个算法都重复运行20次，停止准则为CPU最长运行时间M_AXT=0.1NN_SN_FN_P。评价指标为平均相对偏差

A_{\mathrm{R}\mathrm{P}\mathrm{D}}=\frac{\mathrm{1}}{R}{\displaystyle \sum _{i=\mathrm{1}}^R}\frac{C_i-C_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}{C_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}（30）

式中：C_i 为KDIG算法在第i次测试中获得的目标值；C_best为测试获得的最小目标值。

3.2 参数校准

采用文献［24］的实验设计方法，详细分析参数对所提算法的影响，其中，学习因子β∈｛0.1，0.2，0.3，0.4｝，衰减因子Γ∈｛0.5，0.6，0.7，0.8｝，温度系数T₀∈｛0.4，0.8，1.2，1.6｝，权重因子a，b∈｛0.5，1.5，2.0｝。上述参数的组合总数为576，随机选择60个组合的算例校准参数。每个实例在1个参数组合下运行20次，比较20次结果的A_RPD。实验结果采用多元方差分析（analysis of variance，ANOVA）进行分析，验证参数之间的交互作用是否具有统计学意义。表2所示为多元方差的分析结果。

如果p-value小于阈值0.05，则对应的2个变量存在显著差异。如表2所示，学习因子β对应的F-ratio在所有测试变量中最大，对算法有明显的影响。KDIG算法参数主效应如图5所示。结合表2和图5得到KDIG算法的参数取值：β=0.3，Γ=0.8，T₀=1.2，a=1.5，b=2.0。

3.3 组成成分分析

为证明KDIG算法中各个策略的有效性，设计变体KDIG1～KDIG3与KDIG进行对比实验。其中，KDIG1采用NEH策略初始种群，其他策略保持不变；KDIG2采用NEH插入方法替换基于知识的破坏和构建方式，其他策略保持不变；KDIG3去除Q-learning机制，其他策略保持不变。

表3给出了KDIG算法及其变体在81个大规模实例的A_RPD（KDIG算法及其变体对每个实例各自独立执行20次的结果），最优结果以粗体显示。为分析KDIG算法与其变体是否具有显著差异，进行了Wilcoxon检验，结果见表4，其中，R⁺表示结果可取，R^-则相反。图6所示为KDIG算法及其变体算法的结果区间图。

分析表3和图6可知KDIG算法优于变体。Wilcoxon检验得到的p-value均小于0.05，证实KDIG算法与其变体存在显著差异。对比KDIG1和KDIG可知，在传统NEH策略中添加问题知识可提高算法的性能。KDIG3在所有变体中表现最差，说明基于Q-learning的变邻域局部搜索对KDIG算法性能的影响最大。综上可得，所提策略对KDIG算法解决DAHFSSP-DRC都有效，但不同策略对KDIG算法的性能有不同程度的影响。

3.4 算法比较

为证明KDIG算法的有效性，将其与算法KBIG^［18］、HDIWO^［25］、IG_VNS^［26］、MNIG^［27］和WWO^［28］进行比较。分别采用6种算法对每个实例各自独立执行20次，获取对应的A_RPD。由表5可知KDIG算法在大多数组上的结果明显优于其他比较算法。

为分析KDIG算法与对比算法是否具有显著差异，进行Wilcoxon检验，结果见表6，所有的p-value均小于0.05，这表明KDIG算法与其他算法差异显著。如图7所示，KDIG算法的A_RPD均最小，再次验证KDIG算法的最优性。

为进一步验证KDIG算法的收敛性，给出两个不同规模算例的收敛曲线。图8a为算例N=20，N_S=N_F=N_F=2的收敛曲线，所有算法初始解的差距不大，但KDIG算法的下降趋势最为明显，说明其优势较大。图8b的结果与图8a类似， KDIG算法在收敛性方面也是最优。由此可得，KDIG算法优于算法KBIG、HDIWO、IG_VNS、MNIG和WWO。

4 结论

针对以最小化总延迟为目标的DAHFSSP-DRC求解，设计了一种KDIG算法。初始化阶段，采用KD-NEH启发式初始化策略生成初始解决方案；破坏和重构阶段，设计基于知识的破坏和构造策略，以提高勘探能力；局部搜索阶段，提出基于Q-learning的变邻域局部搜索，以提高开发能力。在81个大型实例上进行了KDIG算法与其他5种算法的比较实验。实验结果表明，KDIG算法优于其他算法。

参考文献

[1] SHAO Zhongshi， SHAO Weishi， PI Dechang. LS-HH： a Learning-based Selection Hyper-heuristic for Distributed Heterogeneous Hybrid Blocking Flow-shop Scheduling［J］. IEEE Transactions on Emerging Topics in Computational Intelligence， 2023， 7（1）： 111-127.

[2] ZHANG Wenqiang， LI Chen， GEN M， et al. A Multiobjective Memetic Algorithm with Particle Swarm Optimization and Q-learning-based Local Search for Energy-efficient Distributed Heterogeneous Hybrid Flow-shop Scheduling Problem［J］. Expert Systems with Applications， 2024， 237： 121570.

[3] DI Yuanzhu， DENG Libao， ZHANG Lili.A Collaborative-learning Multi-agent Reinforcement Learning Method for Distributed Hybrid Flow Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2024， 91： 101764.

[4] LIU Feige， LI Guiling， LU Chao， et al. A Tri-individual Iterated Greedy Algorithm for the Distributed Hybrid Flow Shop with Blocking［J］. Expert Systems with Applications， 2024， 237： 121667.

[5] CUI Hanghao， LI Xinyu， GAO Liang， et al. Multi-population Genetic Algorithm with Greedy Job Insertion Inter-factory Neighbourhoods for Multi-objective Distributed Hybrid Flow-shop Scheduling with Unrelated-parallel Machines Considering Tardiness［J］. International Journal of Production Research， 2024， 62（12）： 4427-4445.

[6] SHAO Weishi， SHAO Zhongshi， PI Dechang. A Network Memetic Algorithm for Energy and Labor-aware Distributed Heterogeneous Hybrid Flow Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2022， 75： 101190.

[7] 魏光艳， 叶春明. 分布式多柔性装配作业车间调度问题研究［J］. 中国机械工程， 2023， 34（20）： 2442-2455.

[8] WEI Guangyan， YE Chunming. Research on Distributed and Multi-flexible Assembly Job-shop Scheduling Problems［J］. China Mechanical Engineering， 2023， 34（20）： 2442-2455.

[9] 曹阳华， 孔繁森. 基于装配线平衡的U形装配线生产效率研究［J］. 中国机械工程， 2015， 26（14）： 1908-1915.

[10] CAO Yanghua， KONG Fansen. Study on Production Efficiency of U-shaped Assembly Line Based on Assembly Line Balancing［J］. China Mechanical Engineering， 2015， 26（14）： 1908-1915.

[11] 魏书鹏， 唐红涛， 李西兴， 等. 考虑双资源约束的柔性机械加工车间逆调度问题研究［J］. 中国机械工程， 2024， 35（3）： 457-471.

[12] WEI Shupeng， TANG Hongtao， LI Xixing， et al. Dual-resource Constrained Flexible Machining Workshop Inverse Scheduling Problem［J］. China Mechanical Engineering， 2024， 35（3）： 457-471.

[13] 梁向檩， 宋豫川， 雷琦， 等. 考虑工人数量配置优化的柔性作业车间调度问题研究［J］. 中国机械工程， 2023， 34（17）： 2065-2076.

[14] LIANG Xianglin， SONG Yuchuan， LEI Qi， et al. Research on Flexible Job-shop Scheduling Problems Considering Optimization of Worker Number Allocation［J］. China Mechanical Engineering， 2023， 34（17）： 2065-2076.

[15] 张维存， 顾洪羽. 一人多机模式下考虑相似学习效应的车间调度问题［J］. 中国机械工程， 2023， 34（14）： 1701-1709.

[16] ZHANG Weicun， GU Hongyu. Job-shop Scheduling Problems Considering Similar Learning Effect in One-worker and Multiple-machine Partterns［J］. China Mechanical Engineering， 2023， 34（14）： 1701-1709.

[17] RUIZ R， STÜTZLE T. A Simple and Effective Iterated Greedy Algorithm for the Permutation Flowshop Scheduling Problem［J］. European Journal of Operational Research， 2007， 177（3）： 2033-2049.

[18] JING Xuelei， PAN Quanke， GAO Liang， et al. An Effective Iterated Greedy Algorithm for a Robust Distributed Permutation Flowshop Problem with Carryover Sequence-dependent Setup Time［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（9）： 5783-5794.

[19] ZOU Wenqiang， PAN Quanke， MENG Leilei， et al. An Effective Self-adaptive Iterated Greedy Algorithm for a Multi-AGVs Scheduling Problem with Charging and Maintenance［J］. Expert Systems with Applications， 2023， 216： 119512.

[20] QIN Haoxiang， HAN Yuyan， ZHANG Biao， et al. An Improved Iterated Greedy Algorithm for the Energy-efficient Blocking Hybrid Flow Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2022， 69： 100992.

[21] ZHAO Fuqing， XU Zesong， WANG Ling， et al. A Population-based Iterated Greedy Algorithm for Distributed Assembly No-wait Flow-shop Scheduling Problem［J］. IEEE Transactions on Industrial Informatics， 2023， 19（5）： 6692-6705.

[22] KARIMI-MAMAGHAN M， MOHAMMADI M， PASDE LOUP B， et al. Learning to Select Operators in Meta-heuristics： an Integration of Q-learning into the Iterated Greedy Algorithm for the Permutation Flowshop Scheduling Problem［J］. European Journal of Operational Research， 2023， 304（3）： 1296-1330.

[23] YU Fei， LU Chao， ZHOU Jiajun， et al. Mathematical Model and Knowledge-based Iterated Greedy Algorithm for Distributed Assembly Hybrid Flow Shop Scheduling Problem with Dual-resource Constraints［J］. Expert Systems with Applications， 2024， 239： 122434.

[24] YANG Yahong， LI Xun. A Knowledge-driven Constructive Heuristic Algorithm for the Distributed Assembly Blocking Flow Shop Scheduling Problem［J］. Expert Systems with Applications， 2022， 202： 117269.

[25] RUIZ R， MAROTO C. A Genetic Algorithm for Hybrid Flowshops with Sequence Dependent Setup Times and Machine Eligibility［J］. European Journal of Operational Research， 2006， 169（3）： 781-800.

[26] NAWAZ M， ENSCORE E E， HAM I. A Heuristic Algorithm for the M-machine， N-job Flow-shop Sequencing Problem［J］. Omega， 1983， 11（1）： 91-95.

[27] ZHAO Fuqing， HU Xiaotong， WANG Ling， et al. A Reinforcement Learning Brain Storm Optimization Algorithm with Learning Mechanism［J］.Knowledge Based Systems，2022，235：107645.

[28] KOU Lei， WANG Yukuan， ZHANG Fangfang， et al. A Chaotic Simulated Annealing Genetic Algorithm with Asymmetric Time for Offshore Wind Farm Inspection Path Planning［J］. International Journal of Bio-Inspired Computation， 2025， 25（2）： 69-78.

[29] SMITH J R， LARSON C. Statistical Approaches in Surface Finishing. Part 3. Design-of-experiments［J］. Transactions of the IMF， 2019， 97（6）： 289-294.

[30] SANG Hongyan， PAN Quanke， LI Junqing， et al. Effective Invasive Weed Optimization Algorithms for Distributed Assembly Permutation Flowshop Problem with Total Flowtime Criterion［J］. Swarm and Evolutionary Computation， 2019， 44： 64-73.

[31] SHAO Weishi， PI Dechang， SHAO Zhongshi. Optimization of Makespan for the Distributed No-wait Flow Shop Scheduling Problem with Iterated Greedy Algorithms［J］. Knowledge-Based Systems， 2017， 137： 163-181.

[32] SHAO Weishi， SHAO Zhongshi， PI Dechang. Modeling and Multi-neighborhood Iterated Greedy Algorithm for Distributed Hybrid Flow Shop Scheduling Problem［J］. Knowledge-Based Systems， 2020， 194： 105527.

[33] ZHAO Fuqing， SHAO Dongqu， WANG Ling， et al. An Effective Water Wave Optimization Algorithm with Problem-specific Knowledge for the Distributed Assembly Blocking Flow-shop Scheduling Problem［J］. Knowledge-Based Systems， 2022， 243： 108471.

基金资助

国家重点研发计划(2023YFC3011100)

国家自然科学基金(62373146)

湖南省自然科学基金(2022JJ30265)

湖南省自然科学基金(2023JJ40286)

湖南省人才托举工程青年人才项目(2022TJ-Q03)