自适应混合蚁群算法在MRCPSP中的应用

闫 森，王玉玫

(1.华北计算技术研究所系统三部，北京 100083； 2.华北计算技术研究所总体部，北京 100083)

0 引 言

活动工期的不确定性和多模式问题在项目调度中往往难以避免，为了如期完成任务，厂家往往通过增加资源投入来减少工期，由此产生了工期不确定的多模式资源约束项目调度问题(Multi-mode Resource Constrained Project Scheduling Problem， MRCPSP)[1]。多模式指同一活动的不同执行模式会有不同的活动工期以及相应的资源需求量。

MRCPSP中活动的执行除了要受到其紧前事件的限制，还要受到多种资源的约束。MRCPSP作为一种复杂的非线性NP难问题，很难利用精确算法[2]去求得最优解，而启发式算法[3-4]和智能优化算法(遗传算法[5-7]、模拟退火算法[8-9]、粒子群算法[10-11]和蚁群算法[12])往往能在求解精度和效率之间取得令人满意的效果，并且因为活动工期常来源于经验与主观预测，具有不准确性，因此往往采取随机任务工期的方法[13-15]。

自然界中，蚁群通过释放信息素，指导后续蚂蚁寻找目标，由此概念产生的蚁群算法在解决NP难问题方面功效尤为显著[16]。Chen等[17]将云工作流调度建模为一个多目标优化问题，使用2个蚁群分别处理这2个目标，提出了一种新的信息素更新规则。Zhou等[18]提出了一种新的混合互补启发式策略，该策略包含3种启发式信息方案，以避免蚁群只关注自己的目标。Mutar等[19]使用改进的蚁群算法解决CVRP问题，依赖于利用以前迭代中的子路径经验进行的信息素更新。迄今为止，对于改进蚁群算法的优化研究有些单纯在信息素更新策略方面进行改进而忽略了其他参数的影响[17-18，20]，有些在迭代过程中不能很好地对参数进行自适应更新[21]，于二者的平衡问题仍缺乏相关深入探索，有必要进行进一步的研究探索，加以优化。……