基于两阶段混合迭代贪婪算法的分布式异构非置换流水车间调度
来源：计算机集成制造系统杂志2025年第8期北京时间：
作者：熊福力, 陈思远, 熊宁馨, 师江波
单位：1.西安建筑科技大学信息与控制工程学院2.中国石油大学(北京)克拉玛依校区石油学院
摘要：针对分布式异构非置换流水车间调度问题,建立以最小化总拖期惩罚费用为目标的混合整数线性规划模型。鉴于问题的复杂性,在深入分析置换与非置换解关系的基础上,提出了一种两阶段混合迭代贪婪算法。该算法采用了置换解搜索阶段和非置换解搜索阶段的两阶段递阶搜索策略。在第一阶段中,首先采用改进NEH启发式生成高质量初始解;随后,提出一种扰动策略以避免算法陷入局部最优;最后,为提高求解质量,提出两种不同结构的自适应局部搜索策略,进而生成一个高质量置换解。第二阶段则通过改变某些机器上的工件排序来改进第一阶段产生的置换解。在第二阶段中,首先运用贪婪插入策略进行扰动;然后,交替运用两种不同工件交换顺序的相邻交换局部搜索策略对新解进行改进。扰动过程和局部搜索过程迭代进行,以加强对解空间的探索。最后,通过不同规模的数据实验和与对比算法的比较分析,验证了所提算法的高效性。
关键词：分布式异构非置换流水车间调度,混合整数线性规划,两阶段递阶策略,混合迭代贪婪算法
基金资助：国家自然科学基金资助项目(61473216);陕西省自然科学基础研究计划资助项目(2023-JC-YB-582)。
