高 金 郭顺生 杜百岗 李西兴

（武汉理工大学信息工程学院1） 机电学院2） 武汉 430070）

目前对资源受限的项目调度问题（resourceconstrained project scheduling problem，RCPSP）的研究主要集中于单项目的研究上，对于资源受限 的 多 项 目 调 度 问 题 （resource－constrained multi－project scheduling problem，RCMPSP）通常的处理方式有单项目方式和多项目方式2种［1］.前者是通过人为加入“开始”和“结束”的虚拟活动将多个项目综合转变为单个项目求解，而后者则把项目看成独立的.由于单项目方式忽略了资源在多个项目间的分配与在单个项目内部各活动间的分配的区别，因此存在理论缺陷［2］.

对于多项目方式的研究，研究者从不同的角度，应用不同的技术对该问题进行研究.文献［3－6］运用遗传算法进行网络资源调度，能有效的改进项目调度方案，但是其搜索效率具有一定的随机性，且在作业数量较大时，会使算法的搜索空间急剧扩大，造成遗传算法的性能下降［7］.文献［8］提出一种排序方案，但是该研究没有提及如何处理作业之间的时序逻辑关系.文献［9］提出运用粒子群算法的方案，但是当项目任务多时，该算法对于离散的优化可能导致较大的误差，容易陷入局部最优.文献［10］提出针对RCMPSP的最大－最小蚁群优化算法，并结合禁忌表能够很好的防止蚁群算法的停滞现象.

本文基于实际工作背景，分析RCMPSP的特点，结合文献［11］的案例建立以各项目完成时间最短为目标的数学模型.由于文献［11］用到的是遗传算法的思想，因此存在遗传算法的各种弊端.因此本文根据资源上作业间的时序关系和项目内部任务的紧前关系组成的项目网络图，提出运用蚁群算法和串行调度生产机制［12］相结合的方法对该问题求解，并运用禁忌搜索来提高算法的局部搜索能力.为使算法具有实用性，给出算法的基本步骤.结合实例对算法进行测试，通过实例表明，算法能有效的解决资源约束下的多项目调度问题.

1 问题描述

据典型的RCMPSP的描述，本文研究的RCMPSP共包含N个独立的子项目.各子项目之间没有必然的联系，但可能需要占用同一种资源.

每个子项目包含J个任务；其任务按照1到J进行编码，其中第1和第J个任务为子项目的虚拟起始任务和最终任务，均不占资源和时间；用Aij表示第i个子项目的第j（j＝1，2，…，J）个任务，其工期为dij，任务的开始时间记为STij，完成时间记为FTij；且所有任务一旦开始就不可中断.子项目的各任务之间存在紧前关系，即各任务只有在其所有紧前任务都结束之后才能开始；任务Aij的紧前任务集合记为Pij.所有项目共享K种可更新资源，其中第k种资源的供应量为Rk；任务Aij对第k种资源的需求量为rkij.

记时刻t正在进行的所有任务的集合为It.则RCMPSP可以表示为如下数学模型

式中：Fi，J为第i个项目的最终完成时间，由于所有项目均从时间0开始，则 max｛Fi，J｝为整个项目组的总工期.式（1）即为RCMPSP的目标函数，最小的项目工期；式（2）表示项目内部各任务之间的紧前关系；式（3）表示在任意时刻所有当前任务对资源的总需求不得超过该资源的供应量.

2 基于RCMPSP的蚁群算法

2.1 混合蚁群算法的设计

由于无资源约束下每个项目活动都有各自的最早开始时间STij和工期dij，则根据串行调度生成机制，能够得到个阶段，每个阶段都有一个可行集DJ，在局部可行集中运用蚁群算法的思想，从而实现对RCMPSP的求解.下面对算法的具体求解过程进行说明.

步骤1初始化数据，包括初始化蚂蚁的信息素矩阵、算法的启发式矩阵.

步骤2迭代开始.

步骤3将一只蚂蚁放入虚拟起始点.

步骤4求阶段J的可行任务集.

步骤5蚂蚁根据转移规则从可行任务集中选择下一结点，即任务.将选择任务加入禁忌表中，并更新可行任务集和资源拥有量Rk.其中转移规则，采用轮盘赌选择规则；可行任务集表示在J阶段k资源上可行的任务集合，根据项目活动的计划开始时间和完成时间以及任务Aij占用的资源数决定.

步骤6判断可行任务集是否为空.若非空，则转至步骤5；否则执行步骤7.

步骤7更新项目任务的计划开始时间和完成时间.

步骤8如果蚂蚁走完所有项目的所有任务，记录蚂蚁的路径，执行步骤9；否则返回步骤4.

步骤9如果M只蚂蚁都走完所有项目的所有任务，执行步骤10；否则返回到步骤3.

步骤10将M只蚂蚁的M条路径的信息素进行挥发，对这M条路径中完成时间最短的路径进行信息素增强.且保证所有的信息素浓度在范围［τmin，τmax］中.

步骤11判断迭代是不是满足终止条件，若满足，则迭代结束；否则返回至步骤2.

2.2 状态转移规则

由算法流程可知蚂蚁都从起始点开始直到他们走完所有的节点，即蚂蚁走完所有项目的所有任务.由于在某一时间内可能存在多个项目任务同时占用某一资源，但资源不能同时满足所有项目任务的需求时，如何选择优先执行是算法的关键.由蚁群算法的思想可知蚂蚁会根据随机选择规则进行选择.计算公式为

式中：pJA为阶段J选择活动A的概率；ηJA为阶段J活动A的启发信息由式（6）计算；τJA为阶段J活动A的信息素浓度，由信息素更新机制得到；DkJ为蚂蚁在资源k上阶段J的可行集，由串行调度生成机制得到.

