基于EVM矩阵求解关键路径的方法

林铭德，戴一璟

(1.福建工程学院计算机与信息科学系，福建福州 350108;2.福建工程学院管理学院，福建福州 350108)

在建设工程中，进度计划是项目发展的关键，工程建设项目管理中用网络计划图来表示进度计划。用网络计划对建设项目进行进度控制，能明确表达各项工作之间的逻辑关系。通常在项目执行过程中，存在许多不可预知的因素，可能会影响到项目是否能按期完工，因此相对于进度计划，进度控制也同样重要。挣值法(earned value management，EVM)作为费用/进度的综合测评技术，最早由美国国防部在20世纪60年代将其纳入费用/进度控制系统标准中(C/SCSC的35条准则)。20世纪90年代后期，EVM的价值被重新肯定，美国国家标准协会发布了专门的EVMS标准ANSI/EIA748(1998年)，目前已成为用于现代企业和商业工程项目管理的重要方法。1977年至今，美国国防部已经用这种方法跟踪了800多个项目的绩效，极大地改善了项目超支和超期的恶性循环，节约了大量的经费和时间。

EVM通过计算项目的工期与成本，对项目的进度与成本执行绩效的度量，进行相应的偏差分析，并与项目原计划比较，纠正偏差或调整项目计划。但实际应用中，挣值法在使用上还存在一些局限和不足，尤其是在计划比较复杂的项目中，若挣值的计算过程中没有考虑关键路径，就有可能产生误导信息，影响对于进度的判断［1-2］。传统的关键路径算法［3］存在一些不足:①算法需要分别求出所有事件的最早发生时间和最迟发生时间以及每项活动的最早开始时间和最迟开始时间，然后判断哪些活动是关键活动，算法过程复杂;②算法执行完毕，只能知道哪些是关键活动，却不能统计从源点到汇点的关键路径数，也不能将每条关键路径输出。一些研究人员也对关键路径的算法进行了改进，文献［4］在广度优先搜索的基础上，给出了一种求解关键路径的算法，该算法采用图的十字链表结构形式，不需要进行拓扑排序求出所有关键活动，对传统算法进行了改进。该算法的优点是无需进行拓扑排序而求取关键路径;不足之处在于采用十字链表作存储结构，显得比较复杂;需要对图进行三次广度优先搜索，才能输出所有的关键活动，但不能把所有的关键路径输出。文献［5］在深度优先搜索的基础上，求出从源点到汇点的所有路径，经过分析比较后找出最长的路径，从而求取关键路径。由于在求解过程中需要进行多次递归回溯，算法的执行效率较低。文献［6］针对上述不足提出了一种在广度优先搜索基础上，利用优先队列，结合动态规划思想实现求解关键路径的算法。该算法使得时间复杂度降低为O(n+e)，然而，由于算法采用图的邻接表形式，以自底向上的方式计算最优值，并在该过程中记录一些有用信息，因此需要额外的存储空间，同时，采用一个按照入度值为优先级的优先队列排序。在输出所有关键路径时，需要将每个节点信息转换为一个二维数组，因此，该算法是以空间为代价换取时间。以上算法均未综合考虑节点变化的情况。

笔者针对传统的求解关键路径算法的不足，通过引入将AOE图邻接矩阵转变为EVM矩阵的思想，提出了一种新算法。算法具有如下特点:①能精确求出AOE图中从源点到汇点的所有关键路径、关键活动和长度;②算法简单、直观，在AOE图变为EVM树的过程中进行关键路径的求解，当矩阵转换完成时，关键路径也同时求解出来;③施工过程中节点的变化(增减节点，边权值变化)可较简易地通过EVM相关节点的变化实现新的计算，不需要重新计算所有的路径。

1 AOE网

定义1 建设工程的网络计划图［7-10］是一个AOE(activity on edge)网，边表示活动的网，是一个带权的有向无环图，其中节点表示事件(event)，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始，弧表示活动，权表示活动持续的时间。AOE网可用来估算工程的完成时间。由于整个工程只有一个开始点和一个完成点，故在正常的情况(无环)下，网中只有一个入度为零的点(起点或源点)和一个出度为零的点(终点或汇点)。

定义2 由于AOE网中有些活动可以并行地进行，因此完成工程的最短时间是从开始点到完成点的最长路径的长度(路径上各活动持续时间之和)。路径最长的路径叫做关键路径。图1是一个典型的AOE网。

图1 典型的AOE网

AOE网具有以下两个性质:①只有某节点所代表的事件完成后，从该节点出发的各有向边所代表的活动才能开始;②只有进入某节点的各有向边所代表的活动全部结束，该节点所代表的事件才能发生。

