抢占式资源受限项目调度问题的遗传算法

Genetic algorithms for the preemptive resource-constrained project scheduling problem

针对抢占式资源受限项目调度问题中任意活动只被允许抢占最多1次的子问题,在经典的活动列表和优先权值编码方案基础上,引入抢占点概念,设计2种新的二维编码方案,并设计相应的解码方法.在4种编码方案基础上,采用不同的选择算子、交叉算子及变异概率,并对各种遗传算法的参数设置进行系统的实验测试,确定各方案的最佳参数设置.基于标准PSPLIB数据集设计大规模计算实验.结果表明,在资源受限项目调度问题中引入抢占能够显著缩短项目工期,采用优先权值编码方案的遗传算法在抢占式资源受限项目调度问题上有良好的求解效果,当问题规模扩大时采用活动列表编码方案的遗传算法也表现良好.

In order to solve a subproblem of the preemptive resource-constrained project scheduling problem in which each activity is allowed to be exempted once only, a new concept of preemption point was intro- duced to design two new encoding schemes based on the classic encoding schemes such as the activity list and priority values. Decoding schemes were designed for all encoding schemes respectively. Based on dif- ferent encoding and decoding schemes, four genetic algorithms were proposed with different configurations of selection operators, crossover operators, and mutation probabilities. Systematic tests were carried out to determine the optimal parameter configurations. A large-scale computational experiment was designed using the standard PSPLIB problem sets. Computational results show that preemption helps shorten the duration of resource-constrained projects and the genetic algorithm based on priority values is most effective in handling preemptive resource-constrained project scheduling problems whereas the genetic algorithm based on activity lists is competitive for problems with more activities.