《aoe关键路径》word版

《《aoe关键路径》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、6.4.4关键路径一、AOE网与AOV-网相对应的是AOE-网(ActivityOnEdge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。例如，图6.22是一个假想的有11项活动的AOE-网。其中有9个事件v0，v1，v2，…，v8，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v0表示整个工程开始，v8表示整个工程结束，v4表示a4和a5已经完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天等。图6

2、.22一个AOE网和AOV-网不同，对AOE-网有待研究的问题是：(1)完成整项工程至少需要多少时间?(2)哪些活动是影响工程进度的关键?由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(CriticalPath)。假设开始点是v0，从v0到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动的最迟开始时间l(i)，这是在不推

3、迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。例如在图6.22中，v0是源点，v8是汇点，关键路径有两条：(v0，v1，v4，v6，v8)或(v0，v1，v4，v7，v8)，长序均为18。关键活动为(a1，a4，a7，a10)或(a1，a4，a8，a11)。比如，关键活动a1需要6天完成，如果a1提前1天，整个

4、工程也可提前1天完成。所以不论是估算工期，还是研究如何加快工程进度，主要问题就在于找到AOE-网的关键路径。58如何确定关键路径，首先定义4个描述量。(1)事件vi的最早发生时间ve(i)进入事件vi的每一活动都结束，vi才可发生，所以ve(i)是从源点到vi的最长路径长度。求ve(i)的值，可根据拓扑顺序从源点开始到汇点递推，通常将工程开始顶点事件v0的最早发生时间定义为0，即：ve(0)=0ve(i)=Max{ve(k)+wk,i}∈T，1≤i≤n-1其中，T是所有以vi为头的弧的集合，wk,i是弧的权值，即对应活动的持续时间。(2)事件vi

5、的最迟发生时间vl(i)事件vi的发生不得延误vi的每一后继事件的最迟发生时间。为了不拖延工期，vi的最迟发生时间不得迟于其后继事件vk的最迟发生时间减去活动的持续时间。求出ve(i)后可根据逆拓扑顺序从汇点开始向源点递推，求出vl(i)。vl(n-1)=ve(n-1)vl(i)=Min{vl(k)－wi,k}∈S，0≤i≤n-2其中，S是所有以vi为尾的弧的集合，wi,k是弧的权值。(3)活动ai=的最早开始时间e(i)只有事件vj发生了，活动ai才能开始。所以，活动ai的最早开始时间等于事件vj的最早发生时间ve(j)，即：e(

6、i)=ve(j)(4)活动ai=的最晚开始时间l(i)活动ai的开始时间需保证不延误事件vk的最迟发生时间。所以活动ai的最迟开始时间l(i)等于事件vk的最迟发生时间vl(k)减去活动ai的持续时间wj,k，即：l(i)=vl(k)－wj,k显然，对于关键活动而言，e(i)=l(i)。对于非关键活动，l(i)－e(i)的值是该工程的期限余量，在此范围内的适度延误不会影响整个工程的工期。一个活动ai的最晚开始时间l(i)和最早开始时间e(i)的差值l(i)－e(i)是该活动完成的时间余量。它是在不增加完成整个工程所需的总时间的情况下，活动ai可以拖延的时间。当一活动的时间余

7、量为零时，说明该活动必须如期完成，否则就会拖延整个工程的进度。所以称l(i)－e(i)=0，即l(i)=e(i)时的ai是关键活动。二、关键路径求解的过程(1)输入e条弧，建立AOE-网的存储结构。(2)从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i](1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。(3)从