一种基于PERT的资源优化新方法

武小平，安 静，熊高江

（1.西安邮电大学 经济管理学院，西安 710061；2.陕西地矿第二综合物探大队，西安 710016）

0 引言

目前，解决有限资源优化问题的方法有最小工作时差优先法（MINSLK）、最小最迟完成时间优先法（LFT）和资源进度安排法（RSM），其中RSM法是本文所采用方法的基础[2]；在这些方法的基础上乌日娜、徐方舟等[3]提出项目资源约束下资源优化的一种启发式算法，减少了涉及变量和计算量，但是在工期计算中涉及工作顺序并不适用于时序性强的项目；陈志勇、杜志达[4]提出用随机数产生的随机优先度来区分平行活动的先后关系，使用随机搜索算法进行寻优；李岚[5]提出基于网络图时间参数UTM算法的施工项目资源优化；魏欣海[6]提出水利工程中资源有限优化工期的方法。

本文的资源优化算法是在PERT基础上根据劳动密集型项目所面临的实际情况合理地做出创新和改进，由于考虑到项目的资源、面临的风险和消耗的成本对工期的影响，运用了层次分析法计算了影响因素的权重，以上文献在资源优化过程中很少考虑资源、风险和成本对工期的影响，本文在考虑这三个因素对工期影响的情况下提出了新的求解网络计划资源优化方法。

1 问题描述和优化策略设计

1.1 问题描述

给定一个进度计划网络图，假设工作（i-j）是其中的一个工作，在某个时间段里不可能只进行（i-j）工作，会存在与（i-j）并行的工作，那么在该时间段或工作之间存在交叠时间段时，对资源的需求量就会增加，如何配置能够保证这种增加不超过资源限量，且在不超过资源限量的基础上实现工期最短。

1.2 优化策略设计

在资源有限的条件下，以调整相应工作后的工期最短为目标。这里着重讨论每项工作资源强度固定和每项工作连续（工作内部不可中断）情况下的优化方法。那么相应的优化策略就要在此限制条件下进行。因此，如何调整工序延后时间，使得所有工作结束时工期最短？为了研究方便，下面给出3个限制条件：

（1）时序关系：有些工作可以同时进行，而有些工作则必须在其他若干项工作完成之后才能进行，把工作之间的这种限制关系称作时序关系。

（2）工序工作连续性：为保证工序工作合理性，在前一次资源分配时已经进行的工作在后续分配中不可中断。

（3）人力资源约束：各工序调整后要保证资源曲线在资源限量下方，不超出资源限量。在网络计划中，各项工作所需资源总数Zi-j是一个常数,它等于工作的资源需要量强度Ri-j与相应工作持续时间Di-j的乘积，各项工作所需资源总数为：Zi-j=Ri-j×Di-j。

本文重点讨论工作资源强度固定，工作内部连续不可中断的情况，优化策略如下：

（1）先根据初始网络计划图确定可能同时进行的所有工作 F（k）

在第k次分配时，会存在几项工作同时进行，但是前提是这几项工作的紧前工作均完成了，把这几项工作定义为工作集合F（k）。

（2）计算在t（AS_AF）阶段同时进行的工作总资源强度∑R

参加第k次资源分配的各项工作，在t（AS—AF）时间段的总资源数量应该为在该阶段参加工作的资源强度加和。将∑R与资源限量Q进行比较∑R＞Q，则在该时段参加的工作要延后进行；∑R≤Q，则该时段参加的工作不需要延后进行。

（3）表示同时进行工作的开始时间ASi-j，持续时间Di-j和结束时间AFi-j

由于工作连续性：AFi-j=ASi-j+Di-j。

（4）各工作持续时间不同，就存在几项工作只是在（ASi-j_AFi-j）过程中某一时段同时进行，把各工作同时进行的时间段表示为t（AS_AF）

若同时进行的工作为i-j,m-n和h-s则对同时进行工作开始时间到结束时间这一时间段取交集即：

（5）同时进行工作的时间段（tAS_AF）的结束时间为Ft

如同时工作时间t（AS_AF）=（1-3）则Ft=3。

（6）计算工作延后时间段△t

存在工作需要延后就是因为在t（AS_AF）时间段内同时进行的工作的资源强度的加和∑R大于资源限量Q，需要延后某项工作使该时间段内的工作强度加∑R≤Q。所以确定工作延后时间就是要判断在该时间段内同时进行的几项工作中每项工作与其他工作不同时进行的时间。每项工作与其他工作不同时进行时间为ti-j=Ft-ASi-j+1；该时间段内延后时间△t=min（ti-j）对应延后工作为i-j。

