摘要： 针对混合流水车间系统的最小化Makespan调度问题，提出一种基于关键路径理论的变邻域禁忌搜索算法，讨论其关键技术。在该算法中，提出基于关键路径的毗邻域概念，防止搜索算法陷入局部最优解，采用变邻域搜索策略，在无法改进解时，实现对移动毗邻域的搜索。仿真结果表明，该算法获得的调度结果优于简化禁忌搜索和启发式算法。

关键词: 禁忌搜索, 毗邻域, 调度

Abstract: Aiming at the minimum Makespan scheduling problem of Hybrid FlowShop(HFS), this paper proposes a tabu search algorithm in varying neighborhood approach based on critical path theory, and its key technic is discussed. To prevent the algorithm from tripping in local optimal solution, the concept of adjacent neighborhood is proposed. If it cannot improve solution, tabu search will search adjacent neighborhood of moves by using the change neighborhood search strategy. Simulation results show that this algorithm can get a better solution than other algorithms.

Key words: tabu search, adjacent neighborhood, scheduling

中图分类号: 

• TP311.1