基于蚁群算法的资源受限多项目调度问题研究

中图法分类号 ：TH186 doi：10.3963/j.issn.2095-3844.2013.01.043目前对资源受限的项 目调度问题(resource-constrained proj ect scheduling problem，RCPSP)的研究主要集中于单项 目的研究上，对于资源受限 的 多 项 目调 度 问 题 (resource-constrainedmulti-project scheduling problem，RCMPSP)通常的处理方式有单项 目方式和多项 目方式 2种[1].前者是通过人为加入开始”和结束”的虚拟活动将多个项 目综合转变为单个项 目求解，而后者则把项目看成独立的.由于单项目方式忽略了资源在多个项目间的分配与在单个项目内部各活动间的分配的区别，因此存在理论缺陷 ]。

对于多项目方式的研究，研究者从不同的角度，应用不同的技术对该问题进行研究.文献[3-6]运用遗传算法进行网络资源调度，能有效的改进项 目调度方案，但是其搜索效率具有-定的随机性，且在作业数量较大时，会使算法的搜索空间急剧扩大，造成遗传算法的性能下降 ].文献[8]提出-种排序方案，但是该研究没有提及如何处理作业之间的时序逻辑关系.文献E9]提出运用粒子群算法的方案，但是当项 目任务多时，该算法对于离散的优化可能导致较大的误差，容易陷入局部最优.文献[103提出针对 RCMPSP的最大-最小蚁群优化算法，并结合禁忌表能够很好的防止收稿日期：2012-09-29高 金(1986-)：男，硕士生，主要研究领域为通信与信息系统蚁群算法的停滞现象。

本文基于实际工作背景，分析 RCMPSP的特点，结合文献[11]的案例建立以各项 目完成时间最短为目标的数学模型.由于文献[11]用到的是遗传算法的思想，因此存在遗传算法的各种弊端。

因此本文根据资源上作业间的时序关系和项 目内部任务的紧前关系组成的项目网络图，提出运用蚁群算法和串行调度生产机制[ 相结合的方法对该问题求解，并运用禁忌搜索来提高算法的局部搜索能力.为使算法具有实用性，给出算法的基本步骤。

结合实例对算法进行测试，通过实例表明，算法能有效的解决资源约束下的多项目调度问题。

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

每个子项目包含 个任务；其任务按照 1到J进行编码，其中第 1和第 .，个任务为子项 目的虚拟起始任务和最终任务，均不占资源和时间；用A，表示第 i个子项目的第J( 1，2，，J)个任务，其工期为 d 任务的开始时间记为 ST 完成· 184 · 武汉理工大学学报(交通科学与工程版) 2O13年 第 37卷时间记为 F丁 且所有任务-旦开始就不可中断.子项 目的各任务之间存在紧前关系，即各任务只有在其所有紧前任务都结束之后才能开始；任务A，的紧前任务集合记为P 所有项 目共享 K种可更新资源，其中第 k种资源的供应量为R ；任务A 对第k种资源的需求量为r 。

则 RCMPSP可以表示为如下数学模型min maxF州 (1)S.t.ST ≥ FT ，V h∈ P V i， (2)>：r ≤R ，V k，t (3)A-l E fST ≥ 0，V i，J (4)式中：F 为第i个项目的最终完成时间，由于所有项 目均从时间 0开始 ，则 maxF ，)为整个项目组的总工期.式(1)即为 RCMPSP的目标函数 ，最小 的项 目工期；式 (2)表示项 目内部各任务之 间的紧前关系；式(3)表示在任意时刻所有当前任务对资源的总需求不得超过该资源的供应量。

2 基于 RCMPSP的蚁群算法2.1 混合蚁群算法的设计由于无资源约束下每个项目活动都有各自的最早开始时间ST 和工期d 则根据串行调度生N 成机制，能够得到 >：J 个阶段，每个阶段都有-个可行集 D ，在局部可行集中运用蚁群算法的思想，从而实现对 RCMPSP的求解.下面对算法的具体求解过程进行说明。

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

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

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

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

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

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

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

2.2 状态转移规则由算法流程可知蚂蚁都从起始点开始直到他们走完所有的节点，即蚂蚁走完所有项目的所有任务.由于在某-时间内可能存在多个项 目任务同时占用某-资源 ，但资源不能 同时满足所有项目任务的需求时，如何选择优先执行是算法的关键.由蚁群算法的思想可知蚂蚁会根据随机选择规则进行选择.计算公式为pJ - 如 A∈D； (5)rA。批A∈D；式中： l，A为阶段J选择活动A的概率；r/， 为阶段J活动A 的启发信息由式(6)计算；r， 为阶段 J活动A 的信息素浓度，由信息素更新机制得到；Du为蚂蚁在资源k上阶段 .，的可行集 ，由串行调度生成机制得到。

1- ㈣ A ED.stA式中：st 为活动 A 的开始时 问；D，为阶段 ，的可行集。

2.3 信息素更新规则当所有蚂蚁都遍历完所有 的项 目任务，所有的项 目任务的信息素将发生更新.根据实际的蚂蚁可知，信息素的更新方式主要包括信息素挥发和信息素加强.首先当蚂蚁遍历所有项目任务时，信息素会按照-定的比例进行信息素挥发，挥发量由下式给出rJA- (1- p)rJA (7)式中：J0为挥发强度，0%p%1。

在迭代中，为了突出蚂蚁的最佳路径在下次迭代中被选择概率，只对最佳路径上的信息素浓度进行加强，即最佳的项 目调度的信息素得到加强.加强方式如下第 1期 高 金，等：基于蚁群算法的资源受限多项目调度问题研究 ·185 ·FJA - rJa △ (8)式中：酶 为迭代中最佳的项目调度增加的信息素。

n △ - (9)L，式中：Q为蚂蚁的信息素总量，为-常数； 为最佳路径的距离，这里表示项目调度中，最短的完成时间。

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

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

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

1.1项目l：项目2：项目3：I e图 1 资源冲突3 实例仿真与分析实例模型采用文献El1]的模具生产项目，即3个具有相同结构的并行执行项 目，网络结构见图 2.每个项 目有 16个任务，-共 48个任务，占用 9种资源，且每个项目任务只占用-种资源，不同的项 目任务的执行时间不同.项 目任务在无资源约束下的计划开始时间、工期和占用资源数量见表 1。

