在项目管理中,关键路径是指网络终端元素的元素的序列,该序列具有最长的总工期并决定了整个项目的最短完成时间。
求关键路径的算法分析
(1) 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径; (2) 只有缩短关键活动的工期才有可能缩短工期; (3) 若一个关键活动不在所有的关键路径上,减少它并不能减少工期; (4) 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。
探寻关键路径
AOE网
用顶点表示事件,弧表示活动,弧上的权值表示活动持续的时间的有向图叫AOE(Activity On Edge Network)网 。AOE网常用于估算工程完成时间。例如: 图1
图1 是一个网。其中有9个事件v1,v2,…,v9;11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如 v1表示整个工程开始,v9 表示整个工程结束。V5表示活动,a4和a5已经完成,活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。
AOE 网具有的性质
只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。 只有在进入某一顶点的各有向边所代表的活动都已经结束,该顶点所代表的事件才能发生。 表示实际工程计划的AOE网应该是无环的,并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。 2)
最早发生时间和最晚发生时间的定义
可以采取如下步骤求得关键活动: A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。 Ve(k)=max{ve(j) dut(<j,k>)} ( 1.1 ) j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。 如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n,则说明网中有环,不能求出关键路径,算法结束。 表1
B、从完成顶点 v n 出发,令vl(n)=ve(n),按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-dut(<j,k>)} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。 C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j);最晚开始时间: l(i)=vl(k)-dut(<j,k>) 若某条弧满足 e(i)=l(i) ,则它是关键活动。 对于图1所示的 AOE 网,按以上步骤的计算结果见表1,可得到a1 , a4 , a7 , a8 , a10 , a11 是关键活动。
AOE 网的关键路径
图2
这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条,如图7.21的AOE网中有二条关键路径,(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它们的路径长度都是16 。如图2所示:
AOE网研究的问题
(1) 完成整个工程至少需要多少时间; (2) 哪些活动是影响工程的关键。 1956年,美国杜邦公司提出关键路径法,并于1957年首先用于1000万美元化工厂建设,工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中,节省了100万美元。
关键路径的几个术语
(1) 关键路径 从源点到汇点的路径长度最长的路径叫关键路径。 (2) 活动开始的最早时间e(i) (3) 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动。 (4) 事件开始的最早时间ve(i) (5) 事件开始的最晚时间vl(i) 设活动ai由弧<j,k>(即从顶点j到k)表示,其持续时间记为dut(<j,k>),则 e(i)=ve(j) l(i)=vl(k)-dut(<j,k>) (6_6_1) 求ve(i)和vl(j)分两步: · 从ve(1)=0开始向前递推 ve(j)=Max{ ve(i)+dut(<i,j>) } (6_6_2) <i,j>T, 2<=j<=n 其中,T是所有以j为弧头的弧的集合。 · 从vl(n)=ve(n)开始向后递推 vl(i)=Min{ vl(j)-dut(<i,j>) } (6_6_3) <i,j>S, 1<=i<=n-1 其中,S是所有以i为弧尾的弧的集合。 两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。 4、 求关键路径的算法 (1) 输入e条弧<j,k>,建立AOE网的存储结构。 (2) 从源点v1出发,令ve(1)=0,求 ve(j) 2<=j<=n。 (3) 从汇点vn出发,令vl(n)=ve(n),求 vl(i) 1<=i<=n-1。 (4) 根据各顶点的ve和vl值,求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s),其中e(s)=l(s)的为关键活动。 求关键路径是在拓扑排序的前提下进行的,不能进行拓扑排序,自然也不能求关键路径。 Status ToplogicalSort(ALGraph G,stack &T){ FindInDegree(G,indegree); InitStack(S);count=0; ve[0..G.vexnum-1]=0; while(!StackEmpty(S)) { Pop(S,j);Push(T,j); ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; if(--indegree[k]==0) Push(S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<G.vexnum) return ERROR; else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..G.vexnum-1]=ve[0..G.vexnum-1]; while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; dut=*(p->info); if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; } for(j=0;j<G.vexnum;++j) for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; dut=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?’*’:’’; printf(j,kdut,ee,el,tag); } }
温馨提示:答案为网友推荐,仅供参考