求解资源受限项目调度问题的改进布谷鸟搜索算法

聂慧^1,2，刘波¹，韦向远³，杨辉华³

1. 中国矿业大学(北京)力学与建筑工程学院2. 桂林电子科技大学人事处3. 桂林电子科技大学广西信息科学实验中心

摘 要：针对资源受限项目调度问题(RCPSP),提出一种基于改进布谷鸟搜索(ICS)算法的高效求解方法。ICS算法设计如下:在解空间表示方面提出一种适应莱维飞行特点的任务调度顺序优先级编码方案,并采用串行调度求解该问题;为提高算法收敛速度、避免陷入局部最优解,对CS的局部搜索机制进行改进,即引入对精英个体的局部搜索策略及对首领的寿命衰老机制。最后,通过PSPLIB基准测试问题J30、J60和J90对算法性能进行测试,并与CPLEX优化结果及参考值进行比较,结果表明ICS算法较CS算法收敛更快、结果更优,调度结果理想。

关键词：资源受限项目调度问题;布谷鸟搜索算法;精英个体局部搜索;寿命衰老机制;