关键链项目调度中的资源分配算法研究

崔南方,陈 雪,张 艳

(华中科技大学 管理学院 湖北 武汉 430074)

为了应对外部环境和项目本身的不确定性，构建一个具有强抗干扰能力的项目调度计划显得非常重要，因此，鲁棒性项目调度受到了广泛关注。如DEMEULEMEESTER等[1]研究表明，鲁棒性资源分配方法和关键链技术均可以有效提高项目调度的鲁棒性。GOLDRATT[2]提出了关键链项目调度方法,该方法综合考虑工序和资源约束来构建项目调度计划，并通过插入缓冲来提高项目调度的鲁棒性,目前对关键链项目调度的研究主要集中在识别关键链、计算缓冲方法等方面[3]。BIE等[4]提出了一种基于活动依赖性的缓冲区大小确定方法。ZHANG等[5-6]在考虑工序和资源约束的基础上，进一步考虑了活动之间的信息流，以最小化总协调成本为目标来确定关键链排序，并研究了模糊资源约束下项目调度问题的缓冲计算方法。YANG等[7]提出了一种基于任务优先级和关键链的多项目调度方法。

鲁棒性资源分配的目的是找到鲁棒性较好的资源传递路线来保护项目完工期。LEUS等[8]利用资源流网络、分支定界算法对鲁棒性资源分配问题进行求解。DEBLAERE等[9]以最小化项目惩罚成本为目标，提出了3种基于整数规划的资源分配的启发式算法和一种最小化项目惩罚成本的构建法MABO，并将这几种算法与平行调度生成计划和链式局部调度启发式算法做了比较，结果显示MABO算法得到的项目调度鲁棒性最好。而近几年关于资源分配算法的研究[10-11]主要关注于资源分配的算法效率，很少考虑资源分配算法的鲁棒性效果。

传统的关键链项目调度过程中并没有预先确定资源在活动间如何传递，资源一旦释放便可用于其他任一未完成活动。然而，实际项目的实施都会提前安排好资源(尤其是人力资源)的任务和流动。在项目开始前安排好资源，有利于决策者做好外部活动计划，有利于员工提前知道自己未来的工作[12]，所以在关键链项目调度中考虑资源分配很有必要。李俊亭[13]综合分析了关键链项目进度控制中的资源分配，提出了一种基于优先规则的资源配置方案，但这种方案是响应式的，没有在制定项目调度计划时考虑资源分配。

基于此，笔者将鲁棒性资源分配应用于关键链项目调度，提出了一种针对关键链项目调度的主动式资源分配方案来提高项目调度的鲁棒性，以便使关键链调度计划在执行过程中能够更好地抵御活动工期的不确定性，提高完工率。同时，通过大规模仿真实验进一步分析了多种不同的资源分配对关键链调度计划鲁棒性的影响，验证了算法的有效性。

1 资源分配

1.1 资源流网络

定义原始项目网络为G=(N,A)，N为节点集合，表示项目活动；A为箭线集合，代表活动之间的先后关系。节点集合N={0,1,2,…,n}，其中包括虚拟节点0和n。对于项目中的任意活动j，其工期为dj，对第k(k=1,2，…,K)种资源的需求量为rjk，而每种资源的可利用量为ak，其中虚拟节点0和n的工期和资源消耗量均为0。活动的实际开始时间为Sj，计划开始时间为sj。由分支定界算法得到的基准计划为S。

ARTIGUES等[14]最早提出资源流的概念，用来描述资源在活动之间的流动情况。资源流网络G′=(N,AR)与原始项目网络G=(N,A)的节点数相同，但是资源弧集合AR是连接节点i和节点j的箭线集合，且节点i和节点j之间存在任意一种资源k的资源流fijk(fijk>0)。假设每种资源k从虚拟开始活动流出的资源总量等于流入虚拟结束活动的总量，且等于该种资源的总可利用量ak，其数学表达式如式(1)所示。并且，一个可行的资源流网络还必须满足在每一个活动节点的流量守恒，即对于每种资源k和每个非虚拟活动i(i≠0,n)，流入该活动的总量必须等于流出量，且等于该活动的资源需求量rik，其数学表达式如式(2)所示。