2 EVM矩阵

利用AOE网的邻接矩阵，由EVM生成算法计算得到的矩阵是一个EVM矩阵，该矩阵有以下性质:①EVM矩阵元素表示AOE网节点的编号。②AOE网源点编号0为EVM矩阵的第1列元素，非第1列的元素值为0表示无节点。③EVM矩阵的每一行表示AOE网的一条工作路径。④矩阵行中＜i，j＞表示节点i与节点j之间有直接前后序关系。⑤工作路径的长度为EVM矩阵的最后一列元素。⑥若AOE网发生变化，根据变化特点由相应的算法对EVM矩阵进行计算，得到的结果依旧是一个EVM矩阵。

3 EVM矩阵生成算法

按AOE网络节点和权值关系创建邻接矩阵G(i，j)，元素值为0表示节点i与节点j无直接前后序关系，非0则表示节点i与节点j有直接前后序关系，且元素值为边的权重。

EVM生成算法步骤如下:

(1)读取数组G第1行第1个到最后一个数组元素，找出非0数组元素(即源点的直接后序节点)，依顺序按非0数组元素列下标生成新的EVM矩阵G，共生成n行，n为非0元素个数(即源点的出度为n)。该数组为n×2，每一行第1列数组元素为0，即起点编号，第i行第2列则为数组G中第1行第i个非0数组元素的列下标，即起点的直接后序节点。EVM每行前后节点的权值length相加。

(2)设i=2，m为G的行数。

(3)若i＞m，则转移到步骤(8)，否则查找G的第i行，依次找出非0元素，共n个(即节点i的出度)。

(4)查找EVM矩阵G中元素最大值为i-1行，若查找到，则执行步骤(5);若查找不到，则转移到步骤(6)。

(5)将找到的节点复制n-1个，依次将步骤(3)找到的节点添加到步骤(3)找到和生成的EVM矩阵相应的队列中，并累加该节点与步骤(2)找到的节点的边的权值。

(6)继续查找EVM矩阵G下一个满足步骤(3)的行，若找到继续步骤(4)的操作，若找不到则转移到步骤(7)。

(7)i=i+1，返回到步骤(3)。

(8)输出EVM矩阵，每行为1个工作路径，权值最大的路径即为关键路径，结束。

4 Matlab实验仿真

4.1 EVM矩阵生成算法的Matlab部分代码

可将图1的AOE网络节点用邻接矩阵G表示，算法在Matlab 7.01a上实现。

4.2 实验仿真结果

(1)计算源点与直接后序节点连接结果:

(2)计算G第2行后得到的结果:

(3)计算G第3行后得到的结果:

(4)以此类推，计算最后一行的结果为EVM矩阵:

结果说明:最终得到EVM矩阵的每一行即为一条工作路径，由此可以轻易得到关键路径的长度为24，一共有3条路径可作为关键路径，分别为(0、1、3、6、8)、(0、2、4、5、6、8)和(0、2、5、6、8)，关键路径上的活动都是关键活动。

5 AOE网边权值变化、节点增减的算法

在AOE网络计划图中，常见的变化有以下几种(算法在Matlab仿真实现):

(1)边权值变化算法(节点数量及前后顺序没变)。假设图1中节点i=5和节点j=7连接的边的权值由kv1=4变成kv2=6。

其算法可先求出权值差delt(kv)=k2-k1，相应地只要在用笔者算法生成的EVM矩阵中找到所有包含相邻节点为〈i，j〉的行(即工作路径)，修改行路径累加权值length=length+delt(kv)即可，不需重新生成EVM矩阵，也不需要从源点开始重新计算路径的长度，能有效地减少计算的开销。

(2)节点(非源点汇点)的增加。假设在节点i与节点j之间增加一个节点k(k！=0-n)，节点i到节点k边的权值为kv;节点k的直接后序节点是节点m和节点n，边的权值分别为x和y，如图2所示。

图2 增加节点k后的AOE网络图

节点增加算法的步骤为:①在EVM矩阵中统计节点 k的直接后序节点编号集合〈i，k，j〉，i，j属于(0到n)，共k1个。②在EVM矩阵中依次查找包含有〈i，j〉(i，j为直接前序后序节点)的行(即原有路径，共k2行)，删除每行节点编号在节点i之后的所有节点。③重复步骤②直到EVM中没有包含〈i，j〉的行(路径)。④经过步骤②和步骤③，(0，…，i，j，…，qz)变为集合 rout=(0，…，i，k)，计算节点集合的权值qz1。⑤在EVM中查找包含k的第一个直接后序节点j的行，复制该行m节点之后所有的节点，得到节点集合(j，…，)。计算节点集合的权值qz2。⑥继续查找包含k的下个直接后序节点的行，重复步骤⑤，直到所有的节点k的直接后序节点都完成步骤⑤，设共有s个，集合节点不重复。⑦复制rout1，与所有步骤⑤得到的集合连接成新的行(即新的路径)，计算路径长度l=qz1+x+qz2并加入到EVM矩阵中。⑧结束。