图 2 项 目网络 图表 1 项 目活动无资源约束下 的开始 时间和工期及 占用资源数量任务 资源 项目1 项目2 项 目3号 种类 Rd ST DT Rd ST DT Rd ST DT注：Rd为占用资源数量；ST为无资源约束下的计划开始时间，d；DT为项 目任务的工期，d。

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

4 结 束 语针对资源受限的多项 目调度问题的特征，运用串行进度生产机制和蚁群算法的基本思想，设计出-种混合的蚁群算法.为了避免蚁群算法的停滞现象，该算法采用最大最小蚁群算法中对信息素的浓度进行限制的方法，从而有效的提高算4 6 1 4 3 6 3 2 1 2 3 3 4 4 5 3 O 4 0 O O O 6 9 6 9 9 1 4 6 9 3 1 1 1 1 l 1 1 1 1 2 2 2 2 3 6 8 9 7 5 4 8 9 8 7 9 6 5 6 6 8 5 6 2 3 2 6 6 3 1 2 3 4 2 4 3 3 O 5 l 1 1 1 7 3 7 3 3 6 O 2 6 9 1 1 1 1 1 2 1 2 2 2 3 3 3 3 4 6 7 7 6 6 7 5 6 5 7 3 7 3 7 6 4 3 2 4 3 5 4 2 1 2 4 3 3 2 3 4 O 4 7 7 7 7 2 6 2 6 6 8 1 4 6 9 1 1 1 1 1 1 2 2 2 2 8 5 6 6 3 8 7 6 5 4 5 8 9 5 8 3 1 1 4 1 3 2 1 2 7 6 7 5 6 7 8 9 1 2 3 4 5 6 7 8 9 O 1 2 3 4 5 6 l · l86 · 武汉理工大学学报(交通科学与工程版) 2013年 第 37卷表 2 资源约束下的调 度计 划 d法较优解的选取.通过实例的演算与分析发现此算法能够较好的解决 RCMPSP问题。