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

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