A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

技术摘要：一种基于关键路径驱动双邻域搜索的柔性车间调度遗传算法

问题定义
本文研究了柔性车间调度问题（FJSP），这是一个在现代制造业中广泛存在的强 NP-hard 优化挑战。与操作具有固定机器分配的经典车间调度问题（JSP）不同，FJSP 允许每个操作从一组候选备选机器中选择任何一台进行加工，且加工时间可能各不相同。主要目标是最小化最大完工时间（$C_{max}$），即所有作业的最大完成时间。该问题涉及确定每个操作的机器选择以及每台机器上的加工顺序，同时必须满足前置约束和机器可用性。

方法论：HGVNSA
作者提出了一种混合遗传变邻域搜索算法（HGVNSA），该算法将用于全局探索的遗传算法（GA）与用于局部开发的关键路径驱动变邻域搜索（VNS）相结合。

1. 编码与解码： 解由两层编码表示：操作序列（OS）向量和机器选择（MS）向量。采用主动解码策略来生成可行调度方案。
2. 种群初始化： 为了平衡质量与多样性，初始种群采用混合策略生成：全局选择（60%，最小化全局负载增量）、局部选择（30%，平衡作业内的负载）以及随机选择（10%）。
3. 遗传操作：
   • 交叉： 引入了一种基于路径重联（Path-Relinking, PR）的交叉算子。它不是随机交换基因，而是系统地将一个父代解转化为另一个父代解，通过记录并评估中间解来利用父代之间的搜索空间。
   • 变异： 一种自适应变异机制根据个体适应度和世代数调整概率。使用了两种变异类型：OS 变异（打乱操作顺序）和 MS 变异（改变机器分配）。
   • 多样性保持： 采用基于汉明距离（Hamming distance）的策略来维持种群多样性并防止过早收敛。
4. 关键路径驱动的双邻域 VNS： 嵌入在 GA 框架内的这种局部搜索专注于位于关键路径（析取图中路径最长的路径）上的操作。它利用了两个互补的邻域结构：
   • N8 邻域： 优化同一台机器上的操作序列。它扩展了传统的 N5-N7 移动，允许关键操作移动到关键块之外的端点或块的前后位置。
   • k-插入邻域： 将关键操作重新分配到不同的机器。这涉及遍历备选机器并将操作插入到可行位置，同时检查是否存在循环依赖。
   • 搜索策略： VNS 过程优先考虑 N8 邻域（计算成本较低），仅在未发现改进时才切换到 k-插入（成本较高，搜索范围更广），从而确保效率与探索深度之间的平衡。

核心贡献
论文概述了五项主要贡献：

1. 混合框架： 建立了一个协同的“先全局探索，后局部开发”框架，有效地平衡了求解精度与计算效率。
2. 双邻域集成： 这是首次将 N8 和 k-插入邻域集成到统一的 FJSP VNS 框架中。这种结合同时解决了机器内排序和机器间重分配的问题，显著增强了局部搜索能力。
3. 增强型遗传算子： 引入的路径重联交叉和自适应变异概率增强了算法探索解空间的能力并保持了收敛稳定性。
4. 基准测试表现： 在 Brandimarte MK 基准测试集上，HGVNSA 在 10 个实例中的 6 个（MK01-MK04, MK08-MK09）达到了已知最优解，并且在对比算法（HGWO, HLO-PSO, HA, SLGA, ISLGA）中实现了最低的平均相对百分比偏差（RPD，为 0.06%）。
5. 实际应用： 该算法应用于 A 公司的齿轴加工场景。与传统的遗传算法相比，HGVNSA 将生产效率提高了 8.81%，证明了其工程实用性。

结果与验证

• 基准测试： 在 MK01-MK10 实例上的广泛实验表明，HGVNSA 在解质量和稳定性方面均优于对比算法。消融实验证实，移除 VNS 组件、双邻域结构或自适应机制都会导致性能显著下降（例如，移除 VNS 使 MK02 的平均完工时间从 26 增加到 30.4）。
• 案例研究： 在涉及 10 个作业、59 个操作和 15 台机器的 A 公司案例研究中，该算法将完工时间从 522（传统 GA）降低到了 476。
• 收敛性： 收敛性分析表明，虽然其他算法在初始快速收敛后趋于停滞，但 HGVNSA 通过其局部搜索机制持续优化解，在后期迭代中突破了局部最优。

意义
论文声称 HGVNSA 为 FJSP 提供了一个高效且鲁棒的解决方案框架，有效解决了平衡全局搜索与局部搜索以及设计有效邻域结构的挑战。研究验证了将关键路径驱动的局部搜索与遗传进化相结合，在理论基准和实际工业环境中均能产生卓越的结果。作者指出，这项工作为未来分布式调度以及使用深度强化学习进行智能邻域选择的研究奠定了基础，尽管他们并未声称在当前研究中已实现这些扩展。