Abstract: 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.

Key words: job shop scheduling, multi-operation precise joint movement, neighborhood structure, hybrid evolutionary algorithms, diversified search

摘要： 针对作业车间调度问题,以最小化最大完工时间为优化目标,提出一种基于多工序精确联动邻域结构的混合进化算法。从理论上给出了关键块中工序无效移动的判定条件,据此设计了3对工序精确联动的邻域结构。为避免算法过早收敛,引入基于邻域惩罚的交叉父本匹配选择算子与基于动态惩罚阈值的种群更新策略。通过与其他先进算法在车间调度问题基准算例上进行对比实验,验证了所提算法的有效性与稳定性。

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