混合流水车间调度的变邻域禁忌搜索算法  

Tabu Search Algorithm in Varying Neighborhood for Hybrid Flowshop Scheduling

作　　者：李霄峰[1] 史金飞[1] 阎威武[2] 

机构地区：[1]东南大学机械工程系,南京210096 [2]上海交通大学自动化系,上海200237

出　　处：《计算机工程》2008年第21期10-11,25,共3页Computer Engineering

基　　金：国家“863”计划基金资助项目(70272046);国家自然科学基金资助项目(60504033)

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

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

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]