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

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

Improved Cuckoo Search Algorithm for Resource-Constrained Project Scheduling

An efficient Improved Cuckoo Search （ICS） algorithm is proposed to solve the resource-constrained project scheduling problem （RCPSP）. The improved CS algorithm is designed as follows, each individual is coded based on the priority of task for scheduling as to be in a form suitable for matching the characteristics of Lrvy flights, and then this individual should be resolved by serial scheduling method. To avoid low efficiency and local minimum, both an elite individual local search method and a mechanism of aging are introduced in the local search phase of CS in addition. To validate the efficiency of ICS, both CS and ICS algorithms are tested on RCPSP of J30, J60 and J90 taken from PSPLIB benchmark. The results are compared with reference values and the optimum results by CPLEX. The results show that ICS always has faster convergence speed and shorter makespan than CS. The approach provides an efficient method for solving other scheduling and optimization problems.