摘 要： 针对资源量随时间变动的项目调度问题提出了一种新的离散人工蜂群求解算法。算法食物源的位置采用基于任务排列的编码方法，并提出一种可以保持解的离散性和可行性的候选食物源生成方法。仿真结果表明，该算法能有效地求解资源时变的受限项目调度问题，研究发现在保持资源总量不变甚至减少的情况下，通过调整资源配置能够显著缩短项目工期，可见资源配置优化在项目管理中的重要作用。
关键词： 项目调度；资源量随时间变动；人工蜂群算法；离散
自上世纪60年代以来，资源受限项目调度问题RCPSP(Resource-Constrained Project Scheduling)引起了国内外学者的极大关注，RCPSP是指在满足资源约束和任务先序关系条件下，合理安排调度，以实现项目的既定目标最优（通常为项目工期最短）。目前，标准RCPSP已经成为运筹学领域的一个经典问题，它建立在一定假设之上，如假定项目的可用资源均为可更新资源，资源的最大可用量在整个项目执行期间已知且保持不变。而实际项目中可用资源量却经常是随时间变化的。以人力资源为例，由于组织或多项目间的需要，在项目执行过程中人员被借用来或抽调走的情况非常普遍；对于机械设备等资源，在不同的项目间被来回占用的情况更是常见。这种资源量随时间变动的项目调度问题是标准RCPSP的一个扩展和补充，它更符合许多项目资源配置的实际情况。Klein[1]采用禁忌搜索算法求解了资源量变动需求固定的RCPSP问题。Hartmann[2]描述了一个真实医疗科研项目，项目中每个活动仅在活动执行的最后时期需要医疗设备，且研究人员和实验设备这两种资源量是变动的。
RCPSP在组合优化中属于NP-hard问题，其求解方法分为精确算法和启发式算法两大类。由于启发式算法与精确算法相比，操作简便灵活，易于移植，同时近年来先进进化算法和智能算法不断涌现，应用与智能算法相结合的启发式算法来求解RCPSP受到更多学者的青睐。2005年，Karaboga[3]提出了一种人工蜂群算法ABC(Artificial Bee Colony)，用以解决连续型多峰函数寻优问题。Akbari[4]等用ABC算法求解了基于优先权的标准RCPSP。不足之处在于，ABC算法针对连续性优化问题提出，参考文献[4]在求解RCPSP时也是按连续型问题进行处理的，没有考虑解的离散性特点。
本文在研究资源量随时间变动的RCPSP解的特点的基础上，提出了一种基于任务排列的离散的食物源编码方法，进而通过离散人工蜂群算法DABC（Discrete Artificial Bee Colony）求解项目的优化调度方案。
1 问题描述
资源时变的RCPSP可描述如下：设项目的任务集为J={0,1,2,…,n,n+1}，任务工时已知且任务不可拆分，任务0和任务n+1为虚任务，工期为0,分别代表开始任务和结束任务。sj、fj、dj分别表示第j项任务的开始时间、结束时间和总耗时，其中sj=fj-dj。每项任务必须在其所有的紧前任务完成后方能开始，Pj为任务j的紧前任务集合。设项目共有K种可更新资源，每种可用资源的最大限额随项目执行的时间而变化，则第k种资源在t时刻的最大可用限额为Rkt，t为项目执行中的每一时刻（t=1，2，…，T），T为项目工期。每个任务对资源的需求量为常量，第j项任务对第k种资源的需求量为rjk。A(t)代表t时刻正在执行的任务的集合。项目调度的优化目标是项目工期最短，则建立该问题的数学模型为：
2 人工蜂群算法的基本原理
ABC算法是一种模拟自然蜜蜂觅食中群体智能行为的元启发算法。该算法中人工蜂群包含三类蜂[3]：工作蜂、跟随蜂和侦察蜂。蜂群按数量等分成两组，前一半是工作蜂，后一半是跟随蜂，另设一个侦察蜂。工作蜂在蜜源采蜜,并将蜜源信息带回，在蜂巢跳舞场以“摆尾舞”的方式与跟随蜂分享信息，其舞蹈形态与蜜源的蜂蜜量成正比。跟随蜂通过观察工作蜂的舞蹈获得蜜源信息，然后依据蜜源的蜂蜜量选择一个适当的食物源，好蜜源将会吸引更多的跟随蜂去采蜜。当一个蜜源被多次采蜜后就会被抛弃，然后由侦察蜂去勘探一个新蜜源。蜂群中每一个工作蜂对应一个食物源，即蜜源，每个食物源的位置代表优化问题的一个可行解，食物源的蜂蜜量称为适应值，适应值的大小表征相关解的质量。适应值越大，蜂蜜量越多，解的质量越好。ABC算法的简明步骤如下：
(1)人工蜂群的初始化
(2)迭代
①将人工蜂放置到食物源采蜜；
②将跟随蜂放置到食物源采蜜；
③派侦察蜂寻找新的食物源；
④更新目前为止找到的最好食物源。
(3)停止(满足迭代停止条件)
工作蜂有SN个，xi是一个D维向量，代表工作蜂i对应的食物源。每次迭代工作蜂i在原食物源xi的基础上再生成候选食物源vi，候选食物源vi由下式生成：
初始食物源的位置需要通过调度生成机制产生可行调度方案。本文采用改进的串行调度生成机制来生成初始食物源。改进的串行调度包含l=1，2，…，n个阶段，每个阶段在先序任务已处理完的待处理任务集合中随机地选择一个任务并安排其执行时间，任务安排遵循在满足随时间变动的资源限制的条件下开始时间越早越好的原则。
3.2 候选食物源的生成
ABC算法中候选食物源的生成方式是优化效果和效率好坏的关键。本文基于任务排列的食物源位置编码对应了项目调度方案，生成候选食物源时既要保持食物源编码的离散性又要保持食物源编码对应的调度方案的可行性，为此本文采用了一种新的候选食物源生成方法。
仍以图1所示项目为例来说明候选食物源的生成方法，设食物源xi=(1，2，4，5，3，6)，选定的相邻食物源xk=(1，3，2，4，5，6)，随机生成一位d=3。则候选食物源vi的生成方法为：vi的前两个元素取xi的前两个元素(1，2)，去除xk中与xi的前两个元素相同的元素即得(3，4，5，6)，取该矩阵中第一个元素为vi的第三个元素，则vi的前三个元素取为(1，2，3)，再从xi中去除(1，2，3)得到(4，5，6)作为vi的后三个元素。这样得到vi=(1，2，
3，4，5，6)。可以证明，采用这种方法得到的候选食物源满足项目任务的先序关系，是可行调度[5]。
3.3 适应值函数
DABC算法中食物源位置编码唯一对应了一种项目调度的任务排列方案，由这一方案可进一步得到任务的时间安排。时间安排也是在串行调度基础上，遵循在满足随时间变动的资源限制的条件下，开始时间越早越好的原则。这样就得到了该食物源对应的任务时间安排和项目工期。资源时变的RCPSP的优化目标是项目工期最短，工期越短意味着调度方案越好，也就意味着该方案所对应的食物源蜂蜜量越多，适应值越大。因此ABC算法中食物源xi的适应值fiti可由式(4)得到：
3.4 DABC算法的基本框架
基于上述原理，求解资源时变的RCPSP的DABC算法实现的基本框架如图3所示。
4 算例仿真
为了验证DABC算法求解资源随时间变动的RCPSP的有效性，本文选取了一个有27个任务的项目算例[6]。如图4所示，任务0和任务26为虚任务，项目的可更新资源种类为3种，图中结点圆圈内数字为任务编号，结点上方数字为任务工期，结点下方数字分别为该任务对3种资源的使用量。
4.1 DABC求解标准RCPSP
设图4项目的三种资源在单位时间内最大使用限额在整个项目执行期间固定不变，均取为6[6]。首先对这一标准RCPSP问题进行验证计算。本文用ABC与DABC两种算法进行计算，图5给出了在10次仿真实验中平均优化过程，算法中蜂群数量NP=30，即食物源SN=15，最大迭代次数Cmax=200，trailmax=3。另外，ABC算法工作蜂生成候选食物源应用式(2)时取参数1=2，跟随蜂寻找候选食物源应用式(2)时，取参数?棕2=3。两种算法得到的项目工期的最优解均为64天，同时在最优工期下可以得到多种最优调度方案。优化结果与参考文献[6]一致。由图5可以看出DABC算法能很好地保持种群的多样性，优化效果要好于ABC算法，同时运算速度也要比ABC算法快。
由DABC算法得到在项目工期为64时最优食物源编码为[1,2,5,3,7,4,6,8,10,11,13,15,18,9,22,19,14,12,23,
17,16,20,21,24,25]，此时三种资源的利用情况如图6所示。
得到满足。
4.3 结果分析
章节4.1和章节4.2的计算是对同一项目在不同资源配置情况下得到的优化调度方案。前者中项目三种资源的总可用量为[384,384,384]，后者中项目三种资源的总可用量为[345,326,321]。从资源配置来看，前者中各种资源可用总量都要比后者的大，但是后者资源配置方法却使得项目工期缩短了整整20天，比前者完工期提前了31.25%。
由此可知，在资源总量保持不变甚至减少的情况下，通过调整资源在项目执行期间的配置情况，可以有效地缩短项目工期。这种调整资源配置的方法在实际项目的运作中无疑是可以操作和实现的。
本文采用一种新的离散人工蜂群算法对资源随时间变化的受限项目调度优化问题进行研究，这一问题是对标准RCPSP的必要补充和扩展。通过实例仿真可以得到如下结论：第一，本文所提出的DABC算法能有效地求解资源量随时间变动的RCPSP和标准RCPSP，比ABC算法有更好的收敛特性；第二，资源时变的RCPSP更符合项目实际，通过调整资源在项目执行中的配置情况，可以在保持可用资源总量不变或减少的情况下显著地缩短项目工期，提高资源利用率。这一结论在今后项目管理中应给予充分的重视。
参考文献
[1] KLEIN R.Project scheduling with time-varying resource constraints[J].International Journal of Production Research, 2000,38(16):3937-3952.
[2] HARTMANN S.Project scheduling under limited resources: Models, methods, and applications[M].Springer,Berlin, Germany,Lecture Notes in Economics and Mathematical Systems，1999:221.
[3] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TRO6, 2005.
[4] AKBARI R, ZEIGHAMI V, ZIARATI K.Artificial bee colony for resource constrained project scheduling problem [J].International Journal of Industrial Engineering Computations,2011,2(1): 45-60.
[5] HARTMANN S.A competitive genetic algorithm for resource-constrained project scheduling[J].Naval Research Logistics, 1998,45(7):733-750.
[6] Zhang Hong, Li Heng, TAM C M.Particle swarm optimization for resource-constrained project scheduling[J].International Journal of Project Management 2006,24(1):83-92.