Abstract: HFSP was an NP-hard problem widely presented in process manufacturing systems. For HFSP aimed at minimizing makespan, an improved Jaya algorithm was proposed by combining the advantages of Jaya algorithm and Tabu search. During the iterative update phase of the algorithm, a path reconnection-based method was proposed for the discrete update of the algorithm according to the designed coding, which ensured the diversity of the population and enhanced the global search capability. To improve local search capability, a Tabu search algorithm integrating two types of neighborhood structures was proposed to further enhance the quality of solutions, and the neighborhood structures were adjusted adaptively according to the characteristics of the problem. The proposed algorithm was used to solve three types of HFSP benchmark sets. New optimal solutions are found in large-scale classic benchmark sets, which are superior to other algorithms in the current literatures in terms of solution quality, verifying the effectiveness and superiority of the proposed algorithm.

Key words: hybrid flow-shop scheduling problem(HFSP), path relink, Tabu search, makespan

摘要： 混合流水车间调度问题(HFSP)是广泛存在于流程制造系统中的NP-hard问题。针对最小化完工时间的HFSP，结合Jaya算法和禁忌搜索的优势，提出了一种改进Jaya算法。在该算法迭代更新阶段，根据设计的编码方式提出一种基于路径重连的方法来进行离散更新，以保证种群的多样性，提高全局搜索能力。为提高局部搜索能力，提出融合两种邻域结构的禁忌搜索算法来进一步提高解的质量，并根据问题特性对邻域结构进行适配调整。采用所提算法求解三种基准测试集，在大规模经典测试集中求出新的最优解，在解的质量方面优于当前文献中其他算法，验证了所提算法的有效性和优越性。

关键词: 混合流水车间调度, 路径重连, 禁忌搜索, 完工时间