Abstract: To solve the Resource-Constrained Project Scheduling Problem (RCPSP),a new Dynamic Diversity Evolution Strategy (DDES) algorithm was proposed.The balance between global exploration and local exploitation was realized by controlling the population diversity dynamically and restarting the diversity evolution.A two-point-crossover operator based on max resource utilization rate and a insert-based mutation operator were designed to generate the individuals,and a diversity-based elitism selection operator was used to select the next generation population.Taguchi method of design-of-experiment was used to find out the best combinations of parameter values in DDES.The simulation for testing case showed that the proposed method had better performance than basic evolution strategy in solution quality and convergence,and the effectiveness of proposed method was verified by computational results and comparisons with other heuristic algorithm further.

Key words: resource-constrained project scheduling problem, evolution strategy, dynamic diversity, resource utilization, elitism selection, resource-constrained project scheduling, Taguchi method

摘要： 针对资源受限项目调度问题,提出一种动态多样性的进化策略。算法通过动态控制种群的多样性和使用多样性重启方法来实现全局搜索能力和局部探测能力的平衡,并设计了一种基于最大资源利用率的两点交叉算子和基于插入的变异算子来产生新个体,使用基于多样性的精英保留选择算子来产生新种群。使用实验设计的Taguchi方法求得了新算法的最佳参数组合,对标准测试库的测试案例进行了仿真实验,结果表明新算法比基本进化策略具有更好的求解质量和收敛性。通过与其他启发式算法进行比较,进一步验证了算法的有效性。

关键词: 资源受限项目调度, 进化策略, 动态多样性, 资源利用率, 精英保留, Taguchi方法