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

摘要：

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值.

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

所属期刊栏目：31

分类号：TP278(自动化技术及设备)

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

在线出版日期：2011-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：5071-5074