式中：stA为活动A的开始时间；DJ为阶段J的可行集.

2.3 信息素更新规则

当所有蚂蚁都遍历完所有的项目任务，所有的项目任务的信息素将发生更新.根据实际的蚂蚁可知，信息素的更新方式主要包括信息素挥发和信息素加强.首先当蚂蚁遍历所有项目任务时，信息素会按照一定的比例进行信息素挥发，挥发量由下式给出

式中：ρ为挥发强度，0＜ρ＜1.

在迭代中，为了突出蚂蚁的最佳路径在下次迭代中被选择概率，只对最佳路径上的信息素浓度进行加强，即最佳的项目调度的信息素得到加强.加强方式如下

式中：ΔτbsJA为迭代中最佳的项目调度增加的信息素.

式中：Q为蚂蚁的信息素总量，为一常数；Cbs为最佳路径的距离，这里表示项目调度中，最短的完成时间.

然而，由于在一次迭代中可能存在所有的蚂蚁都选择同一种调度方案，从而导致这个调度方案的信息素增加太快，以致发生停滞现象，影响最优解的求得.为了避免这种现象的发生，本文采用最大最小蚁群算法，将信息素浓度控制在［τmin，τmax］中.

式中：a为常数.

2.4 可行任务集DJ

由算法流程图可知，可行任务集DJ是算法的重要参数，它的扩展包含了整个项目调度的所有的解空间，如何求可行任务集DJ是算法的重点.根据Kelley的串行调度生成机制，对于包含N个项目的RCMPSP来说，一共包含个任务，因此对于RCMPSP的串行调度生成机制，需要个阶段.在每一阶段中，首先要确定可行集DJ，根据一定的优先规则从DJ中选取任务，并在满足式（2）、（3）的条件下进行调度.通过局部扩展，逐步更新可行集，从而得到整个项目的进度安排.

由于每个项目都有各自的计划开始时间，于是将各项目任务按计划开始时间分配到对应资源k上，如图1所示3个项目活动在资源k上的计划进度安排.由图可知项目1和项目2最早开始发生资源冲突，则在此冲突持续时间段内的所有项目任务即为此阶段的可行任务集DJ.

图1 资源冲突

3 实例仿真与分析

实例模型采用文献［11］的模具生产项目，即3个具有相同结构的并行执行项目，网络结构见图2.每个项目有16个任务，一共48个任务，占用9种资源，且每个项目任务只占用一种资源，不同的项目任务的执行时间不同.项目任务在无资源约束下的计划开始时间、工期和占用资源数量见表1.

图2 项目网络图

表1 项目活动无资源约束下的开始时间和工期及占用资源数量

根据设计的蚁群算法的思想，在迭代次数NC＝100，挥发系数ρ＝0.1，偏重因子α＝0.3，β＝8的设置下可以得到一个可行的调度计划，见表2.由表2可知，项目组的总的完成时间为61 d，比文献［11］少1d，说明此算法的设计在资源受限的多项目调度方面存在一定的优势，能够提高企业的项目调度效率.

4 结束语

针对资源受限的多项目调度问题的特征，运用串行进度生产机制和蚁群算法的基本思想，设计出一种混合的蚁群算法.为了避免蚁群算法的停滞现象，该算法采用最大最小蚁群算法中对信息素的浓度进行限制的方法，从而有效的提高算法较优解的选取.通过实例的演算与分析发现此算法能够较好的解决RCMPSP问题.

表2 资源约束下的调度计划 d

［1］BROWNING T R，YASSINE A A.Resource－constrained multi－project scheduling：priority rule performance revisited［J］.International Journal of Production Economics，2010（2）：212－228.

［2］WILEY V D，DECKRO R F，JACKSON Jr J A.Optimization analysis for design and planning of multiproject programs［J］.European Journal of Operational Research，1998（2）：492－506.

［3］GONCALVES J F，MENDES J J M，RESENDE M G C.A genetic algorithm for the resource constrained multi－project scheduling problem［J］.European Journal of Operational Research，2008（3）：1171－1190.

［4］应 瑛，寿涌毅，李 敏.资源受限多项目调度的混合遗传算法［J］.浙江大学学报：工学版，2009（1）：23－27.

［5］李 敏.资源约束下多项目调度问题遗传算法研究［D］.杭州：浙江大学，2008.

［6］VALLS V，BALLESTIN F，QUINTANILLA S.A hybrid genetic algorithm for the resource－constrained project scheduling problem［J］.European Journal of Operational Research，2008（2）：495－508.

［7］林 琳，姚 郁.多资源约束下的多项目作业调度问题研究［J］.哈尔滨工业大学学报，2007（7）：1045－1049.

［8］REMY J.Resource constrained scheduling on multiple machines［J］.Information Processing Letters，2004（91）：177－182.

［9］杨 铭，王 凯，李 原，等.基于改进型粒子群算法的航空多项目调度方法［J］.火力与指挥控制，2010（2）：55－58.

［10］MCRKLC D，MIDDCNDORF M，SCHMCCK H.Ant colony optimization for resource－constrained project scheduling［J］.IEEE Transactions on Evolutionary Computation，2002，6（4）：333－318.

［11］廖 仁，陈庆新，毛 宁.模具虚拟企业项目调度遗传算法研究［J］.计算机集成制造系统，2004（7）：80－84.

［12］KELLEY J E.The critical path method：resources planning and scheduling［J］.New Jersey Industrial Scheduling USA：Prentice Hall，1963（1）：347－365.