如工作1的持续时间D1=4，开始时间到结束时间（AS1-AF1）=（1-4）；工作2的持续时间D2=4，开始时间到结束时间（AS2-AF2）=（4-7）；工作3的持续时间D3=6，开始时间到结 束 时 间 （AS3-AF3）=（1-6）;可 知 道 t（AS_AF）= （AS1_AF1）∩（AS2_AF2）∩（AS3_AF3）=4，Ft=4。 工 作 1 延 后 时 间 t1=Ft-AS1+1=4-1+1=4；工作2延后时间t2=Ft-AS2+1=4-4+1=1；工作3延后时间t3=Ft-AS3+1=4-1+1=4；延后时间△t=min （t1，t2，t3）=1，工作2延后一天。

（7）在△t的基础上对延后工作开始时间和结束时间进行相应的调整，然后再进入下一阶段的分配

工作调整后的开始时间ASg=AS+△t；工作调整后的结束时间AFg=AF+△t。

（8）最终工期为最后一次分配中工作的结束时间为T=AF（maxK）

2 △t的讨论和影响因素权重计算

同一时段会出现许多并行工作，为了使该时段参加工作的总资源需求量小于资源限量，对该时段所有参加的工作进行调整，但是调整平行工作中的哪一项才能保证对工期影响尽可能小，这是对△t进行的讨论的重要原因。在资源受限条件下，选择对工期影响小的工作进行调整，对工期影响的大小可以直观的从各个工序的延后时间表现出来，延后时间大的工作对工期影响大，延后时间小的对工期影响小；但是通过计算发现同时段的并行工作的延后时间有可能出现想同值，这时候就需要对出现延后时间相同的工作进行权重分析，在延后时间相同的情况下，考虑工作紧后工作数（C1），工作紧后路线长度（C2）和工作资源强度（C3）三个非直观因素对工期的影响，构建层次结构图和判断矩阵进行权重分析。

2.1 △t的讨论

在优化策略中，延后时间△t的选取涉及多因素，使得延后时间△t的确定出现困难，由于工期由工作持续时间和工作延后时间组成，延后时间△t的选择影响整个工期，于是引入权重来明确各因素对△t影响程度，最终通过权重比较确定延后时间△t的选取。在确定延后时间△t的值时既简化了计算又避免使用穷举法计算工期。这里运用层次分析法（AHP）来确定权重。考虑到△t值对工期的影响，计算出并行工作的△t值，当△t值不同时，选择△t的最小值；当并行工作的△t值出现相同值且都为最小的△t值时，在资源优化过程中，要考虑△t值所对应的工序对资源优化整体水平的影响，层次结构如表1所示[7]。

表1 层次结构图

资源有限条件下，对工期优化进行决策时，往往难以把影响这一目标的各个因素做出精确的量化排序，这样会给决策者做出正确决策带来难度。层次分析法就是根据对各个因素之间的重要程度进行量化，再通过对量化结果的处理得到各个因素对于总目标的影响的一个排序，该排序是以数字的形式表现出来的，虽然这些数字并不能精确的量化各个指标的权重，但是它们清晰地显示出了对总目标的重要程度，给决策带来了便利。

2.2 影响因素权重计算

工作的紧后工作数目C1：工作的紧后工作越多，对整个工期影响越大，所以工作紧后工作数目可以作为衡量工作先后安排的指标；工作紧后路线长度C2：工作后续影响路线越长，对整个工期影响越大，所以工作紧后路线长度可以作为衡量工作先后安排的指标；工作资源强度C3:根据起始资源曲线图资源强度大的优先延后，使资源使用量不超过资源限量且资源分布较为均衡。如表2所示运用层次分析法对影响工期的因素工作紧后工作数（C1），工作紧后路线长度（C2）和工作资源强度（C3）进行权重比较[8-10]。

表2 B-C层次总排序

设C1（i,j）为工作（i,j）的紧后工作数目；设C2（i,j）为工作（i,j）的紧后线路的最大长度；设C3（i,j）为工作（i,j）的资源强度，为了使三个因素具有可比性，对它们进行归一化处理，即：

其中max是对所有工作求最大值。综上，得出权重Ω（i，j）=0.4SC1（i，j）+0.4SC2（i，j）+0.2SC3（i，j）。 对 工 作 延后时间△t进行讨论，可以保证在同一时间段内进行的各个工作延后时间中选取最小值，由于工期T=∑D+∑△t,在∑D固定情况下，∑△t取得最小值，使得工期最短。