∀k∈K

(1)

∀i∈N{0,n},∀k∈K

(2)

1.2 鲁棒性资源分配

项目调度的鲁棒性分为两类：第一类是质鲁棒性, 指整个项目的完成时间的稳定性,用按时完工率或完工期度量；第二类是解鲁棒性, 指活动开始时间的稳定性[15]。在关键链项目调度中，多用不确定情况下的平均完工率(质鲁棒性)衡量调度计划的鲁棒性。对于同一个项目，满足资源流网络约束的资源分配方案可能有多种，笔者用一个小项目算例说明资源分配方案给项目鲁棒性带来的影响。

项目用AON网络图表示，如图1所示，其中活动1和活动6分别为虚拟开始节点和虚拟结束节点，圆圈内数字代表活动编号，活动上方数字为活动时间，下方数字为活动的资源需求，该项目只涉及一种可更新资源，资源总量为4个单位。

图1 项目网络图

图2 资源分配方案a

图3 资源分配方案b

一种可行的资源分配方案a如图2所示，可看出完工期为4个单位，活动3的资源有一个来自活动4，另一个来自活动2。另一种资源分配方案b，如图3所示，可看出活动3所需的2个资源都来自活动4，完工期同样为4个单位。方案a中，活动2或活动4延迟1个单位时间都会造成活动3不能按时开工，从而使得整个工期延长。然而在其他条件相同的情况下，方案b中，只有活动4延迟会影响活动3，而活动2延迟1个单位开始并不会影响整个工期，这种方案下的项目完工率会更加稳定。可见，资源分配方案b的项目鲁棒性比方案a更好。

至此电动汽车最优出行的约束条件便已完成，配合联合目标函数，共同构成了电动汽车最优出行路径的规划模型。由此模型，便能求解出任意初始位置与终止位置的最优路径。

项目调度中考虑资源分配本身是一种NP难题，笔者将针对关键链项目调度，探索出一种具有较好鲁棒性的资源分配方案。

2 基于优先规则的主动式关键链资源分配算法

2.1 算法设计

关键链的长度决定了项目工期，所以欲使项目尽快完工则需要保证关键链顺利进行。根据TOC思想，非关键链要尽可能“迁就”关键链，尽可能不让非关键链活动的延迟影响关键链活动，即减少非关键链活动对关键链活动的资源约束。基于以上思想，笔者提出了关键链资源分配算法(critical chain resource allocation,CCRA)，该算法以关键链活动为核心，在不影响计划最短完工期的情况下，优先满足关键链活动的资源需求，尽量减少非关键链活动对关键链活动的资源约束，以保证关键链顺利进行，使得项目更加稳健地执行。算法按照活动开始时间的先后顺序，依次为其分配资源，提供资源的活动为已完成的活动，且分配资源时满足一定规则以得到鲁棒性较好的资源分配方案。具体步骤如下：

(1)构建基准调度计划并找出关键链。以最短工期为目标，使用DEMEULEMEESTER等[16]设计的分支定界算法生成项目基准调度计划S，通过活动最早开始时间和最晚开始时间找到关键链。

(2)生成资源待分配的活动顺序Sequence。首先根据基准调度计划，按照活动最早开始时间由小到大排列所有活动，开始时间相同的活动，先安排序号较小的活动。然后在开始时间相同的活动中将关键链活动提前(为了优先给关键链活动分配资源)，非关键链活动顺序不变，从而得到最终的资源待分配顺序Sequence。

(3)初始化各活动资源可供给数量，其值等于各活动资源需求。

(4)依次为Sequence中的待分配活动i找到可以为其提供资源的活动序列Supply_set(在活动i之前完成且资源供给不为零)，该序列确定了为活动i提供资源的活动先后顺序，其优先规则如下：①如果活动i是关键链活动，则优先用其紧前的关键链活动提供资源，再用紧前的非关键链活动提供资源，最后用其他可提供资源的活动(先完成的活动优先)提供资源；②如果活动i是非关键链活动，则优先用其紧前的非关键链活动提供资源，再用紧前的关键链活动提供资源，最后用其他可提供资源的活动(先完成的活动优先)提供资源。