EVM矩阵中的行就是增加节点k后所有的工作路径，权值最大的就是关键路径。

实验仿真:在图1的AOE网络节点3和节点6之间加入节点k，节点3到节点k边的权值为6，节点k到节点6边的权值为5，删除节点3到节点6的边，增加一条节点k到节点7的边，权值为5，如图2所示，按节点增加算法得到EVM，与之前的EVM相比，工作路径数量增加了1，由8条路径变为9条路径(改变节点的第1行和新增加最后一行)，关键路径数量由原来的3条变为现在的1条(即第1行，工作路径长度最大，为27):

(3)节点(非源点汇点)的减少。节点减少一般分两种情况，一种是将该节点k的直接前序节点i连接到该节点k的直接后序节点j;另一种是将该节点的直接前序节点i连接到其他节点j1，j2，…。

第一种情况算法步骤为:①在EVM矩阵中查找包含节点k(即要删除的节点)所在行(即包含节点k的路径)，在邻接矩阵 G中查找〈i，k〉和〈k，j〉的权值并累加，然后在该行中删除节点 k，计算权值 =原路径累加权值 -〈i，k〉和〈k，j〉的权值并累加+〈i，j〉边的权值length。②重复步骤①直到EVM矩阵所有的行都不含节点k。

实验仿真:将图2中的节点k删除，新增〈3，6〉边权值为 6，〈3，7〉边权值为 5，则按算法可得关键路径为2条，长度length=24。

第二种情况算法步骤为:①在EVM矩阵中依次查找节点k的直接前序节点i所在的行，复制该行起点到节点i的所有节点集合rout1=(0，…，i)。②在EVM矩阵中查找节点i的后序节点j1所在的行，复制该行节点j1开始到汇点的所有节点集合rout2=(j1，…，n)，n为汇点编号，形成新的路径rout=rout1∪rout2，计算路径长度，判断rout是否与EVM行重复，重复则转到步骤③，若不重复，则加入到EVM矩阵中。③重复步骤②，直到节点i的后序节点都完成，转移到步骤④。④重复步骤①，直到所有节点k的直接前序节点都完成，结束。

根据笔者设计的EVM矩阵生成算法，再加入所设计的边和节点变化算法可设计出一个带反馈的关键路径计算的模型，如图3所示。

6 结论

图3 EVM矩阵求解AOE网关键路径模型

笔者在AOE网邻接矩阵的基础上，给出了一种新的求解关键路径的算法，该算法借助图的邻接矩阵结构，进行关键路径的求解。整个求解过程不需要对AOE网进行多次遍历搜索。该算法考虑了AOE网的各种变化情况并进行处理，如网的边权值的变化，节点的增减。因此，该算法具有更高的健壮性，算法简单直观，且易于操作。通过仿真实验进行比较，该算法较传统的算法更具全面性，在求解所有工作路径的同时求解出所有关键路径，具有一定的实用性。

［1］贺桂珍，吕永龙，刘达朱，等.挣值管理在环境审计中的应用［J］.审计研究，2007(2):3-8.

［2］戚安邦.项目挣值分析方法中的错误与解决方案［J］.数量经济与技术经济研究，2004(5):63-68.

［3］严蔚敏，吴伟民.数据结构(C语言版)［M］.北京:清华大学出版社，1997:17-98.

［4］徐凤生，黄倩.关键路径求解的新算法［J］.计算机应用，2004，24(12):108-109.

［5］孟繁桢.求关键路径的一个算法［J］.计算机工程，2001，21(4):6-9.

［6］刘芳，王玲.基于动态规划思想求解关键路径的算法［J］.计算机应用，2006，26(6):1440-1442.

［7］陈建新，唐海.有向无环图分层算法研究［J］.华中师范大学学报:自然科学版，2008，42(3):359-363.

［8］韩中，高建民，陈富民，等.面向对象的流程工业系统有向无环图建模［J］.计算机工程，2009，35(8):23-25.

［9］方霞，潘梅森，席金菊.网络计划图合法性检测改进算法［J］.计算机工程与应用，2010，46(35):222-224.

［10］杨婧，陈英武.项目网络拓扑结构与关键路径相关性仿真分析［J］.系统仿真学报，2011，23(12):2721-2726.