一种求解资源受限项目调度问题的遗传算法

A Genetic Algorithm for Solving RCPSP

提出一种求解使用可更新资源的单模式资源受限项目调度问题的遗传算法.采用遗传算法对项目活动进行调度,在满足紧前关系约束和资源约束的条件下,最小化项目工期.继承了基于排列和基于优先级的编码方案的优点,提出一种新的基于优先权排列的编码方案.采用串行调度方法生成项目计划.使用PSPLIB中的标准问题库对算法进行了充分的数值实验,通过与既有算法进行比较,证明本文算法的有效性.

A genetic algorithm （GA）is proposed to solve the resource constrained project scheduling problem（RCPSP）, in which resources are renewable and there is a single mode to perform each activity. Genetic algorithm is employed to schedule project activities to minimize make-span subject to precedence constraints and resources availability. A new permutation of priority-based encoding scheme is designed in the algorithm, and it inherits the merits of both the permutation-based encoding scheme and the priority-based encoding scheme. The serial scheduling scheme is used in decoding scheme to generate project plan. A full computational experiment is set up using the wellknown standard instances library in PSPLIB, and the algorithm presented in this paper is compared with the other existing intelligent optimization algorithms. The experiment results reveal that the algorithm is effective for the RCPSP.