(5)分配资源。用提供资源的活动集合Supply_set依次给当前待分配资源的活动i提供资源，更新活动i的资源需求和提供资源活动的供给数量，直到活动i的资源需求被满足。然后，转步骤(4)分配下一个活动，直到所有活动资源需求都被满足。

步骤(4)中选择先完成的活动优先提供资源是为了保证非关键链汇入关键链的总时差，因为时差越大，鲁棒性越好。另外，如果活动j要给活动i分配资源，则应尽可能多地分配资源(不超过活动i的资源需求量)，以减少额外资源约束。

2.2 算例说明

为了更直观地说明CCRA算法，笔者以图1的简单项目为例演示具体资源分配步骤。

(1)得到最小完工期对应的项目基准调度计划S=[0,0,2,0,2]。根据基准调度计划得到关键链为1→4→3→6。

(2)根据最早开始时间和关键链活动得到资源待分配顺序(不考虑虚拟活动)Sequence=[2,4,3,5]，其中活动2和活动4开始时间相同，但活动4是关键链活动，则活动4在活动2前被分配资源，得到最终活动资源分配序列Sequence=[4,2,3,5]。

(3)初始化各活动资源可供给数量，其值等于各活动资源需求。

(4)分配资源。根据Sequence首先给活动4分配资源：活动4开始时，可以提供资源的活动为Supply_set4=[1],则f1,4=3(此时，活动4资源需求变为0，活动1资源供给变为1)；接着分配活动2，Supply_set2=[1],则f1,2=1；分配活动3，Supply_set3=[4,2](此时活动4和活动2都可提供资源，但因为活动3是关键活动，优先让前序关键活动4提供资源),则f4,3=2(此时，活动3资源需求变为0)；分配活动5，Supply_set5=[2,4](因为活动5为非关键活动，优先让紧前非关键活动2提供资源),则f2,5=1；活动6为虚拟活动，需求为0，不作考虑。至此完成CCRA资源分配过程，得到资源分配结果即为图3所示的鲁棒性更好的分配方案。

对比两种资源分配方案可以看出，相比于资源分配方案a，方案b做到了尽量“迁就”关键链，减少了2→3和4→5的两个额外资源约束，且具体资源分配数量也有不同。

3 不同资源分配算法的对比分析

3.1 实验设计

为了验证笔者所提资源分配算法的有效性，笔者使用Matlab软件进行大规模仿真实验，选择了PSPLIB实例集J30中具有代表性的48个项目例子进行模拟仿真，比较不同的资源分配算法对关键链项目调度计划鲁棒性的影响。对比的资源分配算法包括：随机资源分配算法、MABO资源分配算法、笔者提出的关键链资源分配算法CCRA。随机资源分配算法在进行资源分配时不考虑任何鲁棒性绩效指标，实验中作为比较基准；MABO资源分配算法是目前资源受限型项目调度研究中能够获得较好鲁棒性的一种资源分配算法。

实验中关键链项目调度计划生成的具体步骤如下：①以最短工期为目标，构建项目基准调度计划S，找出关键链活动(使用文献[16]提出的分支定界算法得到S，使用文献[17]提出的方法查找关键链和非关键链)。②使用3种资源分配算法(随机、MABO、CCRA)得到具体资源分配方案。③根据工序约束和资源约束，分别重新确定非关键链(关键链不变)。④在非关键链与关键链汇合处插入汇入缓冲FB(使用剪切粘贴法，大小为50%的非关键链长度[18])，笔者不考虑项目缓冲。⑤调整缓冲大小解决二次资源冲突(断开关键链)，输出关键链调度计划。⑥将生成的1 000次模拟活动时间按照3种不同的调度计划执行，分别统计鲁棒性指标。

式中：wi为每个活动权重,表示该活动延迟一个时间单位开工所造成的损失；Si和Si*分别表示活动i的计划开始时间和仿真执行中的实际开始时间。

