禁忌搜索算法解决零空闲流水线调度问题  

Tabu search algorithm for no-idle flowshop scheduling problems

作　　者：任文娟[1] 潘全科[1] 韩红燕[2] 

机构地区：[1]聊城大学计算机学院,山东聊城252059 [2]聊城大学数学科学学院,山东聊城252059

出　　处：《计算机工程与设计》2010年第23期5071-5074,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(60874075);中国博士后科学基金项目(20070410791)

摘　　要：针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型。新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能。利用动态方式更新禁忌表长,提高了新算法的鲁棒性。为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法。仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值。For NP-Hard scheduling problems,the no-idle flowshop scheduling problemis deeply analyzed.Then a tabu search algorithm based on the NEH method is proposed for the no-idle flowshop scheduling problem.And an algorithm model with the target of the maximum makespan is established.The new algorithm uses the NEH heuristic to generate the initial solution and this improves its searching performance.It updates the length of the tabu list dynamicly to improve the robustness of the new algorithm.In order to improve the efficiency of the algorithm it uses fast search algorithm to improve the proposed tabu search,that is,fast search algorithm as the neighborhood function of the tabu search.Then an improved tabu search algorithm is presented.Simulation results proved the effectiveness and superiority of the new algorithm.The practical value of the new algorithm is very high in the flowshop production scheduling field, automation engineering field and and so on.

关 键 词：零空闲流水线调度 最大完工时间 快速搜索 禁忌搜索算法 调度 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]