求解资源受限项目调度问题的改进粒子群算法

An Improved PSO for Solving Resource-constrained Project Scheduling Problem

提出了一种求解资源受限项目调度问题的粒子群算法。根据资源受限项目调度问题的特点,依据向量相似度理论建立速度更新模型。在位置更新机制中,根据所谓向量速度和分量速度对粒子的位置进行移动。算法使用一种基于优先权排列的编码方式,该编码方式综合了基于优先权列表和基于排列两种编码方式的优点。采用被普遍应用的PSPLIB标准问题对该算法进行了大量的仿真测试,并与既有粒子群算法和其他智能优化算法进行了比较,结果显示本文所提出的算法对求解资源受限项目调度问题是有效的。

To solve resource-constrained project scheduling problem（RCPSP）,an improved particle swarm optimization（PSO） algorithm is presented.In this algorithm,the velocity-updating mechanism is formulized based on the vector similarity theory according to the characteristics of RCPSP,and in the position-updating mechanism the particles can move according to the so-called vector velocity and dimension velocity.A new permutation of priority-based encoding scheme is designed,and it inherits all the merits of both the permutation-based encoding scheme and the priority-based encoding scheme.A full-factorial computational experiment is set up using the well-known standard instances in PSPLIB,and the algorithm given in this paper is compared with the existing PSO algorithms and other intelligent optimization algorithms,the results reveal that the algorithm is effective for the RCPSP.