基于混合离散状态转移算法的多目标节能无等待流水车间调度  

Multi-objective Energy-efficient No-wait Flow Shop Scheduling Based on Hybrid Discrete State Transition Algorithm

作　　者：王聪[1] 余佳英 张宏立[1] Wang Cong;Yu Jiaying;Zhang Hongli(School of Electrical Engineering,Xinjiang University,Urumqi 830047,China)

机构地区：[1]新疆大学电气工程学院,新疆乌鲁木齐830047

出　　处：《系统仿真学报》2024年第10期2345-2358,共14页Journal of System Simulation

基　　金：国家自然科学基金(52267010);新疆维吾尔自治区自然科学基金(2022D01C367,2022D01E33)。

摘　　要：针对以完工时间和总能耗为目标的节能无等待流水车间调度问题(energy-efficient no-wait flow shop scheduling problem,EENWFSP),设计一种混合离散状态转移算法(hybrid discrete state transition algorithm,HDSTA)进行求解。根据问题特性设计工序和速度矩阵的编码方式,采用启发式算法获得优质的初始解。根据EENWFSP性质,对4个离散操作算子进行任务分配,将嵌入二次状态转移的交换、移动、对称算子用于工序优化,替换算子用于机器速度优化,并在替换算子中嵌入基于关键路径的速度替换策略。设计了一种改进的破坏重构操作,用于进一步提高Pareto解的质量。通过与4种算法在测试实例上的实验结果分析,表明HDSTA在解决EENWFSP时具有较强优势。A hybrid discrete state transition algorithm(HDSTA)is designed to solve the energy�efficient no-wait flow shop scheduling problem(EENWFSP)minimizing makespan and total energy consumption.According to the characteristics of the problem,the coding method of job sequence and speed matrix is designed,and the heuristic algorithm is used to obtain the high-quality initial solution.According to the properties of EENWFSP,solving and allocating four discrete operators.The swap,shift and symmetry operators are embedded in secondary state transition are used for job sequence optimization,and the substitute operators are used for machine speed optimization.The speed substitute strategy based on critical path is embedded in the substitute operators.An improved destructive reconstruction operation is designed to further improve the quality of Pareto solution.Experimental results of four algorithms on test cases show that HDSTA has strong advantages in solving EENWFSP.

关 键 词：无等待流水车间 节能调度 状态转移算法 总能量消耗 最大完工时间 多目标优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP391.9[自动化与计算机技术—计算机科学与技术]