3 合理性证明

总工期T为从网络计划图起始点到终点的最长路径的持续时间D和延后时间△t的加和时间。在整个网络中其中一条路径为i-j-k-l-m-n；总工期为：

由于 AS（i-j）+{D（i-j）+D（j-k）+D（k-L）+D（L-m）+D（m-n）} 是固 定 的 ，T（i-j）的 大 小 取 决 于 Δt（j-k）+ Δt（k-L）+ Δ t（L-m）+Δt（m-n）}，而上述方法是在既考虑资源限量又考虑工期影响因素情况下，整个网络中每条路径中每个工作增加的延后时间都是最小值，所以每条路径都取得该路径所有工作延后时间的最小值，即：

同上，算出整个工期所有路径工期，因为每条路径各工作的持续时间是固定的，而上述方法对每条路径增加的延后时间都是在满足要求下的最小值，所以最终总工期T为调整后所有路径工期的最大值也是相比较调整前工期增加的最小值。

4 算例分析

已知某项目工作流程以及各项工作的人员需用量和持续时间（工作箭线上方为人员需要量，箭线下方为工作持续时间），根据已知数据绘制初始网络计划图和资源曲线，该项目的资源限量Q=15万人，绘制的网络计划图如图1所示。

图1 初始网络计划图和资源曲线

从图1中可以观察到在第4、5、6、7、8、9、10、11、12天所参加的工作总需要人员已经超过了项目实际能够提供的人员数量，由于人员受到限制就保证不了每天同时进行的每项工作都能正常有序的进行，所以对4～12天的工作进行调整，在满足人员配备的情况下适当的根据优化策略进行调整。

依据优化策略对原始网络计划图进行调整，通过下页表3的形式将优化步骤呈现出来，可以观察到每项工作的资源需求量R、延后时间△t、对整个工期影响权重Ω以及调整次数K，而且优化步骤结束后,会得出优化后的工期T=Ft（K=10）=20。

从原来的PERT方法可以看出，计算过程相对复杂，涉及时差概念和多个变量，对网络计划调整一次就要重新计算每道工序的各项参数和重新绘制一次网络计划图，而且对于人员需要量超出人员限量的时间段内参与的工作，并没有一个量化概念来确定应该调整哪一项工作，也没有定性的确定每一项工作对整个项目工期的影响，所以调整工作的方法大多会采取穷举法，使得绘制的网络图增加，计算过程相对复杂，方法的实用性相对较差；而上述方法减少了项目涉及的变量，尤其是时差概念，时差相对于其他非工程领域理解和计算都相对复杂，减少原方法的时差概念也就简化了整个过程的计算量，相比原来的方法本文的方法以延后时间△t的大小定量描述每项工作调整后对工期的影响，根据延后时间△t的值确定调整该时段哪一项工作；延后时间△t=Ft-AS+1的值与每项工作的开始时间和结束时间有关系，在同一时间段就有可能出现相同的延后时间，就需要判断延后时间相同的工作对项目工期的影响，新方法借助层次分析法定性地判断各个工作对项目工期的影响，确定在延后时间相同的情况下应该调整哪一项工作。根据表3可以画出调整过后的网络计划图，如下页图2所示。

上述策略通过表格的方式清楚地呈现出每道工序的工作顺序、延后时间、影响因素的权重和工期，不需要重复多次绘制调整网络计划图，根据表3中的数据就可以画出最终优化网络图，将整个优化过程清晰地呈现出来，由于不涉及时差的概念对于项目工程以外的领域进行扩展和研究就会相对容易。

表3优化过程

图2优化策略调整后的网络计划图和资源曲线

5 总结

本文设计的优化方法是在人员受限的条件下，基于对整个项目的资源消耗、面临风险和成本需求的考虑，在保证任何时段人员需求不超过人员限量的情况下使整个项目实施工期最短，并且在实例分析中也证明了此方法的适用性。该优化方法在网络计划的资源优化中应用前景广泛，不再涉及传统方法中的时差概念，理解和掌握起来相对容易，区别于RSM方法，不再是根据某个单一条件来调整工作，开始考虑定量和定性相结合的方法来确定调整工序，使得在人员配置优化的条件下既保证了调整工作后对工期影响较小又提高了工作的时效性和顾客的满意度，这在服务行业发展迅速的时代至关重要，但是针对大型复杂网络计算步骤偏多，如何运用优化理论，软件计算进行处理，可作为进一步研究方向。