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

    万次阅读 多人点赞 2018-03-26 13:15:05
    关键路径概念: 在无回路的有向网络中,假设只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点),则从源点到汇点之间的最长的路径称为关键路径。AOE网: 无回路有向网络可以用来表示一个包含多项活动的...

    关键路径概念:

          在无回路的有向网络中,假设只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点),则从源点到汇点之间的最长的路径称为关键路径。

    AOE网:

        无回路有向网络可以用来表示一个包含多项活动的工程计划:有向边表示一项活动,边上的权表示完成这项活动需要的时间;顶点表示"所有入边代表的活动已完成,出边代表的活动可以开始"这样一种状态或者事件,其中源点表示工程的开始,汇点表示工程的结束;源点到汇点的某一关键路径上边的权值之和表示完成整个工程的计划时间。

        通过求有向网络的关键路径,可以算出整个工程从开始到结束至少需要多少时间;可以知道哪些活动是影响工程进度的关键活动。

        这种用边表示活动且只有一个源点和一个汇点的无回路有向网络称为边表示活动的网,简称AOE网。

    两个与顶点有关的量:

        在下面的讨论中,假定AOE网有n个顶点,源点是V1,汇点是Vn。

        -最早发生时间:

            事件Vi的可能的最早发生时间earliest(i),它等于从源点V1到顶点Vi的最长路径长度。

        -最迟发生时间

            在保证汇点事件Vn在earliest(n)时刻发生的前提下,事件Vi允许的最迟发生时间latest(i),它等于earliest(i)减去从顶点Vi到汇点Vn的最长路径长度。

    earliest数组的计算方法:

        -令earliest(1)=0;

        -按顶点的拓扑顺序计算earliest(j):

            earliest(j)=max{(earliest(i)+Wij)|Vi邻接到Vj}

        -例如

            earliest(a)=max{earliest(b)+u,earliest(c)+v}

    latest数组的计算方法:

        -令latest(n)=earliest(n);

        -按顶点的逆拓扑顺序计算latest(i):

            latest(i)=min{(latest(j)-Wij)|Vj邻接于Vi}

        -例如:

            latest(a)=min{latest(d)-x,latest(e)-y}

    两个与边有关的量:

        对于活动ak=<Vi,Vj>,可以定义它的可能的最早开始时间和允许的最迟开始时间。

        -最早开始时间:活动ak的可能的最早开始时间等于事件Vi的可能的最早发生时间earliest(i)

        -最迟开始时间:活动ak的允许的最迟开始时间等于事件Vj的允许的最迟发生时间latest(j)减去完成该活动的计划时间Wij。

       

    (最早发生,从前往后算;最迟发生,从后往前算。)


     

    求关键路径的算法:

        1、计算每个事件可能的最早发生时间

    //计算每个事件可能的最早发生时间
    template<class T>
    void ExtLGraph<T>:: Earliest(int* earliest, int* order)
    {
        for(int i=0;i<n;i++)  earliest[i]=0;
         for(i=0;i<n;i++){
    	    int k=order[i];
    	    for (ENode<T>* p=a[k]; p; p=p->nextArc){
                int  j=p->adjVex;
    	    if (earliest[j]<earliest[k]+p->w) 
    	  	  earliest[j]=earliest[k]+p->w;
            }
      }
     }

        2、计算每个事件允许的最迟发生时间

    //计算每个事件允许的最迟发生时间
    template<class T>
    void ExtLGraph<T >:: Latest(int* latest,int* order,int longest)
    {
    	for (int i=0;i<n;i++) latest[i]=longest;
        for (i=n-2;i>-1;i--){
            int j=order[i]; 
               for (ENode<T>* p=a[j];p;p=p->nextArc) {
                   int  k=p->adjVex;
       if (latest[j]>latest[k]-p->w)
    		  latest[j]=latest[k]-p->w;
    }
         }
     }
    

        3、输出关键活动

    最早发生时间和最迟发生时间相等的事件,一般就是关键活动。

    从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动称为关键活动。



    展开全文
  • 在实施GJB5000A二级“项目策划”过程域时,制定进度计划要求给出任务间的依赖关系,标准推荐的一个方法就是关键路径法。PS:标准要求的是标识任务间的依赖关系,不是要求必须给出关键路径,在GJB5000A评价时有些评价...

    在实施GJB5000A二级“项目策划”过程域时,制定进度计划要求给出任务间的依赖关系,标准推荐的一个方法就是关键路径法。

    PS:标准要求的是标识任务间的依赖关系,不是要求必须给出关键路径,在GJB5000A评价时有些评价员却以没有关键路径给被评项目的这条实践打L,是不合适的。

    但是,标准中对于关键路径法却没有给出详细的解释。这个方法是项目管理的专业知识,学习PMP的同学应该都了解这个方法。

    下面对关键路径法做下简单介绍。

    关键路径法(Critical Path Method,CPM)是借助网络图和估计的各项活动(或任务)所需时间,由此统筹计算出整个项目的工期和关键路径。这里的关键路径就是工期最长的那条路径。

    关键路径法把项目活动(或任务)间的关系定义为以下四种依赖关系:

    • 结束对起始(FS)。前一活动必须在后一活动开始前结束。

    • 结束对结束(FF)。前一活动必须在后一活动结束前结束。

    • 起始对起始(SS)。前一活动必须在后一活动开始前开始。

    • 起始对结束(SF)。前一活动必须在后一活动结束前开始。

    同时每个活动又有四个和时间相关的参数:

    • 最早开始时间(ES):某项活动能够开始的最早时间。

    • 最早结束时间(EF):某项活动能够完成的最早时间。

    • 最晚结束时间(LF):为了使项目按时完成,某项工作必须完成的最迟时间。

    • 最晚开始时间(LS):为了使项目按时完成,某项工作必须开始的最迟时间。

    参见下图。

    2e434469-151f-eb11-8da9-e4434bdf6706.png

    其中:EF=ES+工期估计,LS=LF-工期估计

    关键路径法要遵循两个规则:

    • 规则1:某项活动的最早开始时间必须相同或晚于直接指向这项活动的最早结束时间。

    • 规则2:某项活动的最迟结束时间必须相同或早于该活动直接指向的所有活动最迟开始时间的最早时间。

    根据以上规则,通过正向计算(从第一个活动到最后一个活动)就可以推算出项目的最早完工时间,然后再通过反向计算(从最后一个活动到第一个活动)推算出最晚完成时间,而最早完成时间和最晚完成时间相等的活动就成为关键活动。把这些关键活动串联起来的路径就是关键路径。关键路径的工期实际上就是项目的工期。

    如果实施GJB5000A的项目负责人要使用关键路径法来标识任务依赖关系,可以找专业的项目管理书籍学习下关键路径法。

    这正是:

    关键路径好方法,任务关系可用它

    时间关系估算好,任务排定就拿下

    参考书目:软件工程与UML案例解析(第三版),作者:何晓蓉,出版社:中国铁道出版社


    作者简介:王小双,长期从事GJB5000推广、实施、评价、改进的工作,创建《软件工程之思》微信公众号,一直在《软件工程之思》分享GJB5000、CMMI、软件工程的知识和感悟。现致力于GJB5000咨询以及软件过程改进、软件工程能力提升的研究工作。
    展开全文
  • 关键路径法详解

    万次阅读 2010-06-08 19:05:00
    关键路径法)是项目管理中最基本也是非常关键的一个概念,它上连着WBS(工作分解结构),下连着执行进度控制与监督。关键路径是项目计划中最长的路线。 它决定了项目的总实耗时间。项目经理必须把注意力集中于那些...
    摘要

    CPM(CriticalPathMethod 关键路径法)是项目管理中最基本也是非常关键的一个概念,它上连着WBS(工作分解结构),下连着执行进度控制与监督。关键路径是项目计划中最长的路线。 它决定了项目的总实耗时间。项目经理必须把注意力集中于那些优先等级最高的任务,确保它们准时完成,关键路径上的任何活动的推迟将使整个项目推迟。向关键 路径要时间,向非关键路径要资源。所以在进行项目操作的时候确定关键路径并进行有效的管理是至关重要的。

    关键路径法

    关键路径法:定义

    关键路径法(Critical Path Method,CPM),又称关键线路法。一种计划 管理方法。它是通过分析 项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络 分析。它用网络图表示各项工作之间的相互关系,找出控制工期 的关键路线,在一定工期、成本、资源条件下获得最佳的计划安排,以达到缩短工期、提高工效、降低成本 的目的。CPM中工序时间是确定的,这种方法多用于建筑施工和大修工程的计划安排。它适用于有很多作业而且必须按时完成的项目。关键路线法是一个动态系统 ,它会随着项目的进展不断更新,该方法采用单一时间估计法,其中时间被视为一定的或确定的。

    关键路径法


    关键路径法 :起源

    关键路线法是一种网络图 方法,最早出现于20世纪50年代,由雷明顿-兰德公司(Remington- Rand)的JE克里(JE Kelly)和杜邦公司的MR沃尔克(MR Walker)在1957年提出的,用于对化工 工厂的维护 项目进行日程安排。这种方法产生的背景是,在当时出现了许多庞大而复杂的科研 和工程项目,这些项目常常需要运用大量的人力、物力和财力,因此如何合理而有效地对这些项目进行组织,在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题,这样CPM就应运而生了。

    关键路径

     

    关键路径法:原理与网络步骤

    关键路径法(CPM)是一种网络分析 技术,是确定网络图当中每一条路线从起始到结束,找出工期最长的线路,也就是说整个项目工期的决定是由最长的线路来决定的。

    关键路径法是时间管理中很实用的一种方法,其工作原理是:为每个最小任务单位计算工期、定义最早开始和结束日期、最迟开始和结束日期、按照活动的关系形成顺序的网络逻辑 图,找出必须的最长的路径,即为关键路径。

    时间 压缩 是指针对关键路径进行 优化 ,结合成本因素、资源因素、工作时间因素、活动的可行进度因素对整个计划进行调整,直到关键路径所用的时间不能再压缩为止,得到最佳时间进度计划
    简单网络图

    (1)画出网络图,以节点标明事件,由箭头代表作业。这样可以对整个项目有一个整体概观。习惯上项目开始于左方终止于右方。

    关键路径法 关键路径法

    (2)在箭头上标出每项作业的持续时间(T)

    (3)从左面开始,计算每项作业的最早结束时间(EF)。该时间等于最早可能的开始时间(ES)加上该作业的持续时间。

    (4)当所有的计算都完成时,最后算出的时间就是完成整个项目所需要的时间。

    (5)从右边开始,根据整个项目的持续时间决定每项作业的最迟结束时间(LF)。

    (6)最迟结束时间减去作业 的持续时间得到最迟开始时间(LS)。

    (7)每项作业的最迟结束时间与最早结束时间,或者最迟开始时间与最早开始时间的差额 就是该作业的时差。

    (8)如果某作业的时差为零,那么该作业就在关键路线上。

    (9)项目的关联路线就是所有作业的时差为零的路线。

     

    关键路径法-组成与应用

           

     

    关键路径法 关键路径法
    对于一个项目而言,只有项目网络中最长的或耗时最多的活动完成之后,项目才能结束,这条最长的活动路线就叫关键路径(Critical Path),组成 关键路径 的活动称为关键活动。其通常做法是:

    (1)将项目中的各项活动视为有一个时间属性 的结点,从项目起点到终点进行排列;

    (2)用有方向的线段标出各结点的紧前活动和紧后活动的关系,使之成为一个有方向的网络图;

    (3)用正推法和逆推法计算出各个活动的最早开始时间,最晚开始时间,最早完工时间和最迟完工时间,并计算出各个活动的时差;

    (4)找出所有时差为零的活动所组成的路线,即为关键路径;

    (5)识别出准关键路径,为网络优化 提供约束条件;

    关键路径法-特点

           

     

    关键路径法 关键路径法
    (1)关键路径上的活动持续时间决定了项目的工期,关键路径上所有活动的持续时间总和就是 项目 的工期。

    (2)关键路径上的任何一个活动都是关键活动,其中任何一个活动的延迟都会导致整个项目完工时间的延迟。

    (3)关键路径上的耗时是可以完工的最短时间量,若缩短关键路径的总耗时,会缩短项目工期;反之,则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间,也不至于影响工程的完工时间。

    (4)关键路径上活动是总时差最小的活动,改变其中某个活动的耗时,可能使关键路径发生变化。

    (5)可以存在多条关键路径 ,它们各自的时间总量肯定相等,即可完工的总工期。

    关键路径是相对的,也可以是变化的。在采取一定的技术组织 措施之后,关键路径有可能变为非关键路径,而非关键路径也有可能变为关键路径。

    关键路径法-优化与制定

           

     

    关键路径法 关键路径法
    项目管理 中, 编制 网络计划的基本思想就是在一个庞大的网络图中找出关键路径,并对各关键活动,优先安排资源,挖掘潜力,采取相应措施,尽量压缩需要的时间。而对非关键路径的各个活动,只要在不影响 工程 完工时间的条件下,抽出适当的人力、物力和财力等资源,用在关键路径上,以达到缩短工程工期,合理利用资源等目的。在执行计划过程中,可以明确工作重点,对各个关键活动加以有效控制和 调度

    在这个优化思想指导下,我们可以根据项目计划的要求,综合地考虑进度、资源利用和降低费用等目标,对网络图进行优化,确定最优的计划方案。下面分别讨论在不同的目标约束下,优化方案策略的制定步骤。

    目标一 时间优化,即根据对计划进度的要求,缩短项目工程的完工时间。

    可供选择的方案:

    1. 采取先进技术的措施如引入新的生产机器等方式,缩短关键活动的作业时间;

    2. 利用快速跟进法,找出关键路径上的哪个活动可以并行;

    3. 采取组织措施 ,充分利用非关键活动的总时差,利用加班、延长工作时间、倒班制和增加其它资源等方式合理调配技术力量及人、财、物等资源,缩短关键活动的作业时间。

    目标二 :时间-资源优化,在考虑工程进度的同时,考虑尽量合理利用现有资源,并缩短工期。

    具体要求和做法是:

    1. 优先安排关键活动所需要的资源;

    2. 利用非关键活动的总时差,错开各活动的开始时间,拉平资源所需要的高峰,即人们常说的“削峰填谷”;

    3. 在确实受到资源限制,或者在考虑综合经济效益的条件下,也可以适当地推迟工程时间。

    目标三 :时间-费用优化。这个目标包括两个方面,一个是指在保证既定的工程完工时间的条件下,所需要的费用最少;或者是在限制费用的条件下,工程完工时间最短。

    一般来讲,工程费用可分为直接费用和间接费用两大类,其中直接费用包括直接生产的工人工资及附加费,设备折旧、能源、工具及材料消耗等直接与完成活动有关的费用。为缩短活动的作业时间,需要采取一定的技术组织措施,相应地需要增加一部分直接费用,如为了赶工增加设备 或者单位时间内增加能源消耗等。因此,在一定条件下和一定范围内,活动的作业时间越短,直接费用越多。间接费用通常包括管理人员的工资、办公费等,从成本会计上,我们把间接费用按照工程的施工 时间进行直接分摊。在一定的生产规模内,活动的作业时间越短,分摊的间接费用也越少。因此,我们有以下时间-费用函数: Y = f1(t) f2(t)

    Y:总费用
    f1(t):直接费用
    f2(t):间接费用

    该方程式表明,工程项目的不同完工时间所对应的活动总费用和工程项目所需要的总费用随着时间的变化而变化。假设当 t = T’ 时,Y’ = Min(Y) 即工程总费用达到最低点,我们将T’点称为最低成本日程(我们可以用一阶导数为零,二阶导数为正来求得T’点)。在制订网络计划时,无论是以降低费用为主 要目标,还是尽量缩短工程完工时间为主要目标,都要计算最低成本日程,从而拟定出时间-费用的优化方案

    关键路径法-优缺点

           

     CPM(关键路径法)主要是一种基于单点时间估计、有严格次序的一种网络图。它在项目管理应用中既有优点,又有其不足之处。

    优点 :它的出现为项目提供了重要的帮助,特别是为项目及其主要活动提供了图形化的显示,这些量化信息为识别潜在的项目延迟风险 提供极其重要的依据。

    缺点 :首先,现实生活中的项目网络往往包括上千项活动,在制定网络图时,极其容易遗漏;其次,各个工资之间的优先关系未必十分明确,难以做图;最后是各个活动时间经常需要利用概率 分 布来估计时间点,有可能发生的偏差;最后,确定关键路径目标其实质上为了确保项目按照这一特定的顺序严格执行,从而不至于使整个项目停顿、拖延,如果管理 团队对确实无法确定的工作,就应该在项目运作的计划中进行充分的分析和重新安排,此是网络计划显得无能为力。因此在项目中,CPM也需要其它工具和方法同 时辅助 使用。

    关键路径法-项目时间计划中最短路径法分析

           

    如果某一条线路消耗 时间比较短,在这个线路上它就具有一定的时间裕量。因此关键线路是进行项目时间管理时需要注重的工作。在分析关键线路的时候,可以采取两种分析方法:即单一时间估计 法(CPM)和三点时间估计法(PERT)。

    单一时间估计就是单一时间估计的关键路径法。

    特点:有一个确定的工作时间,根据确定的工作时间确定出每一项工作的具体时间参数和浮动时间。

    具体的步骤可以从项目计划开始,首先是确定工作,然后确定工作弹性并建立一些网络图。接下来是通过项目的时间参数结算来确定关键路径。

     

    关键路径法 某一咨询项目的单一时间估计表
    如右图表某一咨询项目的单一时间估计表。这个项目一共有7项工作。每项工作给出一个工作代号,即ABCDEFG。这个先后顺序通常用紧前工作来表示。如需求分析就是准备和提交 建议书 的紧前工作。如果项目工作之间存在多条路径,就会出现一个、两个或是多个牵制工作,我们用牵制工作的代号就可以反映项目之间的顺序。如果对每个工作所 花费 的时间进行 估算 ,基于这样一个表就能够计算每一条线路所需要的时间。

    以这个例子为例,可以得出两条路径,也就是从起始到结束有两条路径,分别计算出两条路径所花费的时间。有两种估算方法,顺推法:ESEF;逆推法:LSLF。

    顺推法:计算最早开始和结束时间。假设这个项目完成时间是15周。那么,每一个项目最早开始和结束时间是。

    逆推法:就是从项目的结束开始用倒推法,即假定最后一项工作要求是15周完成,用最迟的时间减去当前的工作时间,就可以计算出项目的最迟开始时间。依次进行,可以计算出每一项工作的最迟结束和最迟开始时间。如下:

    A(2):ES=0EF=2;LS=0LF=2
    B(1):ES=2EF=3;LS=2LF=3
    D(2):ES=4EF=6;LS=7LF=9
    E(5):ES=4EF=9;LS=4LF=9
    C(1):ES=3EF=4;LS=3LF=4
    F(5):ES=9EF=14;LS=9LF=14
    G(1):ES=14EF=15;LS=14LF=15

    如果一项工作的最早开始与最迟开始两个时间完全相同,意味着不存在任何自由浮动时间,它的时间是唯一确定的。如果一条线路上所有工作都不具有浮动时 间,这条线路就是关键路径,也就是说在关键路径上工作的浮动时间等于零。相应的可以结算出其它线路的所需时间,如上所示,D工作最早开始工作是第四周,最 迟开始时间是第七周,也就是说,这项工作开始可以在第四周和第七周之间有一个浮动范围,即(Slack=(7-4)=(9-6)=3Wks),这项工作就 属于非关键路径上的工作,它的重要性可以放在一个稍微次要的层次上,这是计算关键路径的一种方法。

    计算关键路径可以用正推法计算出项目的最早开始和最早结束时间,用逆推法计算项目的最迟开始和最迟结束时间,从而就可以确定每一项工作是否具有浮动 时间。如果浮动时间不为零,也就是说这项工作不是位于关键线路上,它是具有浮动时间的。这个浮动区间实际上又决定了每一项工作能够允许的活动时间范围。

    关键路径法-与计划评审方法的联系与区别

           

     

    关键路径法 关键路径法
    计划评审方法 (program evaluation and review technique, PERT)和关键路线法Critical Path Method,CPM)是网络分析的只要组成部分,它广泛地用于系统分析和项目管理,计划评审与关键路线方法是在20世纪50年代提出并发展起来的。 1956年, 美国 杜邦公司为了协调企业不同业务部门的系统规划,提出了关键路线法。1958年,美国海军 武装 部在研制“北极星” 导弹 计划时,由于导弹的研制系统过于庞大、复杂,为找到一种有效的管理方法,设计了计划评审方法。由于PERT与CPM既有着相同的目标应用,又有很多相同的 术语 ,这两种方法已合并为一种方法,在国外称为PERT/CPM,在国内称为 统筹方法 (scheduling method)。

    CPM与PERT的区别

    CPM和PERT都使用了网络,而且同时用到了关键路径,在制订计划时都明确地考虑了成本因素,但是有两点根本不同:

    (1)CPM是一个带有“确定性”的方法:每一项活动只用到一种时间估算。而不像PERT中的那样,是一种预先假设的随机偏差

    (2)CPM方法包括了一个数学 过程,以评估 项目工期和项目成本间的平衡。从一项工作向另一项工作重新调配资源的CPM分析的主要目的是为达到最低的成本,最大限度地缩短项目工期。

    关键路径法-与关键链法差异

           

     

    关键路径法 关键路径法
    1. 关键链法考虑了人的因素和 资源 约束,这是与网络计划里的关键路径法最大的差别。

    2. 关键路径法使用的数据是包含安全时间的保守工期;而关键链法使用的数据最可能工期,并把安全时间拿出来集中管理。

    3. 关键路径是一次就可以确定的;而关键链 是不能一次就确定,是一个循环往复、不断寻优的过程;

    4. 关键路径有严格的紧前紧后关系,而关键链没有,但有较复杂的逻辑关系

    5. 关键链计划是区间计划,比如人们经常说,本工程在明年10月份完工,所谓10月份,即是从10月1日到10月31日的一个区间;而关键路径是一个确定的时间点计划,如本工程在明年10月31日完工。区间计划比点计划更临近实际。

    展开全文
  • 软考--关键路径法

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

    一、什么是关键路径法

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

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

    二、关键路径分析

    关键路径分析也称为关键路径法(Critical Path Method),是一种用来预测总体项目历时的项目网络分析技术。所谓“关键路径”,是指当我们完成了项目进度计划后,在项目的网络图上,存在着若干条从项目启动到项目结束之间的路径,但是对其中一条(严格的来说,可能存在一条以上)路径上来说:

    l         其上所有活动的时间之和就是完成项目的最短历时;

    l         路径上任何活动的延误都会导致项目时间的延长;

    l         如果我们想缩短项目历时,就必须缩短这条路径上活动的历时;

    这条路径就是项目的关键路径。如下图:

    制定进度计划 <wbr>关键路径分析

    图 - 2.        关键路径

    怎样确定关键路径呢?它实际是项目网络图中(历时)最长的路径。下面我们来下一个定义,一个项目的关键路径:是指一系列决定项目最早完成时间的活动。在关键 路径上的活动都很“关键”,因为它们直接决定了项目的进度。每个活动都只有最少的浮动时间或时差。所谓浮动时间或时差是指一项活动在不耽误后续活动或项目 完成日期的条件下可以拖延的时间长度。

    现在所有的项目管理软件工具都将寻找一个项目的关键路径作为最基本的功能。它是运用某种运算法则来计算而得出项目关键路径信息的。该运算法则被称为正推法和 倒推法,这个法则输出的结果就是项目的关键路径,当然也包括项目的总历时和项目中每个活动关于进度的“关键”信息。虽然今天已经很少需要手工计算来得到项 目的关键路径了,但是仔细了解一下它的算法将会非常有助于更深刻地理解所得到各项信息的意义。下面我们就来看一下如何用正推法和倒推法来计算项目的关键路 径。

    正推法和倒推法主要是用来计算有关一个项目活动的:

    l         最早开始时间(Early Start,简称ES),在条件具备的情况下,该活动可以开始进行的最早可能;

    l         最早结束时间(Early Finish,简称EF), 在条件具备的情况下,该活动可以完成的最早可能;

    l         最晚开始时间(Late Start,简称LS),在不拖延项目进度的情况下,该活动可以开始进行的最晚可能;

    l         最早结束时间(Late Finish,简称LF), 在不拖延项目进度的情况下,该活动可以完成的最晚可能;

    如下图所示,对每一个项目活动的这4个参数都是一个时间点。

    制定进度计划 <wbr>关键路径分析

    图 - 3.        正推法和倒推法的活动参数

    所谓正推法就是从项目的第一个活动到最后一个活动跟踪全部活动的先后关系,计算出每个活动的最早开始时间(ES)和最早结束时间(EF)。

    所谓倒推法则是从最后一个活动开始向前追溯到第一个活动,计算出每个活动的最晚开始时间(LS)和最晚结束时间(LF)。

     

    正推法的计算过程包括四步:

    步骤一:设定项目的第一个活动的最早开始时间是从第一天开始,如图:

    制定进度计划 <wbr>关键路径分析

    图 - 4.        关键路径正推法的步骤一

    步骤二:计算第一个活动的最早结束时间,可以用第一个活动的最早开始时间加该活动的历时减1得出:EF = ES + 历时-1,如图:

    制定进度计划 <wbr>关键路径分析

    图 - 5.        关键路径正推法的步骤二

    步骤三:计算该活动的所有后续活动的最早开始时间(ES):

    后续活动的ES=前导活动的EF1

    制定进度计划 <wbr>关键路径分析

    图 - 6.        关键路径正推法的步骤三

    步骤四:过重复步骤二、三,为项目中的每个活动计算最早开始时间(ES)和结束时间(EF),如图所示:

    EF = ES + 历时 – 1

    ES = 前导活动EF + 1

    制定进度计划 <wbr>关键路径分析

    图 - 7.        关键路径正推法的步骤四

    但是这里有一种情况需要特别考虑,因为正推法是依赖每个活动的前导活动来决定的,所以如果一个活动存在多个前导活动的话,需要采用前导活动中EF最晚的那个活动来计算该活动的ES。简单来说,当前活动最早什么时候开始,取决于它的所有紧前活动(1一个或者多个)中哪一个是最晚结束的(这里指的是EF的最大值)

     

    倒推法的计算过程也包括四个步骤,只不过这次你是从项目的结束时间开始。但这里要用到正推法的结果:

    步骤一:因为你不能延误项目的完成时间,因此最后一个活动的最早结束时间EF等同于最晚结束时间LF。(此处要记住!!最后一个活动的EF=LF)

    制定进度计划 <wbr>关键路径分析

    图 - 8.        关键路径倒推法的步骤一

    步骤二:计算最后一个活动的最晚开始时间,可以通过用最晚结束时间减去该活动的历时然后加1来得出。

    LS = LF – 历时+1

    制定进度计划 <wbr>关键路径分析

    图 - 9.        关键路径倒推法的步骤二

     

    步骤三:每个活动必须在后续活动开始之前完成,因此可以为每个活动计算最晚结束时间。

    LF = 后续活动 LS – 1

    制定进度计划 <wbr>关键路径分析

    图 - 10.    关键路径倒推法的步骤三

    步骤四:然后重复第二、三步骤,计算出每个活动的最晚开始时间和最晚结束时间

    制定进度计划 <wbr>关键路径分析

    图 - 11.    关键路径正推法的步骤四

    同样在计算过程中也需要处理一个特殊情况,由于倒推法是依赖每个活动的后续活动来考虑的,所以如果一个活动出现多个后续活动的时候,应该取后续活动中LS最早的那个来计算该活动的LF。简单来说,知道了当前D活动最晚开始时间,假设D前面有并排的B,C活动,那么B和C活动的最晚结束时间等于D活动的最晚开始时间!

     

    事实上在完成倒推法的计算之后,我们得到了每个活动有关进度的关键信息:

    l         最后一个活动的EFLF)就是项目可能的最早完成时间,也就是项目的最终进度;

    l         活动的LS确定了我们需要给该活动提供资源的最晚时间,如果超过了这个时间则意味着可能的项目最早交付时间会被延迟;

    l         项目中历时最长的路径就是项目的关键路径

    l         如果关键路径上的活动历时没有被延误,那么项目进度就不会有延误;

    l         如果我们要缩短项目的历时,就要缩短该路径上活动的历时;

    l         我们可以通过公式来计算每个活动的总浮动时间(Total FloatTF = LF-EF,又被称为总时差。它代表了在不影响项目总体进度的前提下,活动可以延误的时间段;

    l         我们还可以通过公式计算每个活动的自由浮动时间(Free Float)FF(活动X)=后续活动的ES - EF(活动X)- 1。它代表了该活动不影响后续活动而可以被延误的时间。上面所说的总时差是自由浮动时间的一种。总时差是每个活动历时可以延误的范围,并且可以不影响总体 项目的进度,而自由浮动时间是指在不延误任何活动最早开始的情况下,项目活动可以延误的时间范围。

     

    下面我们来看一个例子的推演,帮助大家更好的理解。如下图是一个小项目的网络图,已经完成每个活动的历史估算,我们需要确定利用正推法和倒推法求出个活动的ES-EF-LS-LF,以及项目的关键路径:

    制定进度计划 <wbr>关键路径分析

    图 - 12.    例题-推算关键路径

    正推法求ES-EF:

    步骤一:活动A的ES=1,EF=ES+20-1=20,如下图:

    制定进度计划 <wbr>关键路径分析

    图 - 13.    例题-推算关键路径正推法步骤一

    步骤二:求出以活动A为前导活动的那些活动的ES以及EF。

    ES = 前导活动的EF+1  EF = ES + 历时 - 1

    如下图:

    制定进度计划 <wbr>关键路径分析

    图 - 14.    例题-推算关键路径正推法步骤二

    步骤三:重复步骤二,计算出所有活动的ES-EF。但对于出现了两个前导活动的活动E来说,由于B的EF晚于D的EF,所以其计算取B的EF。如下图:

    制定进度计划 <wbr>关键路径分析

    图 - 15.    例题-推算关键路径正推法步骤三

    然后我们用倒推法来计算LS-LF。

    步骤一:设最后一个活动E的LF=EF。LS = LF  历时 + 1。如下图:

    制定进度计划 <wbr>关键路径分析

    图 - 16.    例题-推算关键路径倒推法步骤一

    步骤二:计算那些以活动E为后续活动的活动的LF-LS。

    LF = 后续活动的LS  1    Ls = LF  历时 + 1

    如下图:

    制定进度计划 <wbr>关键路径分析

    图 - 17.    例题-推算关键路径倒推法步骤二

    步骤三:重复步骤二计算所有活动的LS-LF。其中活动A有两个后续活动B和C,

     

    TF=10

    制定进度计划 <wbr>关键路径分析

    图 - 18.    例题-推算关键路径倒推法步骤三

    现在我们就得到了这个项目的关键路径:A- B-E。对于每一个活动的进度要求信息也很清楚,我们可以看到每个活动的浮动时间。在关键路径上活动的浮动时间都为0,意味着这些活动不能有半点拖延。而 活动C和D的浮动时间为10,所以只要延误在10以内就不影响项目的总进度。因此我们可以灵活安排活动C和活动D的资源,可以在这些活动即将开始的时候再 安排资源。这些活动也可以在最早开始时间时开始,也可以延后10天才开始,但都不会影响项目的结束。在资源平衡过程中,我们也经常会用到总时差。

    实际上,活动C和活动D有10天的浮动时间,并不是意味着每个活动都有10天的浮动时间,而是两个活动共有10天的浮动时间。我们习惯上将活动C的浮动时间扣除掉,即只有活动D有浮动时间。路径CD的浮动时间仅为10天。

     

    但是活动C的总时差和活动D的总时差是有差别的。换句话说,就是活动C允许偏离进度的时间和活动D允许偏离进度的时间是有差别的。

    如果活动D在第31天开始,这是活动D的最早开始时间,由于活动D有10天的延误时间,那么该活动在第60天结束,那么会不会影响项目的结束呢?回答是:不会。

    现在,我们假设活动C 可以准时在第21天开始,并且最晚要在第40天时完成。如果这样的话就不会影响项目的进度。但由于活动C的进度发生偏离,那么会影响项目D不能在最早时间 开始和最早时间结束。如果在工作计划中,被安排到活动D的资源的使用时间段为:第31天到第40天。在第40天的时候,这些资源将被撤走,安排到其它的项 目中。因为活动C的进度延误将会导致活动D的资源出现短缺,因而活动D也会出现延误,并最终导致项目的延误。因此活动C间接地导致了项目的延误。

    在这里我就可以看到总时差和自由浮动时间的区别,例如:

    FF(活动C)=31(后续活动最早ES)-30(EF(活动C))- 1 = 0

    FF(活动D)=61(后续活动最早ES)-50(EF(活动C))- 1 = 10

    因此活动D有10天的自由浮动时间,而活动C没有。


    注意:如果项目第一个节点的ES设置为0,那么计算起来就方便了,

    所谓活动从第0天还是第1天开始,意思是说要不要把活动开始的那一天计算在工作时间段内。因为现实中第0天是不存在的,所以活动开始的那一天就不需要计算在内;而活动从第1天开始,由于第1天是存在的,就需要计算在工作时间段内。这两种情况导致当前活动的EF或者LS,紧后活动的ES和LF在计算时要考虑是否减去或加上这1天的问题。


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



    展开全文
  • 关键路径法(CPM)

    千次阅读 2013-11-06 15:13:06
    关键路径法(CPM),也称为关键路径分析,是一种用来预测项目总体历时的项目网络分析技术,它既可以用来估计软件项目的总体进度,也是帮助项目经理克服项目进度拖延现象的一种重要工具。  一个项目的关键路径是指...
  • Python小白的数学建模课-21.关键路径法

    千次阅读 多人点赞 2021-07-15 10:52:35
    关键路径法是基于进度网络模型的方法,用网络图表示各项活动之间的相互关系,获得在一定工期、成本、资源约束条件下的最优进度安排。 NetworkX 提供了拓扑序列和关键路径的函数,但没有给出计划网络分析的时间参数,...
  • 关键路径

    2014-06-16 09:59:09
    写这篇博客的原因主要是因为觉得数据结构的书上有关关键路径求法讲的太理论了。本人头脑简单所以一时难以接受,所以,自己凭借着之前搞ACM的基础自己研究了一个,在HDU 上提交验证是正确的。  其实,关键路径...
  • PMP知识点总结—关键路径法

    千次阅读 2012-05-19 20:06:00
    关键路径法(CPM),也称为关键路径分析,是一种用来预测项目总体历时的项目网络分析技术,它既可以用来估计软件项目的总体进度,也是帮助项目经理克服项目进度拖延现象的一种重要工具。  一个项目的关键路径是指...
  • 项目管理之关键链VS关键路径法

    千次阅读 2010-05-17 11:09:00
     关键链关键路径法的区别是:关键路径法是工作安排尽早开始,尽可能提前。而关键链是尽可能推迟。   项目管理培训  关键链的提出主要基于两方面的考虑:     项目经理圈子  (1)如果一项工作尽早开始,...
  • 关键路径讲解

    2020-11-14 21:47:10
    这是一个简单的AOE网,它是一个有向边的图,每两个节点之间的a0,a1之类的东西叫做时间,最后我们求得关键路径也和他们有关系。事件后面跟着的数字是权值,我们可以理解为做完这个事件所需要的时间。首先我们要知道...
  • 关键路径法(Critical Path Method, CPM)

    千次阅读 2010-09-24 07:54:00
    关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种,属于肯定型的网络图。
  • 关键路径计算

    万次阅读 多人点赞 2017-09-03 13:58:48
     至此已介绍完了四个特征属性的求法,也出了上图中边的e(i)和l(i),取出e(i)=l(i)的边为a1、a2、a4、a8、a9,即为关键路径上的边,所以关键路径有两条:a1 a4 a9和 a2 a8 a9   ...
  • 选择题快速求解AOE网的关键路径

    千次阅读 多人点赞 2020-11-28 12:12:26
    王道的书上在举例子的时候,备注了一小行话:“如果这是一道选择题,根据上述ve()的过程就已经能知道关键路径。”,但并没有展开讲如何确定。本文就补充说明一下。 #求法 这里直接举例给出求法 如下AOE图,我们...
  • 计划评审技术PERT和关键路径法CP

    万次阅读 2014-12-04 13:57:28
    关键路径法(CPM), 也称为关键路径分析,是一种用来预测项目总体历时的项目网络分析技术,它既可以用来估计软件项目的总体进度,也是帮助项目经理克服项目进度拖延现象的一种重要工具。   一个项目的关键路径...
  • PMP关键路径终极例题

    2018-08-25 14:06:38
    关键路径法是PMP必考的知识点,我们在编写《PMBOK指南》第六版辅导教材(暂定书名《PMP考试全解读》)的过程中,对其进行了详细的整理说明,除了明确考试的重点,还对其中考生常见的模棱两可的知识点进行了图解说明...
  • 在学习了拓扑排序之后,我们可以开始学习关键路径了。拓扑排序可以有多个起点和多个终点,跟拓扑排序不同的是,关键路径只能有一个起点、一个终点。 我们使用带有权重的有向图表示,8 -> 0 -> 1 -> 4 ->...
  • 经典算法之关键路径

    千次阅读 2018-07-19 16:29:56
    问题提出: 设一个工程有11项活动,9个事件,事件V1 ----- 表示整个工程开始,事件V9 ----- 表示整个工程结束。 每个事件的开始必须是它之前的活动已完成。...关键路径:AOE-网中,从起点到终点最长...
  • 然后看紧前工作(以一个工作起点事件作为终点事件的工作) 例如B的紧前是A,就在A与B之间画一个从A指向B的箭头 画出开始和结束节点,最后填上时间,很简单 三、双代号网络图绘制、工作计算关键路径法 (1)双代号...
  • DAG图中的关键路径算法

    千次阅读 2013-11-26 22:38:53
    简单的将就是不可以推辞的活动组成的路径,这对于工程上有着极其重要的应用,利用关键路径算法可以计算那些事件是不可推辞的,必须如期完成,下面是代码: //关键路径算法 //图的邻接矩阵表示 #include #include...
  • 项管师考试中每次都会有跟关键路径有关的题目。解答这些题目的关键就是找到关键路径。 柳纯录的项管教程的关键路径部分写的又长又啰嗦,反正我根本看不明白。 张友生的案例分析教程和试题分类精解写的关于找关键路径...
  • 实例图解关键路径及实现(C++)

    千次阅读 多人点赞 2019-01-16 00:50:18
    关键路径求解步骤 1, 先正向拓扑排序出点的最早开始时间:ve(取最大ve(j)=Max{ve(i)+dut(&lt;i,j&gt;)}) 2, 再逆向拓扑排序出点的最迟开始时间:vl(取最小vl(i)=Min{vl(j)-dut(&lt;i,j&gt;...
  • 系统分析师、信息系统项目管理师都是经常出的,网络规划设计师考纲也有项目控制的内容,我看了下大家答题的情况,很多人不了解关键路径和其相关计算的求法,考试出题有关键路径的计算,最早开始时间,最迟开始时间。...
  • 这中类型的题是高级中比较常见的,系统分析师、信息系统项目管理师都是经常出的,网络规划设计师考纲也有项目控制的内容,我看了下大家答题的情况,很多人不了解关键路径和其相关计算的求法,考试出题有关键路径的...
  • 图解:什么是关键路径

    千次阅读 多人点赞 2020-05-06 20:31:39
    小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说一说。哈哈,不过我们还是先来说一说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果...
  • 关键路径的一道练习题

    千次阅读 2020-10-17 20:20:49
    1.已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 4 6 ...(3)图G的关键路径,并计算该关键路径的长度。 (1) ...
  • 关键路径算法

    万次阅读 2010-07-30 16:47:00
    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。 1. 什么是拓扑排序? 举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须...
  • 最短路问题 一、概念: ...1. 单源最短路径问题:这种问题是最短路径问题中最基本的问题了,其主要目的是从一个固定源点开始到每一个点的最短路径;对于这个问题,所有的方法都适用; 2.
  • 关键路径的选取

    千次阅读 2007-10-22 22:08:00
     本人就例子来教大家怎样提取关键路径: 先解释一下什么叫关键路径 所谓关键路径就是,在电路中频繁调用,而且延迟过长, 或者产生意外的几率比较大的线路。 1:组合电路中的关键路径提取: q=a&b&c|d&e&b; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,014
精华内容 24,405
关键字:

关键路径简单求法