迭代贪婪算法优化分布式阻塞流水车间成组鲁棒调度问题  

Optimization of iterated greedy algorithm for distributed blocking flowshop group robust scheduling problem

作　　者：王一正 王玉亭[1] 韩玉艳[1] 李寰[1] 高开周 Wang Yizheng;Wang Yuting;Han Yuyan;Li Huan;Gao Kaizhou(School of Computer Science,Liaocheng University,Liaocheng Shandong 252059,China;Macao Institute of Systems Engineering,Macao University of Science&Technology,Macao 999078,China)

机构地区：[1]聊城大学计算机学院,山东聊城252059 [2]澳门科技大学、澳门系统工程研究所,中国澳门999078

出　　处：《计算机应用研究》2025年第2期469-476,共8页Application Research of Computers

基　　金：国家自然科学基金资助项目(61973203,61803192,62106073,61966012);山东省自然科学基金资助课题(ZR2023MF022);聊城大学光岳青年创新团队资助项目(LCUGYTD2022-03)。

摘　　要：为了优化复杂生产环境中生产计划的鲁棒性,确保不同场景下生产调度的稳定性,此研究将多生产线单元制造问题抽象为分布式流水车间成组调度问题,并在此基础上考虑了实际生产中常见的零缓冲区、加工时间不确定性和交付时间窗口等约束。首先,构建了以鲁棒性为优化目标的混合整数线性规划模型并使用Gurobi求解器验证其正确性;然后,提出了一种改进的空闲时间插入方法以适应阻塞约束和成组约束;接着,将上述改进空闲时间插入方法融入到自适应协同迭代贪婪算法中,该算法针对问题的多场景、问题求解的时间复杂度等,分别设计了有针对性的初始化方法、自适应破坏策略以及快速重构和局部搜索方法。最后,在生成的810个实例中,与其他高效的元启发式算法相比,所提出的算法在有限的时间内得到了鲁棒最优解。研究结果表明,该算法能够应对不确定因素和复杂的约束,在解决各种规模的问题上都表现出了良好的性能。ed the multi-production line cellular manufacturing problem into a distributed flowshop group scheduling problem,incorporating common constraints such as zero buffer zones,processing time uncertainties,and delivery time windows.Firstly,the study developed a mixed-integer linear programming model with robustness as the optimization objective and validated it using the Gurobi solver.Then,this paper proposed a modified idle time insertion method to meet blocking and grouping constraints.It designed an adaptive collaborative iterated greedy algorithm,which was driven by the modified idle time insertion method,to address this problem.This algorithm featured an initialization method that accounted for the intrinsic connections of multiple scenarios,an adaptive destruction strategy,and accelerated reconstruction and local search methods.Finally,in 810 generated instances,the proposed algorithm achieved better solutions within limited time compared to other efficient metaheuristic algorithms.The results demonstrate that the algorithm effectively handles uncertainties and complex constraints,showing strong performance across various problem sizes.

关 键 词：分布式调度 成组调度 不确定加工时间 交付时间窗口 迭代贪婪算法 空闲时间插入 

分 类 号：TP13[自动化与计算机技术—控制理论与控制工程]