作业车间调度的多工序精确联动邻域结构混合进化算法  

Hybrid evolutionary algorithm with multi-operation precise joint movement neighborhood structure for job shop scheduling problem

作　　者：巴智勇 袁逸萍[1] 裴国庆 王波 BA Zhiyong;YUAN Yiping;PEI Guoqing;WANG Bo(College of Mechanical Engineering,Xinjiang University,Urumqi 830017,China;Saurer Intelligent Technology Co.,Ltd.,Urumqi 830057,China)

机构地区：[1]新疆大学机械工程学院,新疆乌鲁木齐830017 [2]卓郎新疆智能机械有限公司,新疆乌鲁木齐830057

出　　处：《计算机集成制造系统》2024年第2期537-552,共16页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(71961029);新疆维吾尔自治区重点研发计划资助项目(2020B02013)。

摘　　要：针对作业车间调度问题,以最小化最大完工时间为优化目标,提出一种基于多工序精确联动邻域结构的混合进化算法。从理论上给出了关键块中工序无效移动的判定条件,据此设计了3对工序精确联动的邻域结构。为避免算法过早收敛,引入基于邻域惩罚的交叉父本匹配选择算子与基于动态惩罚阈值的种群更新策略。通过与其他先进算法在车间调度问题基准算例上进行对比实验,验证了所提算法的有效性与稳定性。Aiming at the Job Shop Scheduling problem(JSP),a Hybrid Evolutionary Algorithm with multi-operation precise joint Movement Neighborhood Structure(HEA-MNS)was proposed to optimize the maximum completion time.The judgment condition of invalid movement operation in the critical block was given theoretically,and the neighborhood structure of precise joint movement of three pairs of operations was designed accordingly.To avoid premature convergence,a cross-parent selection operator based on neighborhood penalty and a population updating strategy based on dynamic penalty threshold were introduced.By comparing HEA-MNS with other state-of-the-art algorithms on the JSP benchmark,its effectiveness and stability were proved.

关 键 词：作业车间调度 精确多工序联动 邻域结构 混合进化算法 多样化搜索 

分 类 号：TH166[机械工程—机械制造及自动化] TP181[自动化与计算机技术—控制理论与控制工程]