论文题目：A knowledge region selection enhanced quality-diversity algorithm for real-world flexible job shop scheduling with Automated Guided Vehicles transportation

第一作者：秦浩翔 华南理工大学软件学院博士生，目前的研究兴趣包括智能制造、智能车间与智能计算、智能电网、质量-多样性算法、迭代贪婪算法、多目标优化算法、进化算法、神经网络和强化学习。

E-mail：987352978@qq.com

通讯作者：向毅 华南理工大学软件学院副教授，博士生导师、博士后合作导师。长期从事智能软件工程、演化计算、机器学习等领域的研究工作，尤其关注软件工程与人工智能的交叉学科方向。

E-mail：xiangyi@scut.edu.cn


柔性车间调度：Q-Learning 增强质量﹣多样性算法

论文摘要

柔性作业车间调度（FJSP）在现代离散制造中广泛存在，其扩展形式——考虑有限自动引导车（AGV）运输的 FJSP‑AGVs——使得任务不仅涉及工序加工，还涉及不同机器之间的物料运输。传统确切算法在规模扩展后难以在合理时间内求解，而现有启发式与机器学习方法主要将学习用于选择规则或局部搜索算子，缺乏对解集行为多样性的全面挖掘。本文针对这一问题，提出一种基于质量–多样性（Quality‑Diversity, QD） 的调度算法，通过Q‑Learning 区域选择机制在行为特征空间中智能划分区域，结合配对选择策略寻找潜在协同解，并设计了融入 AGV 运输启发规则的局部搜索。算法不仅优化完成时间，还确保解的多样性。在两类中国实厂实例和 21 个基准实例上，该方法较强基线算法使完工时间降低 12.2–30.8%，验证了基于 QD 的调度优化在实际生产中的应用潜力。

一、研究背景与问题

离散制造系统中，每个工件由多个工序组成，工序可在若干机器上加工，构成柔性作业车间调度（FJSP）问题。传统 FJSP 假定物料运输资源充足或忽略运输时间，但在现实车间中 AGV 数量有限、运输路径复杂，运输时间与机器闲置时间会显著影响总完成时间。因此，研究 FJSP‑AGVs 具有重要意义。主要难点包括：

  • 资源约束：机器和 AGV 都是有限资源，不当调度会导致长时间等待。
  • 解空间巨大：随着作业、机器和 AGV 数量增长，解的组合呈指数级增长，传统精确算法无法处理大规模实例。
  • 现有方法局限：大多数强化学习或深度学习方法只用于选择调度规则或局部搜索算子，无法利用解的行为特征指导搜索。

为此，本文提出将质量–多样性算法与Q‑Learning结合，通过引入行为特征空间来探索高质量且多样的解决方案。图1展示了带 AGV 的调度示意，每个操作既有计划开始/完成时间，又有实际执行时间；AGV 的运输行为直接影响机器的空闲与等待。

图1 FJSP‑AGVs 调度示意（取自 Fig. 1）
图1 FJSP‑AGVs 调度示意（取自 Fig. 1）

二、Q‑QD 算法框架

2.1 特征空间构建

为了在搜索过程中平衡质量与多样性，作者定义了基于两个行为特征的二维空间：

  • 机器闲置次数：反映所有机器闲置的累计次数，数值大说明资源利用率低。
  • 作业转移次数：AGV 将工件从一台机器转移到另一台机器的次数（包括往返），范围 。

这两个特征体现了加工与运输的权衡。解在特征空间中的坐标为 ；MAP‑Elites 框架为每个格子保留一条当前最优解，从而在保持多样性的同时保证高质量。

调度的目标是最小化最大完工时间（makespan），其数学定义为

其中  表示第  个作业最后一道工序的完成时间。

2.2 算法总体流程

