一种求解资源受限项目调度问题的差分进化-布谷鸟搜索算法-论文.pdf.pdf

第34卷第2期 2014年5月桂林理工大学学报 JournalofGuilinUniversityofTechnology May 2014 文章编号:1674—9057(2014)02—0315—07 doi:10·3969/j·lssn·1674—905,·2014·02·018 种求解资源受限项目调度问题的差分进化一布谷鸟搜索算法聂慧,刘波,韦向远,刘振丙((北京)力学与建筑工程学院,北京 100084; : 541004) 摘要:提出一种新颖的求解资源受限项目调度问题的差分进化一布谷鸟搜索(DE—cs)算法。DE—cs算法以全局搜索能力强的布谷鸟搜索算法为总框架,通过嵌入具有记忆搜索功能的差分进化算法,结合不同的个体更新操作,增加种群的多样性以改善算法收敛性。采用任务优先级编码和串行进度生成机制来求解 PSPLIB问题库中J3O、J6O、J120的全部480、480和600个问题,以验证算法的有效性,并与多种算法调度结果进行对比。数值试验和算法比较验证了DE—CS算法求解RCPSP问题的有效性。关键词:DE—CS算法;资源约束项目调度问题;优先级编码;串行进度生成机制;项目工期优化中图分类号: 文献标志码:A 建筑、制造、采矿、软件等行业的工程项目, 其完成常常离不开人、财、物等各类资源。换言之,有限的资源作为项目活动的主体,在项目实施过程中起着至关重要的作用。资源约束项目调度问题(resource—constrainedprojectscheduling problem,RCPSP)研究的是在资源及网络优先关系的约束下,如何合理地安排活动进度以实现特定的项目目标如工期最小化、净现值最大化、费用最小化、资源均衡等?。RCPSP问题理论丰富、应用背景强,,求解难度高,自提出后一直是理论和应用研究的热点。元启发式算法是目前RCPSP问题的重点研究对象,出现了遗传算法、蚁群算法J、模拟退火算法J、粒子群算法以及文化基因算法等有效解决方法:Ranjbar等提出了一种混合分散搜索(scattersearch)算法来求解RCPSP问题, 该算法以分散搜索为框架,通过组合两种可行的调度方案来生成新调度方案,并使用向前向后回溯法来提高求解质量;Nasifi等提出了伪粒子群优化算法来求解RCPSP问题,通过路径重连(pathrelinking)生成导向解来逐步引导粒子飞向局部、全局最优解,同时为了避免算法早熟,该算法在粒子之间设定一个距离阈值,并且距离阈值随着迭代次数的增加而减少;Vails等¨。在遗传算法求解RCPSP的基础上引入了向前向后回溯法; Ziarati等¨提出了3种蜂群算法——BA、ABC、 BSO来求解RCPSP问题,每个算法采用不同的蜂群,扩大了搜索空间的范围;Hartmann等¨提出了一种自适应遗传算法,采用两种不同的编码方案求解RCPSP问题。以上方法各有所长,虽都不能确保得到全局最优解,但若适当地运用其中一种或某几种方法的组合进行求解,就可能在求解质量和求解效率上达到一种较好的平衡,从而求得满足各种不同实际需求的最终解决方案。例如:Liu等¨在粒子群算法中嵌入差分进化操作,结合两种不同的个收