2024年SEVC SCI2区，双种群协同遗传算法+AGV柔性作业车间调度，深度解析+性能实测-育师

1.摘要

本文针对柔性作业车间中加工设备与 AGV 的集成调度问题以最小化完工时间为目标，构建了一个新的 MILP 模型，并提出了双种群协同遗传算法（DCGA）。该算法采用基于机器选择与工序排序的双层编码，并通过两种解码策略确定 AGV 分配，同时引入种群协同机制增强搜索能力。

2.问题描述

FJSP-AGV 问题描述为多道工序的作业需在多台可选加工设备上完成，AGV 负责作业在装卸点与各设备之间的运输，且运输时间取决于设备间距离并包含空载与载货两种状态。调度目标是在综合考虑机器选择、AGV 分配以及机器与 AGV 上的作业顺序的情况下，为每道工序同时确定最优加工设备与运输方式，从而最小化系统的最大完工时间。

FJSP-AGV模型以最小化最大完工时间为目标，型约束从工序唯一分配、运输与加工时序衔接、作业起始与结束时间、机器加工顺序以及 AGV 运输顺序等方面，完整刻画了加工与运输的协同关系；其中成对约束分别保证同一机器和同一 AGV 上工序的先后顺序一致性，并借助大 M 方法在不相关情形下自动松弛。

3.双种群协同遗传算法DCGA

DCGA 在传统遗传算法基础上引入双种群结构，通过两类采用不同解码策略的子种群独立进化并按特定规则协同交流，在保持多样性的同时加快可行解收敛并避免陷入局部最优。

编解码方案

论文采用由机器选择与工序排序构成的双层整数编码方式，在解码阶段，依据编码先确定各工序的加工设备与机器加工顺序，并设计了两种不同的 AGV 分配规则，由两个子种群分别采用以保持搜索多样性。两种解码规则均以最早到达为原则。

算子设计

DCGA选择阶段结合二元锦标赛与精英保留策略，在保证优秀个体继承的同时维持种群竞争性；交叉阶段针对双层编码分别设计算子，工序排序层采用优先工序交叉以继承父代优势并确保可行性，机器选择层采用均匀交叉以增强组合多样性；变异阶段则分别对工序排序与机器选择实施多样化扰动，通过交换、插入、逆序及重新分配等操作，增强搜索能力并避免算法陷入局部最优。

DCGA通过引入种群多样性检测与协同进化机制，在进化过程中定期检查种群中解的相似性，当个体完工时间相同且机器选择编码相似度过高时对其重新生成，以避免早熟收敛并维持多样性；同时设计了双子种群协同操作，通过跨种群选择、交叉与择优更新，使两类子种群共享优质结构信息。

4.结果展示

5.参考文献

[1] Han X, Cheng W, Meng L, 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.