整个算法（Q‑QD）基于 MAP‑Elites 框架并融合 Q‑Learning 区域选择机制，其主要步骤如下（图2）：

  1. 初始化与存档：随机生成一批解决方案，根据解在特征空间中的位置存入对应格子，形成初始存档。
  2. 父代选择：从存档中选出  个表现最佳的候选解作为父代1；利用 Q-Learning 选择的特征区域，再通过配对选择策略从该区域中选择协同解组成父代2。
  3. 交叉与变异：对两个父代解执行交叉和变异操作生成子代，然后将解映射到特征空间。
  4. 局部搜索：对子代应用基于领域知识的局部搜索（LS‑DK），对操作顺序、机器分配和 AGV 选择进行针对性扰动。
  5. 更新存档与 Q 表：根据新的解更新存档格子，如果新的解在同一格中目标值更优则替换；根据奖励更新 Q 表的动作价值，逐步调整区域选择策略。
图2 Q‑QD算法框架（取自 Fig. 2）
图2 Q‑QD算法框架（取自 Fig. 2）

2.3 区域选择与配对策略

区域划分：根据特征  将特征空间划分为若干区域，每个区域对应 Q‑Learning 中的一个动作。实验表明仅用  划分区域效果最佳。

Q‑Learning 策略：利用 ‑贪婪策略在区域间选择动作，随着迭代  逐渐减小。对应的 Q 值更新公式为

其中  为学习率， 为折扣因子， 为获得的即时奖励（如解的改进幅度）。

配对选择：在指定区域内随机挑选两个未被占用的格子，通过比较格子内存档的改善次数和质量，选择最有潜力的协同解进行交叉。

该设计使算法既能利用 Q‑Learning 引导到更优的行为区域，又能通过配对策略兼顾探索与利用。

2.4 基于域知识的局部搜索

局部搜索利用关键路径思想：关键路径是调度图中从开始到完成耗时最长的路径，包含机器加工与 AGV 运输。图3给出了关键路径示意，红线标出的操作和运输对总完工时间影响最大。

图3 关键路径示意（取自 Fig. 3）
图3 关键路径示意（取自 Fig. 3）

算法针对关键路径上的作业设计了三种扰动：

  • 机器分配扰动：选择关键路径中运输时间最长的操作，将其分配到备选机器中加工（图4(a)）。
  • 操作顺序扰动：在 OS 向量中交换两个作业的顺序，优先调整运输时间长的作业（图4(b)）。
  • AGV 选择扰动：在 AS 向量中重新为关键操作选择 AGV（图4(c)）。

上述操作形成新的解向量，再通过解码评估其完工时间与特征值。

图4 基于关键路径的局部搜索示意（取自 Fig. 4）
图4 基于关键路径的局部搜索示意（取自 Fig. 4）

2.5 复杂度分析

算法包括初始化和迭代两部分：

  • 初始化阶段生成  个随机解并存档，复杂度为 。
  • 迭代阶段执行  次迭代，每次选择  个父代，完成选择、交叉、局部搜索等操作，复杂度为 。

综合来看，该方法在可接受的时间内完成大规模调度问题的搜索。

三、实验设计与结果分析

3.1 实验设置

研究采用两种实际案例（中国煤机结构件车间与南京加工车间）及 21 个基准实例，工件数量从20到120不等，机器数为5、8、10台，AGV 数量有限。每种配置进行了 20 次独立实验。性能评估指标选用相对增益百分比（RPI）：

RPI 越小表示算法越优。

3.2 特征区域划分与参数敏感性

作者比较了基于作业转移次数 ()、机器闲置次数 () 以及两者联合划分区域的方法。图5显示，仅用  划分区域在 21 个实例中有 71.4% 取得最优 RPI，显著优于其他策略。这说明在 FJSP‑AGVs 中，运输约束是影响调度性能的关键因素。

图5 不同区域划分方式对RPI的影响（取自 Fig. 5）
图5 不同区域划分方式对RPI的影响（取自 Fig. 5）

通过正交实验分析了参数 （选取的精英数）、（选取的区域数）、学习率 、折扣因子  及贪婪系数 。结果表明：、、、、 时平均 RPI 最小（图6），因此实验采用该参数配置。

图6 参数对平均 RPI 的影响（取自 Fig. 6）
图6 参数对平均 RPI 的影响（取自 Fig. 6）

3.3 区域选择方法验证与消融分析

