精华内容
下载资源
问答
  • 关键路径

    千次阅读 2019-04-25 14:19:34
    为了求出关键路径,我们使用一下算法: 1.求出到达各个状态的最早时间(按最大计) 这个过程是要从源点开始向汇点顺推: V1是源点,其最早开始时间是0。 V2、V3、V4最早时间分别是是6、4、5。 对于V5而言,V2到...

    原理:

    例图

     

    如上图,是一个AOE网,点表示状态,边表示活动及其所需要的时间。为了求出关键路径,我们使用一下算法:

    1.求出到达各个状态的最早时间(按最大计)


    这个过程是要从源点开始向汇点顺推:

    1. V1是源点,其最早开始时间是0。
    2. V2、V3、V4最早时间分别是是6、4、5。
    3. 对于V5而言,V2到V5所花费时间是6+1=7,而V3到V5所花费时间是4+1=5。我们要按最大计,也就是V5最早时间是max{7,5}=7,按最大计是因为只有活动a4和a5同时完成了,才能到达V5状态。V3到V5需要5分钟,但是此时a4活动尚未完成(7分钟),所以都不能算到达V5,故而要按最大计。
    4. V6只有从V4到达,所以V6的最早完成时间是(5+2=)7。
    5. 同理,V7最早完成时间是16。
    6. 对于V8而言,和V5处理方法一致。V8=max{V5+7,V6+4}={7+7,7+4}=14。
    7. V9可算出是18。

    这样,我们可以得到各个状态的最早时间的表:

    最早时间表

    2.求出到达各个状态的最晚时间(按最小计)


    这个过程是要从汇点开始向源点逆推:

    1. V9完成时间为18,最V7最迟开始时间是(18-2=)16

      逆推


      因为活动a10所需时间2。如果V7开始时间比16晚,则V9完成时间就会比18晚,这显然不对。
    2. 同理,V8最迟开始时间为14。
    3. 对于V5而言,可以从V7、V8两个点开始向前推算,此时要按最小计,即V5(最晚)=min{V7-9,V8-7}=min{16-9,14-7}=7。
      请注意!!,min{V7-9,V8-7}中,V7、V8取的都是前面算出的最迟开始时间(而不是最早开始时间)。

      按最小计


      最小计,是因为如果按最大计去计算V5的最晚开始时间,那么加上a7和a8的活动时间后,V7、V8至少有一个会比之前逆推算得出的最晚时间还要晚,这就发生了错误。
    4. 同理,可计算出剩下的点

    这样,我们可以得到各个状态的最晚时间的表:

    最晚时间表

     

    事实上,源点和汇点的最晚时间和最早时间必定是相同的。

    3.求出关键路径


    求出关键活动,则关键活动所在路径即为关键路径

    对于a1:

     

    这表明,a1最早只能从0时刻开始,最晚也只能从(6-6=)0时刻开始,因此,a1是关键活动。

    对于a2:

     


    a2最早要从0时刻开始,但是它最晚开始时间却是(6-4=)2。也就是说,从0开始做,4时刻即完成;从2开始做,6时刻恰好完成。从而在[0,2]区间内任意时间开始做a2都能保证按时完成。(请区别顶点的最早最晚和活动的最早最晚时间。图示中的最早最晚是顶点状态的时间,活动的最早最晚开始时间却是基于此来计算的)。
    由于a2的开始时间是不定的,所以它不能主导工程的进度,从而它不是关键活动。

     

    一般的,

     


    活动用时X时间,它最早要从E1时刻开始(一开始就开始),最晚要从L2-X时刻开始(即恰好完成)。所以,如果它是关键活动,则必然有E1=L2-X,否则它就不是关键活动。

     

    值得注意的是,顶点的最早开始时间等于最晚开始时间 是 该顶点处于关键路径 的 不充分不必要条件。

     


    上表中蓝色底纹表示的点即为处于关键路径的点。尽管它们的最早时间与最晚时间都相同,但是这与它们是否为关键路径的点无关。因为这还取决于起始点的最早时间以及活动时间。

     

    关键路径


    原文:https://www.jianshu.com/p/1857ed4d8128

     

    代码实现:

    设一个工程有11项活动,9个事件,事件V1 ----- 表示整个工程开始,事件V9 ----- 表示整个工程结束。

    每个事件的开始必须是它之前的活动已完成。例如:事件V2,V3,V4的开始必须是活动a1,a2,a3完成了。

    这时我们会关注两个问题:

    (1)完成整个项目需要多少时间?

    (2)哪些活动是影响工程进度的关键?
    定义:

    关键路径:AOE-网中,从起点到终点最长的路径的长度(长度指的是路径上边的权重和)

    关键活动:关键路径上的活动

    AOE网:也叫边表示活动的网。AOE网是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间。

    Ve[j] :表示事件j 的最早发生时间

    VI[j]: 表示事件j 的最迟发生时间

    e[i]:表示活动ai的最早开始时间

    l[i]:表示活动ai的最迟开始时间
    方法:

    以邻接矩阵作为存储结构

    1、从原点V1出发,令Ve[1] = 1,拓扑排序求各个顶点的Ve[i]

    2、从Vn出发,令Vl[n] = Ve[n] ,逆拓扑排序求出各个顶点的Vl[i]

    3、根据各顶点的Ve和Vl值,计算每条弧的e[i] 和 l[i],找出e[i] = l[i] 的关键活动

    简单来说:

    顺拓扑排序取大值求出Ve数组,逆拓扑序列取小值求出Vl数组,最后找出Ve[i] = Vl[i] 的顶点,即关键路径上的顶点,将这些顶点连接起来的路径叫关键路径。
    实现:
    手动实现:

     
    代码实现:

        #include <iostream>
        #include <cstring>
        using namespace std;
        #define N 13
        int main()
        {
            int map[N][N]; //邻接矩阵
            // 初始化矩阵的值全部为0表示各个顶点间没有边连接
            for(int i = 0; i <= N-1; i++){
                for(int j = 0; j <= N-1; j++){
                    map[i][j] = -1;
                }
            }
         
            int a,b,values;  //定义a,b,用来输入,values存储权值
            int v,l;  //顶点数和边数
         
            cout << "请输入顶点数:";
            cin >> v;
            cout << "请输入边数:";
            cin >> l;
            cout << "请输入边:" << endl;
         
            for(int i = 1; i <= l; i++){
                    cin >> a >> b >> values;
                    map[a][b] = values; // 表示顶点a指向顶点b的边,且权值为values
            }
         
            int k; //用于计算度数
            int ID[N],OD[N];  //储存各顶点的入度和出度
            int ve[N],vl[N];  //顺拓扑序列取大,逆拓扑序列取小
            memset(ve,0,sizeof(ve));  //初始化ve数组全为0
         
            for(int i = 1; i <= v; i++){  // 计算入度
                k = 0;
                for(int j = 1; j <= v; j++){
                    if(map[j][i] != -1) //如果顶点j到顶点i有边,则顶点i的入度+1
                        k++;
                }
                ID[i] = k;
            }
            for(int i = 1; i <= v; i++){  //顺拓扑序列
                if(ID[i] == 0){
                    for(int j = 1; j <= v; j++){
                        if(map[i][j] != -1){     //如果顶点j与顶点i有边,则删除这条边,并且顶点j的入度-1
                            if(ve[j] < map[i][j] + ve[i])  //取大值
                                ve[j] = map[i][j] + ve[i];
                            ID[j]--;
                        }
                    }
                }
            }
            for(int i = 1; i <= v; i++){  // 计算出度
                k = 0;
                for(int j = 1; j <= v; j++){
                    if(map[i][j] != -1)
                        k++;
                }
                OD[i] = k;
            }
         
            k = v;
            for(int i = 1; i <= v; i++)    //将 vl 数组全部初始化为ve最后一顶点的值
               vl[i] = ve[k];
         
            for(int i = k; i>=1; i--){  //逆拓扑序列
                if(OD[i] == 0){
                    for(int j = 1; j <= v; j++){
                        if(map[j][i] != -1){
                            if(vl[j] > vl[i] - map[j][i])   //取小值
                                vl[j] = vl[i] - map[j][i];
                            OD[j]--;
                        }
                    }
                }
            }
            cout << "****************************\n";
            cout << "Ve数组:";
            for(int i = 1; i <= k; i++){
                cout << ve[i] << " ";
            }
            cout << endl;
            cout << "Ve数组:";
            for(int i = 1; i <= k; i++){
                cout << vl[i] << " ";
            }
            cout << "\n****************************\n";
         
            cout << "关键路径:";
            for(int i = 1; i <= k - 1; i++){
                if(ve[i] == vl[i]){
                    cout << i << "->";
                }
            }
            cout << k << endl;
            return 0;
        }

    结果:

     

    原文:https://blog.csdn.net/qq_37618797/article/details/81114696

    展开全文
  • AOE网络-关键路径

    千次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。先回顾下拓扑排序中讲到的AOV网络,AOV网络即“Activity On Vertex”,即图上每一个顶点表示的是一个事件或者说一个活动,而顶点...

    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。先回顾下拓扑排序中讲到的AOV网络,AOV网络即“Activity On Vertex”,即图上每一个顶点表示的是一个事件或者说一个活动,而顶点之间的有向边则表示这两个活动发生的先后顺序。

    在关键路径这个问题中,AOE网络指的是“Activity On Edge”,即图上的每一条边表示的是一个活动,顶点作为各个“入度边事件”的汇集点,意思是,某个顶点,当所有的“入度边事件”的活动全部完成后,才开始进行该顶点的“出度边事件”。在AOE网络中只有一个入度为零的点,称作源头顶点,和一个出度为零的目的顶点。AOE网络通常用来安排一些项目的工序。

    上图表示的就是AOE网络中的,有向边上方表示该活动的持续时间,也就是完成该活动要多长时间,有向边下方表示该活动的机动时间,机动时间是什么呢,下面等拿例子来讲解时再解释。顶点里又分为三部分,一部分是存放顶点的编号,另外两部分分别存放活动的最早完成时间(即到达该点用时最短),和最晚完成时间(即到达该点用时最长)。

    下面根据一个具体的例子来看到底什么是AOE网络和关键路径:

    在下面的有向无环图中,V1是源头顶点(即开始点),到V10结束,每一条边代表一个活动,有向边的方向表示活动完成后到达哪一个汇集点。有向边上方表示的是活动完成所需要的时间(也是持续时间)。假设活动a7和a8想要开始,那么必须等到活动a4和a5都完成后,a7和a8才能开始。

    还有一种更复杂的情况是:如果活动a7和a8要开始,必须要等活动a4、a5和a6都完成后,才能开始a7和a8活动(因为在AOE网络中有些活动是可以并行地进行的)。这样的情况怎么办?我们不可以把V5和V6顶点连接起来,为什么?因为我们看a9这个活动,它的开始与否和活动a4,a5均无关系,活动a9只需等待活动a6完成他就可以开始了,所以如果我们把V5和V6顶点连接起来,是不行的。那要怎么办?方法是用一个无向虚线(标记线)把V5和V6连接,边上的权值设为0,如图:

    接着根据这个有向无环图,我们看看从开始到结束整个工程活动需要的最短时间是多少?答案是从开始点出发到完成点的最长路径的长度(这里的最长路径长度指的是路径上各个活动持续时间之和,不是指路径上边的数目)。从开始点到结束点的最长路径就叫做关键路径。从开始结点V1开始,它的最早完成时间自然是0了,然后到V2结点,V2结点的最早完成时间是5,同理V3结点最早需要4天完成,V4结点最早需要6天完成。

    接着到下一组,从V4到V6顶点,活动a6需要7天,所以V6上填上6+7=13,也就是说到达V6需要最早完成时间是13天。对于V5这个顶点,它的完成时间有三个,分别是5+3=8,4+2=6和13+0=13。这里我们就要选一个最大的填进去,因为V5的“出度边事件”要进行,也就是活动a7和a8要开始的话,必须等齐a4,a5和a6三个活动结束后才能开始,所以在a4、a5和a6中选一个完成时间最大的,就能确保三个活动都能完成。

    到这里我们就知道程序大概要怎么写了:

    首先我们需要一个Earliest[ ]数组来存放每一个顶点的最早完成时间,Earliest[ 1 ]=0代表的就是开始结点V1的最早完成时间是0,对于图中每一个顶点对<i, j>,Earliest[ j ]的值也就是j结点的最早完成时间就等于Earliest[ i ]+C<i, j>(也就是前一个结点i的最早完成时间加上i和j之间的有向边的权值),当结点j的入度边不止一条的时候,Earliest[ j ]存放的就是所有入度边中最大的值。

    按照这个思路,我们可以把图里接下来的顶点的完成时间都填好:

    到最后V10结束结点等于29,也就是说整个图的所有活动的最短完成时间是29天。

    最后到来看看这个图中活动的机动时间,什么是机动时间呢,就是指图中这些活动中,有哪些活动是一直进行下去的,没有休息时间的。例如活动a10需要3天完成,而获得a11需要2天,则a11有1天的休息时间等待a10完成,a11的这一天休息时间就是所谓的“机动时间”。

    我们用e(i)来表示活动ai的最早完成时间,l(i)表示ai的最迟开始时间,机动时间要怎么算呢?看图来说,我们从结束结点开始倒推,在保证整个工期都不推迟的情况下,也就是第29天开始,反推回去,看结点V9,活动a12需要5天,就是说在保证整个工期能在29天完成的情况下,V9的最晚开始时间(也就是最迟完成时间)是29-5=24,就是说活动a12最迟必须在第24天就要开始工作了。V7结点和V8结点同理,V7结点最迟必须在第24-3=21天就开始工作,V8结点最迟必须在第24-2=22天开始就工作。

    接着看V5结点,从V8倒推到V5,就是22-7=15,a8活动最迟第15天就要开始工作。而从V7倒推到V5的话,21-8=13,a8活动最迟第13天就要开始工作,这里出现两个不同的值,怎么选?答案是选最小值13,因为如果选择第15天开工,那么对于活动a7来说,就延迟了两天开工了,这样就不能保证后面能在29天内完成整个工程,所以遇到两种不同的最晚开始时间时,我们要选最小的,这样才能保证整个工期不被延误。

    同样的,看V6结点,从V8结点倒推到V6结点,22-5=17天,也就是活动a9的最迟开始时间可以是在第17天时才开工?答案是不行的,因为V6结点和V5结点有个虚线连着呢,V6结点,也就是活动a9的最迟开始时间同样是13天。

    从这里就可以看出我们的求机动时间的倒推时的推断是,需要一个Latest[ ]数组存放每一个结点的最迟开始时间,一开始初始化结束结点的Latest[ 10 ]=Earliest[ 1 ],也就是29。然后倒推时,Latest[ i ]就等于Last[ j ]-C<i, j>.。如果某个结点有多个出度边,那么就选择最小值赋给Last[ i ]就可以了。

    按照这个推断,就可以把剩下的顶点的最晚开始时间都算出来:

    V1顶点有三种选择,V2到V1等于5,V3到V1等于7,V4到V1等于0,因为我们要选择最小值,所以V1填上0。

    最后来看看每个结点的机动时间,我们从头开始看,活动a1需要工作5天才完成,到达V2结点中,最迟开始时间是10,也就是说活动a4最迟在第10天开始工作都不会耽误整个工期,而a1从第0天开始只需工作5天就能完成,所以活动a1的机动时间就是10-0-5=5,五天。活动a2最迟在第11天开始工作就可以了,而活动a2只需要4天就可以完成,所以a2的机动时间是11-0-4=7,七天。活动a3等于6-0-6=0,所以活动a3机动时间等于0,也就是说活动a3完成后就要开始下一个活动了,中间没有“休息时间”。

    同理可看出,a4的机动时间是13-5-3=5。a5的机动时间是13-4-2=9。a6是13-6-7=0。这样我们就可以把所有的机动时间都算出来:

    我们假设用e(i)表示活动ai的最早开始时间,用l(i)表示活动的最迟开始时间,那么两者之差l(i)-e(i)表示活动ai的机动时间,把e(i)=l(i)的活动我们称为“关键活动”。关键路径上所有的活动都是关键活动。回到关键路径的问题,关键路径有可能不止一条。所以找出关键路径即找出路径上所有活动都是关键活动的路径即可。

    /*拓扑排序*/
    bool TopSort(ListGraphNode MyGraph, Vertex TopOrder[]) 
    {
    	/*TopOrder[]数组用来顺序存储排序后的顶点的下标*/
    	/*在拓扑排序完成后直接顺序输出TopOrder[]里的元*/
    	/*素就能得到拓扑排序序列*/ 
    	int i;
    	int Indegree[MaxVertex], cnt;/*Indegree数组是图中顶点的入度,cnt是计数器*/
    	Vertex V;/*扫描V顶点的邻接点*/
    	PtrlPointNode W; /*邻接表方式表示图*/
    	Queue PtrQ=Start();
    	for (i=0; i<MaxVertex; i++) {
    		PtrQ->Data[i]=-1;
    	}
    	
    	/*初始化入度数组*/
    	for (V=0; V<MyGraph->numv; V++) {
    		Indegree[V]=0;
    	}
    	
    	/*遍历图,得到图中入各顶点的入度情况并存入Indegree数组中*/
    	for (V=0; V<MyGraph->numv; V++) {
    		for (W=MyGraph->PL[V].HeadEdge; W; W=W->Next) {
    			Indegree[W->Tail]++;
    		}
    	}
    	
    	/*将所有入度为0的顶点入列*/
    	for (V=0; V<MyGraph->numv; V++) {
    		if (Indegree[V]==0) {
    			Push(PtrQ, V);
    		}
    	}
    	
    	/*开始拓扑排序*/
    	cnt=0; /*初始化计数器为0*/
    	while (PtrQ->End!=PtrQ->Head) {
    		V=Delete(PtrQ);/*出列一个入度为0的顶点*/
    		TopOrder[cnt++]=V;/*拓扑排序数组里记录该出列顶点的下标*/
    		/*遍历对于V的每个邻接点W->PL.HeadEdge.index*/ 
    		for (W=MyGraph->PL[V].HeadEdge; W; W=W->Next) {
    			/*若删除V能使该顶点的入度为0*/
    			if (--Indegree[W->Tail]==0) {
    				/*把该顶点入列*/
    				Push(PtrQ, W->Tail);
    			}
    			/*同时更新Earliest数组的值*/
    			if ((Earliest[V]+W->Weight)>Earliest[W->Head]) {
    				Earliest[W->Tail]=Earliest[V]+W->Weight;
    			} 
    		}
    	}
    	/*最后判断*/
    	if (cnt!=MyGraph->numv) {
    		return false;/*说明该图里有回路,返回false*/
    	} else {
    		return true;
    	}
    }

    在拓扑排序过程中,我们就同时更新Earliest数组,把每一个顶点的最早完成时间填入到数组中。

    /*关键路径*/
    bool CriticalPath(ListGraphNode MyGraph, int TopOrder[])
    {
    	int k, ee, el;
    	PtrlPointNode W;
    	Queue List=Start();
    	/*得到后面逆序用*/
    
    	for (k=0; k<MyGraph->numv ; k++) {
    		Push(List, TopOrder[k]); 
    	} 
    
    	/*初始化Lastest数组*/ 
    	for (k=0; k<MyGraph->numv; k++) {
    		Lastest[k]=Earliest[MyGraph->numv-1];
    	}
    	
    	/*开始关键路径*/
    	while (List->End!=List->Head) {
    		k=Delete(List);/*出列一个入度为0的顶点*/
    		/*遍历对于V的每个邻接点W->PL.HeadEdge.index*/ 
    		for (W=MyGraph->PL[k].HeadEdge; W; W=W->Next) {
    		if (Lastest[k]>(Lastest[W->Tail]-W->Weight)) {
    			Lastest[k]=Lastest[W->Tail]-W->Weight;
    		}	
    	}
    	
    	//printf("关键路径为:"); 
    	for (k=0; k<MyGraph->numv; k++) {
    		W=MyGraph->PL[k].HeadEdge;
    		while (W) {
    			ee=Earliest[k];
    			el=Lastest[W->Tail]-W->Weight;
    			if (ee==el) {
    				/*两值相等说明它们是关键活动*/
    				printf("v%d--v%d=%d", MyGraph->PL[k].HeadEdge->Tail, MyGraph->PL[W->Head].HeadEdge->Tail, W->Weight);
    				}
    				W=W->Next;
    			} 
    		}
    	}
    }

    在关键路径的计算过程中再逆序计算出最迟开始时间即可。

    完整代码在个人代码云:

    https://gitee.com/justinzeng/codes/9jbqdrhgn8xl31y6vsw2u75

    展开全文
  • AOE图和关键路径的求解

    千次阅读 2019-10-24 00:02:21
    AOE网和关键路径 本文算是相对知识密度较大的文章,建议看的时候仔细一点,并在迷惑的地方搜索其他文章。 文章目录AOE网和关键路径AOE网和AOV网一些概念关键路径关键路径相关量工程规划工程规划 AOE网和AOV网 ...

    AOE网和关键路径

    本文算是相对知识密度较大的文章,建议看的时候慢一点,并在迷惑的地方搜索其他文章。


    AOE网和AOV网

    一些概念

    拓扑结构:拓扑本是地理上的概念,指只考虑物体间的位置关系而不考虑它们的形状和大小。拓扑结构就是某些东西之间有位置关系。

    拓扑排序:给一个局部有序的拓扑结构排序。如:吃饭->睡觉,睡觉->打豆豆。在拓扑排序后则变成:吃饭->睡觉->打豆豆,这样的拓扑序列。

    Activity On Vertex:用顶点表示活动,用弧表示活动间的优先关系的有向图。

    活动:如吃饭睡觉打豆豆等,在企鹅的一天这个工程中都是活动。

    事件:类似于里程碑,标志着之前的某些活动都已经完成。如:顶点5标志活动a4,a5已完成,a7,a8可以开始了。(a7的先序活动为a4或a5)

    Activity On Edge:是一个带权的有向无环图,其中,顶点表示事件(Event),弧表示活动,权表示活动持续的时间。 入度为零的顶点成为源点,出度为零的顶点称为汇点
    AOE图示例
    AOE网可以求解:

    1. 完成整个工期的时间。
    2. 为缩短工期,应加快哪些活动。

    关系:AOV网常用来拓扑排序,AOE网用来规划工程计划。

    关键路径

    从源点到汇点具有最大长度的路径,关键路径上的所以活动都称作关键活动

    关键活动序列具有最长的总工期并决定了整个项目的最短完成时间,任何元素的延迟将直接影响项目的预期完成时间。

    关键路径相关量

    其中,v:vertex,e:early,l:late。

    以下可以在‘最’字前加上“可以”,便于理解。如:事件可以的最早发生事件。

    1. 事件的最早发生时间:ve[k]

    从源点开始到顶点Vk的最大路径长度(即权值的和)。

    这个长度决定了从顶点Vk发出的活动能够开工的最早时间。

    如:顶点5标志着活动a4、a5已完成,则以a4、a5为前序活动的a7、a8则可以开始进行。

    求解:

    ve[0] = 0;

    ve[k] = max{ve[j] + len<Vj, Vk>}

    即:从上个顶点Vj开始,ve[k]加上从该顶点到Vk顶点路径的最大值。

    1. 事件的最迟发生时间:vl[k]

    指在不推迟整个工期的前提下,事件Vk允许的最晚发生事件。

    vl[n] = ve[n]

    vl[k] = min{vl[j] - len<Vk, Vj>}

    即:从它的下一个顶点Vj开始,vl[j]减去该顶点到Vk顶点路径的最小值。

    注:上述两个相关量求解时总是为最大或最小值,是因为某个顶点的前一个顶点或后一个顶点可能有多个。我们所说的“Vk的前一个顶点”指的是与Vk有弧,且弧头指向Vk的顶点。

    1. 活动的最早开始时间:e[i]

    字面意思。

    e[i] = ve[k]

    即:e[i]等于该弧的弧尾所在顶点的ve[k]的值。

    1. 活动的最迟开始时间:l[i]

    l[i] = vl[j] - len<Vk, Vj>

    即:该弧的弧头所在顶点对应的vl[k]减去该弧的权值。

    然后就可计算各个活动的时间余量(l[k] - e[k] ),时间余量为0者为关键活动。

    工程规划

    在求出关键路径和各个活动的时间余量后,便可做出规划:

    若要保证工程完成工期较短,则关键活动必须要马不停蹄的完成。

    而时间余量不为零的那些活动,则可以拖延相应的时间。

    关键活动。

    工程规划

    在求出关键路径和各个活动的时间余量后,便可做出规划:

    若要保证工程完成工期较短,则关键活动必须要马不停蹄的完成。

    而时间余量不为零的那些活动,则可以拖延相应的时间。

    也可通过上面求得的关键路径相关量,计算安排每个活动开始的时间范围,和整个工程的最短工期。

    展开全文
  • 最全详解关键路径

    万次阅读 多人点赞 2019-10-24 13:01:38
    01什么关键路径法CPM? 关键路径法用于在进度模型中估算项目最短工期,确定逻辑网络路径的进度灵活性大小。这种进度网络分析技术在不考虑任何资源限制的情况下,沿进度网络路径使用顺推与逆推法,计算出所有活动的...

    关键路径法是软考的知识点,我分析了常见的模棱两可的知识点,并进行了图解说明,现在分享给正在准备参加软考试的广大考友。

    01什么是关键路径法CPM?

    关键路径法用于在进度模型中估算项目最短工期,确定逻辑网络路径的进度灵活性大小。这种进度网络分析技术在不考虑任何资源限制的情况下,沿进度网络路径使用顺推与逆推法,计算出所有活动的最早开始ES、最早结束EF、最晚开始LS和最晚完成LF日期。

    由此得到的最早和最晚的开始和结束日期并不一定就是项目进度计划,而只是把既定的参数(活动持续时间、逻辑关系、提前量、滞后量和其他已知的制约因素)输入进度模型后所得到的一种结果,表明活动可以在该时段内实施。

    02什么是关键路径法

    关键路径是项目中时间最长的活动顺序,决定着可能的项目最短工期。

    计算关键路径的长度时,需要将路径上的所有活动的持续时间、提前量(负的)和滞后量(正的)加总在一起。

    最长路径的总浮动时间最少,通常为零;进度网络图可能有多条关键路径。

    长度仅次于关键路径的路径称为次关键路径,次关键路径也可能有多条。

    借助进度计划软件来规划时,为了达成相关方的限制要求,可以自行定义用于确定关键路径的参数。

    03关键路径法的作用

    关键路径法用来计算进度模型中的关键路径、总浮动时间和自由浮动时间,或逻辑网络路径的进度灵活性大小。

    04最早时间和最晚时间

    1. 最早开始结束时间

    ES:最早开始时间(Earliest Start),是指某项活动能够开始的最早时间,只决定于项目计划,只要计划的条件满足了就可以开始的时间。

    EF:最早结束时间(Earliest Finish),是指某项活动能够完成的最早时间。其中EF = ES+DU, DU为活动持续时间,顺推法先知道开始时间。

    2. 最晚结束和开始时间

    LF:最迟结束时间(Latest Finish),是指为了使项目在要求完工时间内完成,某项活动必须完成的最迟时间。往往决定于相关方(客户或管理层)的限制。

    LS:最迟开始时间(Latest Start),是指为了使项目在要求完工时间内完成,某项活动必须开始的最迟时间。其中LS = LF -DU,DU为持续时间,逆推法先知道结束时间。

    3. 图形表示

    按照《PMBOK指南》的推荐,采用图6-24的方式来标注活动的ES、EF、DU、LF、LS以及活动名称(ID)

    6217760-7bde07988733e9b8.jpg

    @提示:在考试中未必需要把图6-24的格子画出来,只需要按照图中的方位进行标注就可以了,这样做的好处时在计算TF和FF时不容易出错。TF和FF的计算方法参见本节后续内容。

    4. 活动从第0天开始还是从第1天开始

    采用顺推法和逆推法进行进度网络路径计算时,需要关注活动是从第0天开始还是从第1天开始,不同的假设计算的结果是不一样的。首先需要明确以下几个概念。

    活动的持续时间DU是指活动的工作时间段,例如一个活动持续时间是24小时,是指3个工作日(每天8小时)。
    活动的开始时间是指活动开工日的上班开始时间;活动结束是指开工日的下班时间。也就是说假设一个活动的持续时间是2天,是指从第1天上班时间,到第2天下班时间的所有工作时间段。
    所谓活动从第0天还是第1天开始,意思是说要不要把活动开始的那一天计算在工作时间段内。因为现实中第0天是不存在的,所以活动开始的那一天就不需要计算在内;而活动从第1天开始,由于第1天是存在的,就需要计算在工作时间段内。这两种情况导致当前活动的EF或者LS,紧后活动的ES和LF在计算时要考虑是否减去或加上这1天的问题。

    无论是从第0天开始,还是第1天开始,都不会影响关键路径的和浮动时间的计算方法,但是考试中如果弄错了则会影响计算结果,考试中为了简化计算通常采用第0天开始,现实中为了与实际相符合通常采用第1天开始。下面就这两种方式举例说明。

    6217760-5b0e92074b7cdfa6.png

    图6-25

    第一种情况:活动从第0天开始。如图6-25

    计算公式如下:

    (1) 对于当前活动:

    顺推时 EF = ES + DU;
    逆推时 LS= LF – DU
    (2)对于紧后活动:

    顺推时ESi= EFi-1,;
    顺推时LFi-1 = LS i (例如逆推时活动C相当于活动D的紧后活动)
    其中自左向右,“i”代表当前活动,则“i-1”代表“i”的紧前活动。

    例如:对于活动A、B的最早时间:

    EFA= ESA+DU = 0+5 = 5,
    ESB = EFA= 5;
    对于活动D和C的最晚时间:

    LSD= LFD – DU = 30 -15 =15,
    LFC = LSD= 15;
    第二种情况:活动从第1天开始。如图6-26


    6217760-3718f49e35a81ffb.jpg

    图6-26

    对于当前活动

    顺推时 EF = (ES + DU)-1;
    逆推时 LS =(LF – DU)+1
    对于紧后活动

    顺推时ESi= EFi-1 +1;
    逆推时LFi-1 = LS i -1
    其中自左向右,“i”代表当前活动,则“i-1”代表“i”的紧前活动。例如:

    对于活动A、B的最早时间:

    EFA= ESA+DU-1 = 1+5-1 = 5,
    ESB = EFA+1= 5+1 = 6;
    对于活动D和C的最晚时间:

    LSD= LFD – DU+1 = 30 -15 +1 =16,
    LFC =LSD -1 = 15;
    @提示:从上两种计算方法来看,活动从第0天开始显然对人工计算来说更加直观简便,这种方法的缺点是与日历日期的对应关系是不一致的。活动从第1天开始计算的结果与日历日期是一致的,但是计算过程是不直观的。好在考试中一般不会涉及具体的日历日期,所以推荐使用活动从第0天开始的计算方法。

    05顺推法与逆推法

    自左向右计算最早时间称为顺推;自右向左计算最晚时间称为逆推。

    6217760-ffe33bf170c39ed5.png

    图6-27

    在顺推时会出现如图6-27(左)的情况,即当前活动有两个和两个以上的紧前活动,那么当前活动的ES的取值应该遵循顺推取最大的原则,

    即ES0 = MAX(EF1,EF2,……)

    在逆推时也会出现如图6-27(右)的情况,即当前活动有两个和两个以上的紧后活动,那么当前活动的ES的取值应该遵循逆推取最小的原则,

    即ES0 = MIN(EF1,EF2,……)。

    @提示:顺推法得到的最早工期代表项目期望的计划工期;逆推法时设定的最晚工期代表相关方的期望工期。

    1. 总浮动时间TF

    定义:在任一网络路径上,进度活动可以从最早开始日期推迟或拖延的时间,而不至于延误项目完成日期或违反进度制约因素,就是总浮动时间或进度灵活性。
    取值:在进行紧前关系绘图法排序的过程中,取决于所用的制约因素,关键路径的总浮动时间可能是正值、零或负值。
    总浮动时间为正值,是由于逆推计算所使用的进度制约因素要晚于顺推计算所得出的最早完成日期,即给定的工期比计划的工期要长。
    总浮动时间为负值,是由于持续时间和逻辑关系违反了对最晚日期的制约因素,即给定的工期要比计划的工期要短。
    计算方法:TF = LS – ES = LF – EF,即按照图6-28箭头所示的方向求值。


    6217760-1431adc16e6dd5f6.png

    图6-28

    2. 负值浮动时间分析

    关键路径出现负的浮动时间意味着,如果不采取措施项目将延期。
    负值浮动时间分析是一种有助于找到推动延迟的进度回到正轨的方法的技术,从而找到保证工期的途径。
    为了使网络路径的总浮动时间为零或正值,可能需要调整活动持续时间(可增加资源或缩减范围时)、逻辑关系(针对选择性依赖关系时)、提前量和滞后量,或其他进度制约因素。

    3. 自由浮动时间FF

    自由浮动时间就是指在不延误任何紧后活动最早开始日期或不违反进度制约因素的前提下,某进度活动可以推迟的时间量。
    总浮动时间可能等于大于自由浮动时间,TF≥FF。
    计算方法,如图6-29所示

    6217760-429e250aa5b8d772.png

    图6-29

    对于图6-29(左)的情况:活动0的FF0 = ES1 – EF0
    对于图6-29(右)的情况:活动0的FF0 = MIN{ (ES1 – EF0),(ES2 – EF0) ,……}
    @提示:由于自由浮动时间的计算涉及前后活动之间的参数不容易记忆,只要记住图6-29所示的计算方式就不容易搞错了。

    4. 项目浮动

    一个项目可以延误但不影响外界(如客户或发起人)限制的完工日期的时间。例如客户要求11.11号完工,项目团队的计划是在11.1完工,那么二者之间就有10天的浮动时间;如果按照客户要求日期完工,则项目浮动会反映在总浮动时间上。

    关键路径常见考点小结,请参考表6-7。

    6217760-3ac513f5e634d2a1.jpg

    表6-7

    06关键路径法完整的计算示例

    请计算如表6-8所列活动的关键路径,并完成顺推计算最早时间和逆推计算最晚时间,计算所有活动的TF和“活动C”的自由浮动时间FF。

    6217760-346491c569f974be.png

    表6-8

    第一步,画出网络图。如图6-30(1)


    6217760-93dec3e1e2fc86f2.png

    图6-30(1)

    第二步:计算关键路径。列出所有可能的路径,比较其长度

    路径A-B-F长度为2+2+2 = 6
    路径A-C-F长度为2+3+2 = 7
    路径A-D-E-F长度为2+4+2+2 = 9
    故关键路径为A-D-E-F,长度为9

    第三步:顺推。计算最早时间,按照从第0天开始,如图6-30(2)

    6217760-928f7716c89da88a.png

    图6-30(2)

    第四步:逆推。计算最晚时间,如图6-30(3)


    6217760-b32d52ec95ba52ce.jpg

    图6-30(3)

    第五步,计算所有活动的TF和活动C的FF。如图6-30(4)所示。活动C的FF为:

    FFc = ESF-EFc=8 – 5 = 3
    或者采取另一种方法:
    FFc = 关键路径耗时 – 包含活动C的路径耗时 = 10 -- 7 = 3


    6217760-4ad75a609ffda306.jpg

    ===========我是华丽的分割线===========


    更多知识:
    点击关注专题:嵌入式Linux&ARM

    或浏览器打开:https://www.jianshu.com/c/42d33cadb1c1

    或扫描二维码:

    6217760-fb25d7cd85861e9a.jpg
    扫我

    展开全文
  • 1.关键路径(Critical Path)从起点到终点的花费时间最长的一条为关键路径。 注意:在关键路径上的任务的松弛时间为0 ●最早开始时间:在关键路径上,从开始到该任务的最早执行的时间 ●最晚开始时间:关键...
  • C语言AOE网、关键路径

    千次阅读 2019-05-01 17:21:36
    2.关键路径 2.1关键路径的概念 2.2关键路径的几点说明 2.3关键路径的求解步骤 2.4关键路径求解示例 1.AOE网(Activity On Edge Network) 1.1AOE网的概念 若在带权的有向图中,用有向边表示活动(子工程),...
  • 项目关键路径,指重要功能都已经完成,而且可以... 最长路径意思很明显,就是耗时最长的。项目后期维护,其实工作量非常大,有时会拖很久。  一般来说,最长路径包含关键路径。有时也不一定,可能会包含部分。 ...
  • 提出问题:为什么会出现关键路径这个东西? 答:加入你是一个包工头,你承包了一个工程,“一年内帮政府建立一座现代化的养老院” ,这下问题就来了,怎么建呢?总不能从天上掉下来一个养老院把?我们需要计划,...
  • 数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么? 数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么?我做了几道...
  • 软考--关键路径

    万次阅读 2018-06-20 16:48:02
    一、什么关键路径关键路径法用于在进度模型中估算项目最短工期,确定逻辑网络路径的进度灵活性大小。这种进度网络分析技术在不考虑任何资源限制的情况下,沿进度网络路径使用顺推与逆推法,计算出所有活动的最早...
  • 有向无环图之关键路径

    千次阅读 2018-01-28 21:48:52
    **有向无环图之关键路径** 1 AOE-网:边表示活动的网。AOE-网是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间。 2 通常AOE-网可用来估算工程的完成时间。 例图: 该图...
  • 关键路径计算、总时差、自由时差

    万次阅读 2018-04-18 18:50:56
    1. 关键路径2. 总时差与自由时差的区别 总时差是指在不延误项目完成日期或违反进度因素的前提下,某活动可以推迟的时间。 总时差=LS-ES=LF-EF 自由时差是指在不影响紧后活动最早开始的情况下,当前活动可以推迟的...
  • 软考之 关键路径

    2014-05-21 17:20:05
    [url]http://bbs.51cto.com/thread-626242-1.html[/url]
  • 关键路径的概念和算法

    千次阅读 2018-10-02 17:22:43
    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网。AOE网中没有入边的顶点称为始点(或源点),...关键路径...
  • 【算法】基于AOE网的关键路径算法

    千次阅读 2017-09-28 15:58:21
    什么关键路径关键路径什么用呢?我又去抱了抱度娘的大腿,发现这个是杜邦公司发明的算法,是用来算工期的。在工程上,我们都很讨厌工程的延期,同时一个工程由分为很多的节点,我们不知道哪些节点决定着这个...
  • AOE网-关键路径

    千次阅读 2017-03-27 19:27:21
    关键路径:我们把路径上各个活动持续时间之和称为路径长度,从源点到终点最大的长度为关键路径,在关键路径上的活动叫关键活动。 那么,显然对上图AOE网而言,所谓关键路径: 开始-->发动机完成-->部件集中到位...
  • 关键路径上的关键活动的最早开始的时间和最晚开始的时间应该是相同的(etv==ltv),否则说明还有其他工程会影响工期,这条路径就不是关键路径了。 ete和lte ete:活动的最早开工时间(相对于边来说的) lte:活动...
  • 图的拓补排序与关键路径

    千次阅读 2014-09-04 21:10:22
    将各个活动持续时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动称为关键活动。并不是加快任何一个关键活动都可以缩短整个工程完成的时间,只有加快那些包括在所有的关键路径上...
  • 关键路径:最早开始时间 计算方式:每个节点找它到下个节点的最大路径 具有最大路径长度的路径为关键路径。因为你得保证每个人都到场才能去看电影嘛,那你肯定得等到最后一个人到了才能走。图中就是v...
  • 文章目录一、画任务框 task box二、过程1. Draw Box2. Enter Durations3. ES & EF4.... LF5. Float6.... 一、画任务框 task box 任务框通常用六个框画。...Early Finish (EF): 最早结束,意思是直到第几天结束,包含这
  • AOE网络的关键活动计算,进而得到关键路径
  • 关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(最早最晚时间、时差)等。...
  • 软件开发的过程中关键路径问题

    千次阅读 2005-01-08 13:07:00
    为了提高整个项目的进度通常方式会采用多组人并行实施的策略,但由于这些步骤之间在时间上存在先后制约关系(例如:建筑施工前需要先购买好水泥、钢材、砖瓦等),我们需要先建立好关键路径,然后按照先后顺序进行...
  • 文章目录有向无环图拓扑排序AOV-网AOE-网关键路径的概念事件的最早/晚开始时间事件和活动的区分活动的最早/晚开始时间 有向无环图 拓扑排序 AOV-网 由于有向无环图可以用一种自然的方式对优先关系或依赖关系进行...
  • 关键路径以点为事件,线为过程,需要将所有工程完成时的路径,所以选最长路径为关键路径才能 确保所有工程都完成 。   顶点(事件)的最早发生时间ve(j):从原点到顶点j的最长路径长度。 顶点(事件)的...
  • 关键路径 拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。比如造一辆汽车,我们需要先造各种各样零件、部件,最终再组装成车,假如,造一个轮子需要0.5天时间...
  • 松弛时间:关键路径时间-当前路径时间,即可以延迟该任务的开始时间而不影响关键路径准时走完花费的时间。   转载自: https://blog.csdn.net/u010011371/article/details/46272393  
  • 进程是什么意思?

    千次阅读 2013-01-17 14:22:20
     危害较大的可执行病毒同样以“进程”形式出现在系统内部(一些病毒可能并不被进程列表显示,如“宏病毒”),那么及时查看并准确杀掉非法进程对于手工杀毒有起着关键性的作用。 进程是程序在计算机上的一次...
  • 什么是相对路径?

    2010-06-30 14:09:00
    对于一个开发人员,理解相对路径的概念和用法非常重要,在实际项目中,常常有人因为对相对路径含义理解不清,导致页面不正常。  下面是有三个文件夹和三个文件,结构层次如下,x.bat是个批处理文件。...
  • Proteus 8 Professional发生关键仿真错误(疑似中文路径导致) 在软件仿真时出现错误 显示好多红色代码 疑似之前把电脑名命名为中文了 所以缓存路径也是中文 导致Proteus 8 Professional发生关键仿真错误 在以后...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,086
精华内容 32,434
关键字:

关键路径什么意思