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

作     者：任文娟 潘全科 韩红燕 REN Wen-juan;PAN Quan-ke;HAN Hong-yan

作者机构：聊城大学计算机学院山东聊城252059 聊城大学数学科学学院山东聊城252059 

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

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2010年第31卷第23期

页      码：5071-5074页

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

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

学科分类：0711[理学-心理学类] 07[理学] 08[工学] 081104[081104] 0811[工学-水利类] 071102[071102] 081103[081103] 

D　O　I：10.16208/j.issn1000-7024.2010.23.040

馆 藏 号：203113351...