一种求解项目鲁棒调度问题的变邻域禁忌搜索算法  

A variable neighborhood tabu search algorithm for project robust scheduling problems

作　　者：梁慧[1] 何羽康 

机构地区：[1]黑龙江大学数学科学学院,哈尔滨150080 [2]黑龙江大学计算机科学技术学院,哈尔滨150080

出　　处：《黑龙江大学自然科学学报》2016年第5期676-681,共6页Journal of Natural Science of Heilongjiang University

基　　金：国家自然科学基金资助项目(71371150);黑龙江省普通高等学校青年学术骨干支持计划项目(1254G044)

摘　　要：鲁棒调度对于不确定环境下项目的平稳实施具有重要意义。基于这一现实背景,针对项目鲁棒调度问题的NP-hard属性,集成禁忌搜索和变邻域搜索各自的优势,将禁忌搜索嵌入到变邻域搜索中,提出了一种变邻域禁忌搜索算法。在随机生成的标准算例集合上,以禁忌搜索和变邻域搜索为对比基准,对所设计的算法进行了测试,并分析了问题规模、可更新资源和项目截止日期等关键参数对算法绩效的影响。结果表明,变邻域禁忌搜索算法的求解质量明显高于其他两种算法,是求解项目鲁棒调度问题的一种高效的算法。The robust scheduling has great significance for the smooth implementation of projects under uncertain conditions. A variable neighborhood tabu search algorithm is proposed considering the NP-hard property of the project robust scheduling problem. The tabu search is embedded into the variable neighborhood search to combine both advantages simultaneously. Influence of the problem scale, renewable resource and project deadline on the performance of the algorithms is analyzed and measured. The results indicate that the solution quality of the variable neighborhood tabu search algorithm is remarkably higher than that of other two algorithms and hence is an efficient algorithm for the project robust scheduling problem.

关 键 词：项目调度 优化模型 禁忌搜索 变邻域搜索 鲁棒性 

分 类 号：C935[经济管理—管理学] F224.33