对比随机区域选择（V-RR）与 Q-Learning 区域选择（Q-QD），图7显示 Q-Learning 在 76.2% 实例中获得最好 RPI，而随机选择仅 42.9%。这表明使用强化学习引导搜索区域可显著提升性能。

图8进一步给出了去除不同组件的四种变体：删除 QD 框架（V-QD）、删除 Q-Learning（V-QL）、删除配对选择（V-I）和删除局部搜索（V-LS）。通过消融实验发现：缺少任何关键部件都会使 RPI 明显升高，其中删除局部搜索影响最大，说明基于关键路径的启发式对于快速收敛至高质量解至关重要。

图7 区域选择策略与运输启发式消融对比（取自 Fig.7 与 Fig.10）
图7 区域选择策略与运输启发式消融对比（取自 Fig.7 与 Fig.10）
图8 Q-QD 及其各变体的比较（取自 Fig.8）
图8 Q-QD 及其各变体的比较（取自 Fig.8）
图9 不同选择策略下各变体的 RPI 分布及获胜次数比较（取自 Fig.9）
图9 不同选择策略下各变体的 RPI 分布及获胜次数比较（取自 Fig.9）

3.4 综合比较与实厂案例验证

在 21 个基准实例上，Q‑QD 平均使完工时间降低 12.2–30.8%，明显优于 QD、迭代贪婪算法、深度 Q 网络辅助算法等先进方法。图10 描绘了部分实例中 Q‑QD 与其他算法的演化曲线，Q‑QD 早期即获得更好解并保持优势。

图10 部分实例的进化曲线（取自 Fig. 13）
图10 部分实例的进化曲线（取自 Fig. 13）

对于两类实际车间，作者分别构建了加工车间布局模型，如图11 所示：煤机结构件车间由 10 台机器和有限 AGV 组成，布置涉及多个加工线；南京加工车间则包含更多工序与机器。实验表明，Q‑QD 在两个车间均能显著缩短完工时间，并且通过 Q‑Learning 选择的最优区域与最终优解所在区域一致，验证了区域选择机制的合理性。

图11 机加车间布局与实例说明（取自 Fig. 14）
图11 机加车间布局与实例说明（取自 Fig. 14）

四、结论与创新点

本文针对现实柔性作业车间调度结合 AGV 运输问题，提出了Q‑Learning 区域选择增强的质量–多样性算法（Q‑QD）。主要结论和创新包括：

  • 创新的区域选择框架：将解的行为特征  映射到特征空间，利用 Q‑Learning 自适应地选择高潜力区域，解决了传统算法随机或静态选择导致的早熟收敛问题。
  • 配对选择与 MAP‑Elites 结合：通过配对选择策略保证每次交叉的解来自不同行为区域，从而在探索新解的同时维持多样性。
  • 基于关键路径的局部搜索：设计利用 AGV 运输时间的启发式规则，对操作顺序、机器分配和 AGV 选择进行针对性扰动，显著提高搜索效率。
  • 全面的实验验证：在 21 个基准实例和两类实厂数据上，Q‑QD 平均减少完工时间 12.2–30.8%，并通过消融实验验证了各模块的重要性。
  • 实践价值突出：算法在实厂案例中的表现表明，结合强化学习与质量–多样性优化可以为智能制造提供具有实际可行性的新型调度策略。

五、未来工作与启示

尽管 Q‑QD 已在大规模实例中表现出良好性能，但仍有改进空间：

  • 特征空间扩展：未来可尝试引入更多与能源消耗、碳排放等相关的行为特征，拓展算法在绿色制造中的应用。
  • 深度强化学习：替换表格式 Q‑Learning 为深度网络，以适应更复杂的特征空间和连续动作。
  • 动态调度：研究如何将 Q‑QD 应用于动态到达工件和实时交通变化的车间，进一步提升算法的鲁棒性。
  • 多目标优化：探索与总延迟、能源消耗等多目标兼顾的扩展算法，解决真实场景中的多维优化需求。


文章须知 

链上镖师团队：常文婕（AEIC）、祁园园、汪朝杰、王一航、张仁义（EIC）、张晓乐

原文链接：https://doi.org/10.1016/j.engappai.2025.113352

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。