一种多项目调度的改进蚁群算法研究

张勇明　陈晔　吴志飞

【摘 要】提出一种用于资源约束下多项目调度问题的改进蚁群算法，该算法基于最大最小蚂蚁基础算法，在解的构建过程中使用伪随机比例行为选择规则，并在每一次迭代中应用禁忌搜索算法进行局部优化。最后仿真实例表明该算法在多项目调度中有良好的优化性能。

【关键词】多项目调度；蚁群算法；禁忌搜索

资源约束下多项目调度问题RCMPSP（Resource-Constrained Multi-Project Scheduling Problems）是一类重要调度问题，优化目标是有资源竞争时的多个项目的总工期最短。目前主要求解算法包括两类：基于规则的启发式算法[1]和智能优化算法[2]。本文针对该问题，提出一种改进的蚁群算法[3]，以最大最小蚂蚁算法[4]为基础，选择最早可行起始时间作为蚂蚁搜索的启发式指导信息，同时对每次迭代结果引入禁忌搜索算法进一步优化。

1 RCMPSP问题蚁群算法描述

为解决蚁群算法在多项目调度问题中易陷入局部最优的问题，本文对最大最小蚂蚁算法MMAS进行了改进，在解的构建过程中使用伪随机比例行为选择规则，并采用积极的行为选择规则以加快算法收敛速度。在引入的禁忌搜索中采用2-opt交换局部搜索，帮助算法跳出可能的局部最优，同时通过将存在未完成紧前任务的任务和等待资源的任务加入禁忌表，能降低算法运算时间。本文提出的改进蚁群算具体迭代步骤如下：

step1： 数据初始化，包括读入问题实例的网络图，初始化信息素矩阵和启发式信息矩阵，初始化信息素的上界与下界，初始化蚂蚁的记忆；

step2： 算法开始一次迭代；

step3： 一只蚂蚁被分配到开始虚拟节点0开始；

step4： 当前蚂蚁选择下一个被调度的任务，其选择规则即状态转移规则采用以轮盘赌（roulette wheel）选择程序为核心的伪随机比例选择规则；

step5： 更新当前蚂蚁的记忆，包括蚂蚁当前已调度任务列表，还有蚂蚁对任务的调度记忆标示，即将已调度过的任务标示为true，未调度的任务仍标示为flase；

step6： 若当前蚂蚁已调度完实例中所有N个项目的D个任务，则计算当前蚂蚁构建的路径的长度，转setp7，否则跳转到step4；

step7： 若所有的m只蚂蚁都已完成了对任务的调度，转step8，否则跳转step3；

step8： 针对每只蚂蚁所构建的路径，采用禁忌搜索进行局部优化；

step9：信息素的更新规则为所有信息素以同一比率蒸发，但仅允许构建出最优方案的蚂蚁释放信息素，要求所有路径上的信息素满足[τmin，τmax]的限制。算法的一次迭代结束；

step10： 满足算法迭代结束条件，迭代结束，否则跳转step2。算法迭代结束条件是连续Nd次迭代不能缩短最优方案的路径长度即多项目的最小总工期，Nd根据算法运行时实际条件取值。

2 针对多项目调度的蚁群算法改进

2.1 状态转移规则

所有蚂蚁都从多项目总网络图的源点出发，直到所有蚂蚁都将所有任务调度完毕，即到达多项目总网络图的汇点时解的构建过程才结束，具体见上文中算法步骤的step3-step7。开始构建解时，蚂蚁首先调度开始虚节点任务0，而后每经过一次迭代蚂蚁就向解中添加一道未调度的任务。在蚂蚁k出现在构建步骤i时，按伪随机比例规则选择下一道调度任务j。这个规则由如下式子给出：

其中q为均匀分布在区间[0，1]中的一个随机变量，q0（0≤q0≤1）是一个参数，J是根据式（2）给出的概率分布产生出来的一个随机变量（其中α=1）。

对式（1），如果q≥q0，则蚂蚁k按照随机比例规则的概率行为选择规则来决定下一道将调度的任务，选择任务j作为下一道调度的任务的概率为

其中ηij代表由式（3）确定的启发式信息，而参数α针对信息素，参数β针对启发式信息， Nik表示还没有被蚂蚁k调度的任务。选择任务j作为后续调度任务的概率由该任务所对应的信息素τij及启发式信息ηij决定。

其中estj是任务j的最早可行起始时间，N包含了所有到目前为止还没有被调度的任务，并且这些未调度任务的所有紧前任务都已经被调度过了。

2.2 信息素的更新规则

信息素更新的第一个步骤是蒸发：

其中ρ是信息素的蒸发率，有0<ρ≤1。信息素蒸发后，第二个步骤信息素释放，本文算法中只允许至今构建出最优方案的蚂蚁释放信息素，以此强调对最优路径的开发。释放规则如下：

算法中任意一个任务调度迭代后的信息素量的上界是1/ρC*，其中C*代表最优方案即最小总修理周期的大小。基于上述结论，可以使用对1/ρC*的估计值1/ρCbs来定义τmax。更新τmax值的时机为每次发现新的至今最优方案时。相应地，信息素的下界被设定为τmin=τmax/a，其中a是一个可根据需要动态取值的参数。

2.3 带2-opt的禁忌局部搜索

为解决蚁群算法易陷入局部最优的问题，本文采用了带2-opt的禁忌搜索TS作为局部搜索算法。禁忌搜索TS以蚁群算法每次迭代完成后形成的解作为初始解，其关键为邻域的搜索和禁忌表的处理。

禁忌搜索TS中的邻域搜索采用2-opt的搜索策略，所谓2-opt策略即用两条边取代原有的2两条边来生成解。禁忌搜索以邻域中最好的解作为新解，它与其它优化方法不同的是即使新解劣于目前解也暂时接受，这样能避免陷入局部最优，从而利于寻找全局最优。2-opt策略中使用了含长度限制的最近邻列表，列表的长度L决定了算法执行时间的增长，其值大小可根据问题的规模来确定。

禁忌局部搜索的结束条件是算法搜索过程经过一定步数之后，仍不能得到改进的解，则禁忌搜索结束。

3 仿真实例

为验证算法性能，本文采用一个模具生产实例，该实例包括3个相同网络结构的项目，其网络图结构如图1所示。

实例中共有3个项目，13种资源，48个任务。给定项目的权重系数分别为a1=0.5、a2=0.3、a3=0.2。设3个项目独立完成时间分别为33d、43d、38d，最晚完成期限分别为48

本文算法结束条件为连续1000次迭代不能缩短最优方案的最小总工期，算法参数值为：α=1，β=3，ρ=0.02，m=50。表2中的仿真结果表明，本文改进蚁群算法对于多项目调度问题具有良好的优化性能。

4 结束语

本文针对多项目调度问题，提出一种改进蚁群算法，其以最大最小蚂蚁算法为基础，选择最早可行起始时间作为蚂蚁搜索的启发式指导信息，并在局部搜索部分引入禁忌算法。仿真实例表明该蚁群算法对于多项目调度问题具有良好的优化性能。

【参考文献】

[1]邓林义，等.资源约束下多项目调度的拓扑优化方法[J].系统仿真学报，2007，19（16）：3846-3849.

[2]林晶晶，周国华.基于粒子群算法的关键链多项目调度管理[J].统计与决策，2012（10）：44-48.

[3]张军，胡晓敏，等，译.蚁群优化[M].北京：清华大学出版社，2007.

[4]Stuzle，T.，Hoos，H.H. MAX-MIN Ant System[J]. Future Generation Computer Systems，2000，16（8）：889-914.

[责任编辑：汤静]