宋 尧,仰燕兰,叶 桦

1(东南大学 自动化学院,南京 210096)

2(复杂工程系统测量与控制教育部重点实验室,南京 210096)

资源受限项目调度问题(Resource-Constrained Project Scheduling Problem,RCPSP)是一种典型的NPhard 问题[1],具有约束条件严苛、组合性强、求解范围广等特点,其基本目标是在一定资源的约束下得到合理的调度方案,使得时间或者项目成本得到最优化.多技能资源受限项目调度问题(Multi-Skilled Resource-Constrained Project Scheduling Problem,MS-RCPSP/MSPSP)是在其基础上增加了技能约束的一种拓展性问题,因其在软件开发、建筑工程、车间调度等方面的广泛应用而不断受到越来越多的学者的关注,并衍生出许多求解方案.比如,任逸飞等人提出了一种包含双层决策及局部优化策略的混合算法对MSPSP 进行求解,并结合基于关键链的局部搜索算法提高了求解质量[2];Skowronski 等人先后用基于调度优先级规则的元启发式算法[3]、禁忌搜索算法[4]和进化算法[5]研究MSPSP,并生成了一套专门针对MSPSP 的基准数据集iMOPSE[6],为后世研究该问题提供了重要参考依据.

总的来说,目前所使用的各种算法都仅能针对部分数据对象而不断靠近最优解,如何提出合适的算法为MSPSP 求出更优解是目前研究努力的一个方向.本文在对比了各种算法之后,考虑到发展已久的遗传算法(Genetic Algorithm,GA)[7]在寻优搜索能力、鲁棒性和兼容性等方面的良好表现,选择其作为本文的基本算法.考虑到该算法存在早熟收敛和后期收敛速度慢的问题,学者们在其基础上进行了相关改进,并用于求解MSPSP 问题.比如,Laszczyk 等人在经典的非支配遗传算法……