3.2 实验结果分析

3种资源分配算法的仿真结果如表1所示，MABO和CCRA两种算法相对随机资源分配的优化百分比统计如表2所示。由表1可知，随着活动工期不确定性(σ)的增加，3种方法各自的平均惩罚成本都增加，平均按时完工率降低，平均完工时间增加。符合项目的不确定越大，越会影响项目的执行的规律。结合表1和表2结果对比分析3种资源分配算法，在σ=0.3的水平下，平均按时完工率最高的是CCRA算法，为92.58%，优化百分比为2.66%；在σ=0.6的水平下，CCRA算法的平均按时完工率最高，为59.55%，提高比率为9.67%；在σ=0.9的水平下，完工率依然是CCRA算法表现最好。随着活动时间不确定性的增加，在按时完工率和平均完工时间方面，CCRA算法的效果一直保持最好，具有一致性。所以，就质鲁棒性而言，CCRA算法比另外两种算法更优。

表1 3种资源分配算法仿真结果

在解鲁棒性方面，当σ=0.3时，MABO算法的平均惩罚成本低于CCRA算法，而当σ=0.6和σ=0.9时，CCRA算法的平均惩罚成本低于MABO算法。可见，虽然MABO算法的目标函数是最小化惩罚成本，但是在“接力赛”执行策略中，效果并非一直最好。所以，就解鲁棒性而言，随着活动时间不确定性的增加，CCRA算法的表现也会比MABO算法好。出现这种结果的一种可能的解释是，当活动不确定性较小时，活动工期波动不大，因而缓冲消耗不大，在接力赛的执行策略下，CCRA算法的完工率高，活动基本提前完工，导致活动的实际开始时间与计划时间偏差较大；而随着活动时间不确定性的增大，CCRA算法在惩罚成本方面的优势就能体现出来，MABO算法因为计划完工期延期较多，完工率低，以致惩罚成本这一指标也不如CCRA算法。

表2 算法优化百分比 %

此外，实验还统计了3种算法的平均耗时，即48个项目生成关键链调度计划并执行该计划所耗平均时间(其他参数完全相同)：随机资源分配算法的平均耗时为14.311 s，CCRA算法的平均耗时为14.765 s，而MABO算法的平均耗时为314.611 s。可见，CCRA算法的效率较MABO算法有显著提高。因此，在制定项目调度计划时，运用不同的资源分配方案确实会影响项目执行的鲁棒性，并且，优先保证关键链上活动执行的资源分配方案能够有效提高项目的鲁棒性。

4 结论

将项目管理领域中相对独立的鲁棒性资源分配研究和关键链项目管理研究相结合，提出了新的能有效提高关键链项目调度计划鲁棒性的资源分配方法。在传统关键链项目调度过程中考虑鲁棒性资源分配，通过一个算例说明了资源分配方案的不同会对项目调度鲁棒性产生影响，进而针对关键链项目调度的特点，提出了关键链资源分配算法CCRA。CCRA算法的主要思想是优先满足关键链活动的资源需求，并尽量减少非关键链活动资源向关键链活动传递的路径，从而减少非关键活动对关键链活动的影响，保护项目完工期。

通过大规模仿真实验对比了3种不同的资源分配方法对关键链项目调度鲁棒性的影响，验证了CCRA算法的有效性。实验结果表明：活动执行时间不确定性(σ)越高，则项目完工率越低，惩罚成本越高；在同一活动时间不确定性水平下，CCRA算法得到的项目调度计划质鲁棒性(完工率、完工期)最好，解鲁棒性(惩罚成本)总体也优于其他两种算法；相比于目前效果较好的MABO资源分配算法，CCRA算法的计算效率更高。可见,不同的资源分配方案会影响关键链项目调度的鲁棒性，CCRA算法可以得到鲁棒性更好的关键链项目调度计划，更加适用于关键链项目调度。

未来有关关键链项目调度的研究，可进一步探究鲁棒性资源分配对缓冲控制会产生何种影响，以便为项目的缓冲控制提供更多的管理方法和启示。