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

第３４卷 第２期 桂 林 理 工 大 学 学 报 Ｖｏｌ３４Ｎｏ２ ２０１４年５月 ＪｏｕｒｎａｌｏｆＧｕｉｌｉｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ Ｍａｙ　２０１４  文章编号：１６７４－９０５７（２０１４）０２－０３１５－０７　　　　　 ｄｏｉ：１０３９６９／ｊ．ｉｓｓｎ１６７４－９０５７２０１４０２０１８ 一种求解资源受限项目调度问题的 差分进化 －布谷鸟搜索算法 １，２ａ １ ２ｂ ２ｂ 聂　慧 ，刘　波 ，韦向远 ，刘振丙 （１中国矿业大学 （北京）力学与建筑工程学院，北京　１０００８４； ２桂林电子科技大学 ａ信息与通信学院；ｂ电子工程与自动化学院，广西 桂林　５４１００４） 摘　要：提出一种新颖的求解资源受限项目调度问题的差分进化－布谷鸟搜索 （ＤＥＣＳ）算法。ＤＥＣＳ算 法以全局搜索能力强的布谷鸟搜索算法为总框架，通过嵌入具有记忆搜索功能的差分进化算法，结合不同 的个体更新操作，增加种群的多样性以改善算法收敛性。采用任务优先级编码和串行进度生成机制来求解 ＰＳＰＬＩＢ问题库中Ｊ３０、Ｊ６０、Ｊ１２０的全部４８０、４８０和６００个问题，以验证算法的有效性，并与多种算法调 度结果进行对比。数值试验和算法比较验证了ＤＥＣＳ算法求解ＲＣＰＳＰ问题的有效性。 关键词：ＤＥＣＳ算法；资源约束项目调度问题；优先级编码；串行进度生成机制；项目工期优化 中图分类号：ＴＰ３９１９　　　　　　　　　　　　　　文献标志码：Ａ ［９］ 建筑、制造、采矿、软件等行业的工程项目， 溯法来提高求解质量；Ｎａｓｉｒｉ等 提出了伪粒子群 其完成常常离不开人、财、物等各类资源。换言 优化算法来求解 ＲＣＰＳＰ问题，通过路径重连 之，有限的资源作为项目活动的主体，在项目实 （ｐａｔｈｒｅｌｉｎｋｉｎｇ）生成导向解来逐步引导粒子飞向 施过程中起着至关重要的作用。资源约束项目调 局部、全局最优解，同时为了避免算法早熟，该 度 问题 （ｒｅｓｏｕｒｃｅｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇ 算法在粒子之间设定一个距离阈值，并且距离阈 ［１０］ ｐｒｏｂｌｅｍ，ＲＣＰＳＰ）研究的是在资源及网络优先关 值随着迭代次数的增加而减少；Ｖａｌｌｓ等 在遗传 系的约束下，如何合理地安排活动进度以实现特 算法求解ＲＣＰＳＰ的基础上引入了向前向后回溯法； ［１１］ 定的项目目标如工期最小化、净现值最大化、费 Ｚｉａｒａｔｉ等 提出了３种蜂群算法———ＢＡ、ＡＢＣ、 ［１］ 用最小化、资源均衡等 。ＲＣＰＳＰ问题理论丰富、 ＢＳＯ来求解 ＲＣＰＳＰ问题，每个算法采用不同的蜂 ［１２］ 应用背景强，属于ＮＰｈａｒｄ问题，求解难度高，自 群，扩大了搜索空间的范围；Ｈａｒｔｍａｎｎ等 提出 ［２］ 提出后一直是理论和应用研究的热点 。 了一种自适应遗传算法，采用两种不同的编码方 元启发式算法是目前 ＲＣＰＳＰ问题的重点研究 案求解ＲＣＰＳＰ问题。 ［３］ ［４］ 对象，出现了遗传算法 、蚁群算法 、模拟退 以上方法各有所长，虽都不能确保得到全局