链上镖师 / Chain Biaoshi
CIE|SMT细胞制造中的产品族与AGV协同调度：生产运输一体化优化
知识引导进化算法同步处理产品族排序、生产单元分配与跨单元运输
论文面向SMT细胞制造系统，将产品族生产排序、生产单元分配与AGV跨单元运输纳入同一调度模型，以最小化最大完工时间。
- 01：研究对象是需要经过多个连续生产流程的PCB产品族。
- 02：模型同时决定产品族排序、族内作业顺序、生产单元分配和AGV派遣。
- 03：MILP模型用于小规模实例建模与验证，KGEA用于求解大规模组合调度问题。
- 04：实验显示KGEA在多数中大规模实例中取得更低的ARPI和更稳定的结果。
仓库、产品族与生产单元：SMT协同调度场景
论文研究细胞制造系统中的集成产品族生产与运输调度问题。每个生产单元由多台机器组成，PCB作业依据工艺相似性划分为产品族，产品族需要依次完成多个生产流程，AGV负责仓库与生产单元之间以及不同生产单元之间的转运。
图1 细胞制造系统中的生产与运输协同结构（来源：Fig. 1）
图2 仓库与生产单元之间的空间关系（来源：Fig. 2）
产品族跨流程移动：调度对象如何形成完整作业链
问题目标是最小化最大完工时间。每个产品族在同一流程内需要连续加工，族内作业保持顺序，产品族完成前一流程后立即请求AGV前往指定生产单元。设置时间发生在生产单元首次加工某个产品族或切换产品族时，族内连续作业之间无需重复设置。
图3 示例实例的调度甘特图（来源：Fig. 3）
图4 产品族的AGV运输过程（来源：Fig. 4）
从完工时间到运输可行性：IGPTSP模型的约束骨架
MILP模型以最大完工时间为目标，将生产时间、设置时间、跨流程运输时间、生产单元容量和AGV可用性统一纳入约束。模型要求每个产品族在每个流程分配一个生产单元，生产流程按顺序执行，AGV单次运输只能承载一个产品族，机器加工禁止抢占和中断。
图6 示例调度中的关键路径（来源：Fig. 6）
11. 决定各流程的产品族顺序与族内作业顺序
22. 为产品族分配各流程对应的生产单元
33. 为跨流程运输任务分配AGV并计算到达时间
44. 联合检查机器容量、族间设置和流程先后关系
55. 以全部作业完成时间中的最大值计算makespan
关键路径如何驱动KGEA搜索
KGEA将领域知识嵌入进化搜索过程。动态编码把解分为序列部分X1和分配部分X2，X1描述产品族与族内作业顺序，X2记录生产单元和AGV分配。解码阶段依据生产单元与AGV的最早可用时间生成或更新分配信息。
图8 关键路径引导的家庭级邻域结构（来源：Fig. 8）
图10 KGEA算法整体流程（来源：Fig. 10）
算法先通过关键路径分析识别影响makespan的关键操作和关键产品族，再对相关产品族开展嵌套变邻域下降搜索。订单交叉和基于记忆的重组用于利用高质量解中的交互信息，种群重启用于恢复搜索多样性，形成局部改进与全局探索相结合的搜索过程。
参数校准与组件贡献：完整算法的实验配置
作者采用正交试验校准种群规模、外部循环邻域执行次数、协作次数、重启次数、内部循环邻域执行次数和重启替换概率。25组参数组合在4个不同规模实例上分别独立运行10次，并通过归一化ARPI汇总跨规模响应值。
表5 正交试验组合及响应值（来源：Table 5）
表6 不同算法组件变体的实验结果（来源：Table 6）
完整KGEA
ARPI 0.818
实例10–4–5–3
静态编码变体
ARPI 9.995
实例10–4–5–3
从小规模精确求解到中大规模竞争比较
小规模实验中，CPLEX能够在较小问题上获得最优解，问题规模扩展到6个产品族后，求解器在1800秒时限内无法证明最优性。8个包含6个产品族的实例中，KGEA有6个实例取得优于CPLEX的解。中大规模实验中，KGEA在多数问题上取得最低ARPI，并保持较低标准差。
图12 不同算法组件变体的置信区间（来源：Fig. 12）
图13 不同元启发式算法的置信区间与小提琴图（来源：Fig. 13）
组件分析显示，关键路径引导的嵌套VND、协作过程、种群重启和动态X2编码共同支撑KGEA的解质量与稳定性。完整KGEA的结果分布集中，波动幅度低于多数对比算法。
家庭数、生产单元与AGV数量变化下的性能边界
交互分析考察产品族数量、生产单元数量、机器数量和AGV数量变化对算法表现的影响。KGEA的ARPI随问题规模增加保持相对稳定，其他元启发式算法的波动更明显。该结论适用于论文设定的细胞制造系统结构、参数范围、两流程协同和实验停止规则。
图14 算法与问题规模因素的交互图（来源：Fig. 14）
✓产品族数量、生产单元位置和各族作业数量预先已知。
✓每个生产单元具备处理两个流程的能力。
✓AGV运输时间按生产单元位置差异设定，单次运输承载一个产品族。
✓缓冲区视为无限容量，AGV路径层面的冲突影响并入运输时间。
✓论文未报告动态订单到达、有限缓冲区、抢占加工和AGV路径冲突下的外推结果。
论文：A knowledge-guided evolutionary algorithm for integrated group production and transportation scheduling with inter-cell coordination in cellular manufacturing systems
作者：Zhi-Xuan Wang，Biao Zhang，Jia-Xing Li，Lei-Lei Meng，Li-Li Liu，Ying-Li Li
期刊：Computers & Industrial Engineering
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
