精华内容
下载资源
问答
  • 有几个基本的概念我们要先了解,在带权有向图中,顶点表示事件,有向边表示活动,以边上的权值表示活动的开销,比如完成活动所需要的时间。这样的网络称为用边表示活动的网络,也就是AOE网。 分清发生和开始 这里...

    在学习数据结构的过程中,我发现关键路径的中的概念取名使得第一印象让人容易产生误解,所以我用最通俗易懂的例子来解释解释这些概念的实际含义。

    基本概念——AOE网

    有几个最基本的概念我们要先了解,在带权有向图中,顶点表示事件,有向边表示活动,以边上的权值表示活动的开销,比如完成活动所需要的时间。这样的网络称为用边表示活动的网络,也就是AOE网。

    分清发生和开始

    这里要首先弄明白的是两个词,也就是后面要学到的概念中的 “发生” 和 “开始”。

    “发生”是针对于事件的,也就是图中的顶点。什么叫事件发生了呢?

    只有在指向该顶点的所有有向边对应的活动结束,该顶点所代表的事件才发生。

    举个例子,一个事件C,它仅被两条边a, b指向,仅当a,b两活动都完成时,事件C发生。

    “开始”是针对于活动的,也就是图中的边。

    只有在一个顶点所代表的事件发生后,从该顶点出发的所有边对应的活动才能开始。

    什么时候开始?即可以在事件一完成就立马开始接下来的活动,也可以推迟活动开始的时间。

    最早发生时间——VE

    到这里就已经能解释我们要说的第一个概念了,最早发生时间。

    我猜这里应该经常会有人有疑惑,为什么是最长的路径长度决定最早的发生时间?我越想要早发生不是越应该走短的路径吗?

    且听我说,摆脱困惑的重点是我们要和求最短路径的思路区分开,求最短路径是找尽可能短的路来保证路径长度最小,你只需要找出一条最短的路就行。但是在关键路径里,一个顶点是有多个前提的,只有前提的路径都走完,才能发生该顶点的事件,那么只有最长的路径走完,保证其余短的路都早已经走完,该事件才发生。

    我们前面说过,发生是针对于事件的,一个事件要发生,首先要指向它的活动都完成。一个事件C,被两个活动a,b指向,a活动的耗费时间是3, b活动的耗费时间是5。那么看下图,从开始到C事件的发生要多久呢?

    在这里插入图片描述
    是最大路径长度5,因为C事件发生的前提必须是a,b两活动完成(活动可同时进行),C事件只有等到b完成才发生,最早完成时间由耗时最久的路决定,所以这就是为什么要取最长路径长度。

    (我想吐槽这个命名,根本就没有什么最早,一个顶点的发生时间就只有一个,就是最长路径长。可能命名是为了和最晚发生时间对称吧。)

    所以求目标顶点最早发生时间的方法是:

    目标顶点的所有前提顶点(比如上图中C的前提顶点为A顶点和B顶点)的最早完成时间+对应的前提顶点到目标顶点的活动消耗 中的最大值。

    比如C的最早完成时间是: Max{ A的最早完成时间+A到C的活动消耗时间, B的最早完成时间+B到C的活动消耗时间}

    具体递推公式:

    1、ve(源点)=0
    2、ve(k) = Max{ ve{j} + Weight(j, k) }, j为k的任意前提顶点, Weight(j, k)表示<j, k>上的权值 。
    只要从源点开始一直递推到汇点(终点)就好了。

    最迟发生时间——VL

    最迟发生时间的定义是这样的:在不推迟整个工程完成的前提下,保证后继事件j能在其最迟发生时间vl(j)能够发生时,该事件最迟必须发生的时间。

    嚯!好家伙,自己的定义里套着自己,这一波套娃是真存心不想让人看懂。

    首先,我们要知道,汇点的最迟发生时间就是它的最早发生时间(可以理解为汇点的最早发生时间就是工期),求VL的过程我们是从汇点倒着推回去的。

    其次,为什么会有最迟发生时间呢?这是因为一个工程中,通常会存在某条路径耗时比其他路径久的多,所以耗时短的事件可以不必太早发生,也就是存在着缓冲时间。

    为了方便理解,我举一个数据大小相差较大的例子:
    在这里插入图片描述
    看看这个图,我在顶点上方写了它的最早发生时间,D是汇点,110是它的最早发生时间(也是最迟发生时间)。

    此时我们可以这样理解,如果在110天时工程必须完成,那么A事件最迟什么时候要发生?

    我们可以用110减去a活动用时,得到105,也就是说A事件最迟可以在第105天发生(一旦发生就要立刻开始a活动,否则将推迟整个工期),指向A的活动可以在第100天才开始。

    而A事件最早可以在第5天就发生(这里说最早才有意义了),最早第5天完成,但是可以推迟到第105天完成,中间差了100天了。

    同理可得B事件的最迟发生时间是第10天,它一刻也不能拖。

    这时候再回去看看最迟发生时间的定义,应该就可以理解了吧

    再刚刚举的例子里,AB事件是相互独立的,如果我再添加一个不独立的事件:
    在这里插入图片描述
    这个图中我添加了一个C顶点,它是B顶点的前提。我把已知的最迟发生时间用绿色笔迹写在了最早发生时间右边。一起看看C事件的最迟发生时间是多少吧。

    这里我们可以看到,和上图不同,C顶点有2个出度,也就意味着它影响着两个后继顶点。

    如果我们仍用上次的方法,用110-10得100,可以认为C事件最迟在第100天发生吗?

    仔细看看是不对的,B顶点的发生前提是C顶点要发生,如果C在第100天才发生,那么B事件等不了啊,B最迟在第10天就要发生,等到第100天干脆毁灭吧

    正确的做法应该是B事件的最迟发生时间减4天得第6天。由此可见,一个顶点的最迟发生时间其实是由它的后继节点所决定的,这也就解答了为什么我们要从汇点开始倒着往起点推。

    我想你也可以理解了为什么公式中使用的是 Min{} 取最小。就比如刚刚的例子,C有两个选择——第6天或者第100天,你必须得选最小的以保证你不会耽误任何后继节点的最迟发生。

    递推公式:

    vl(汇点) = ve(汇点)

    vl(k) = Min{ vl(j) - Weight(k, j) } ,k为j的任意前驱

    活动的最早开始时间——e和最迟开始时间——l

    这两个概念相比之前的就简单多了,首先,还记得我在一开始说的吗,“开始”是针对活动,也就是图中的边的概念。

    活动的最早开始时间,理解起来非常容易,边的起点事件一旦发生就立刻开始,就是最早开始时间了。

    公式:若边<k, j> 表示活动i,则有e(i) = ve(k)

    那最迟开始时间呢,这要和该边指向事件的最迟发生时间挂钩,假如在10点必须写完作业(事件),写作业(活动)要2小时,那最晚啥时候开始写作业呢?8点对吧,也就是边所指向的事件最晚发生时间 - 边对应的活动所需时间。

    公式: 若边<k, j> 表示活动i,则有l(i) = vl(j) - Weight(k,j)

    时间余量d

    d(i) = l(i) - e(i),即活动最迟开始时间与最早开始时间的差额,这代表着活动可以拖延的时间。如果一个活动的时间余量为0,就意味着该活动不能拖延时间,称为关键活动,必须立即完成,否则就将拖延整个工期。

    而时间余量为0的所有边连起来,就是关键路径了。

    要求时间余量d, 就要先求活动的最早开始时间e和最迟开始时间l,要求e和l就要先求事件最早发生时间ve和最迟发生时间vl。所以做题步骤就出来啦,最后来做一题试试看吧!
    在这里插入图片描述
    答案:
    在这里插入图片描述
    在这里插入图片描述
    最终得到的关键路径为(v1, v3, v4, v6)

    最后注意的几点:

    1、关键路径上的所有活动都是关键活动, 它是决定整个工程的关键因素,因此可以通过加快关键活动来缩短整个工期。但是也不能任意缩短,因为一旦缩短到一定的程度,该关键活动就可能变成非关键活动了

    2、网中的关键路径不唯一,对于有好几条关键路径的网,只加快其中某一条关键路径上的活动并不能缩短工期。只有加快存在于所有关键路径上的关键活动才能达到缩短工期的目的。

    写作不易 ,各位看官留个赞吧

    本文转载自知乎:Eee帆
    侵删
    链接:你一定看得懂的关键路径概念

    展开全文
  • 软件设计师--最早开始时间和最晚开始时间

    万次阅读 多人点赞 2018-04-20 18:03:53
    先求最早开始时间:A是开始节点,所以A的最早开始时间是0,并且最早开始时间等于最晚开始时间。等得到图中红色的部分。 其他节点的最早开始时间为以该节点作为弧头的所有有向弧的值+弧尾的值 的最大值,看例子就...

    题目如图所示,解法如下:

     

    方法:

    先求最早开始时间:A是开始节点,所以A的最早开始时间是0,并且最早开始时间等于最晚开始时间。等得到图中红色的部分。

    其他节点的最早开始时间为以该节点作为弧头的所有有向弧的值+弧尾的值 的最大值,看例子就明白了:

    然后求其B的最早开始时间,由B作为弧头的有向弧只有<A,B>且值为2,A的最早开始时间为0,所以B的最早开始时间为0+2=2,得到绿色的结果。

    求C的最早开始时间,以C为弧头的弧只有<B,C>且值为3,B的最早开始时间为2,所以C的最早开始时间为2+3=5,得到黄色结果。

    同理D、G、E的最早开始时间如图所示。

    求F的最早开始时间:以F为弧头的弧有<E,F> <B,F> <G,F> 所对应的值分别为 13 6 13,取MAX{13,6,13}得F的最早开始时间为13,得到紫色结果.

    后面的都一样...

    然后由于J是结束节点,所以最早开始时间与最晚开始时间一样,得到图中的 这个色结果。

     

    接着求最晚开始时间从后往前推。

    先求I的最晚开始时间。应为以I为弧尾的只有弧<I,J>所以,I的最晚开始时间为J的最晚开始时间减去<I,J>的值 18-2=16

    同理F H的最晚开始时间也可以得到。

    求E的最晚开始时间: 以E为弧尾的弧有 <E,H> <E,F> H的最晚开始时间减去<E,H>的值为12   F的最晚开始时间减去<E,F>的值为13-3=10 ,取MIN{12,10}得到E的最晚开始时间为10

    ....

    后面都一样了....

     

    完成项目的最少时间就是结束节点的最早或最晚开始时间 18

    两条关键路径都画在图中了

    BC在关键路径上,所以一天也不能晚;

    BF可以耽搁的时间为 F的最晚-B的最早-<B,F>的值,也就是 13-4-2=7

     

    口诀:最早开始从前往后用加法看弧头最大,最晚开始从后往前用减法看弧尾最小

     

    展开全文
  • AOE网活动的最早、最迟发生时间及关键路径问题

    万次阅读 多人点赞 2018-05-22 18:10:12
    上个学期学数据结构的时候有学到,这学期的离散数学又要考。。复习复习 ...在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE(Activity On Edge)网,如图:  如何求AOE网...

    免费浏览请前往:https://zhuanlan.zhihu.com/p/337438327

    上个学期学数据结构的时候有学到,这学期的离散数学又要考。。复习复习

    有向图中,用顶点表示事件,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

    在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE(Activity On Edge)网,如图: 

    如何求AOE网中各事件(节点)和各活动(边)的最早开始时间和最迟开始时间以及工程的关键路径?

    整个活动的完成时间是AOE图中从始点到终点的最长路径的长度,这条路径称为关键路径。关键路径上的活动称作关键活动。

    注意:关键路径不一定只有一条。

    1.最早发生时间:从前往后,前驱结点到当前结点所需时间,取最大值。

    如上图中的节点4有两个前驱结点(节点2和3),节点2到节点4的最早发生时间是a1+

    展开全文
  • 1)一个点的最早/最晚时间是有公式或者技巧求出来的 2)一个活动的最晚开始几天不影响,或者一个活动可以耽搁的时间,是有公式计算的 3)关键路径为起点到终点权值加起来最大的路径 直接例题 首先,关键路径为最大...

    1)一个点的最早/最晚时间是有公式或者技巧求出来的

    2)一个活动的最晚开始几天不影响,或者一个活动可以耽搁的时间,是有公式计算的

    3)关键路径为起点到终点权值加起来最大的路径

    直接例题
    在这里插入图片描述

    首先,关键路径为最大(大)的总值,计算可以得到ABCEFJ=18,所以关键路径的值为18

    一、一个点的最早开始时间:从起点到该点的最长(大)的值
    • A:起点,最早开始时间为0
    • B:起点到B只有AB=2
    • C:起点到C只有ABC=2+3=5
    • D:起点到D只有ABD=2+2=4
    • E:起点到E只有ABCE=2+3+5=10
    • F:起点到F有ABCEF=13
      ABF=6
      ABDGF=13
      取最大,其中ABCEF和ABDGF一样值,所以F的最早开始时间为13
    • G:ABDG=7
    • H:ABCEH=12
    • I:ABDGI=13
    • J:J有H,F,I 这3个点到J,其中ABCEHJ=12+4=16
      0到F最大+<F,J>=13+5=18
      0到I最大+<I,J>=13+2=15
      取最大,所以J的最早开始时间为18

    二、一个点的最晚开始时间:关键路径的值 - 终点到该点的最大的值

    或者这样理解:关键路径的值 - 终点到该点的值,如果得到的有多个值,那么取最小

    MIN { 关键路径的值 - 终点到该点的值 }

    为了方便运算,求最晚的都是通过反方向来求的

    • J:0
    • H:重点到H只有JH,18-4=14
    • F:18-5=13
    • I:18-2=16
    • E:有JFE=8
      JHE=6
      有最晚开始时间MIN{ 18-8=10,18-6=12 }=10
    • G:有JFG=11
      JIG=8
      最晚开始时间 MIN{ 18-11=7,18-8=10}=7
    • C:因为已经求出E了,可以更简单地运算
      E的最晚开始时间 - <C,E>=10-5=5
    • D:G的最晚开始时间 - < D,G>=7-3=4
    • B:反方向回来的,有C和D两个点到B,则
      BC的方向:C的最晚开始时间 - <B,C>=5-3=2
      DB的方向:D的最晚开始时间 - <B,D>=4-2=2
      所以B的最晚开始时间为2

    三、活动的最长耽搁时间/最晚开始X天不影响整体=后继点的最晚-前驱点的最早-该活动的值

    比如

    • 活动BF最长耽搁时间=F的最晚-B的最早 - <B,F>=13-2-4=7
    • 活动BC最长耽搁时间=C的最晚-B的最早 - <B,C>=5-2-3=0

    其他的也一样,就不写了

    四、活动最迟(晚)应该在第X天开始(出发):关键路径-前驱点到终点的最小值

    或者说max{ 关键路径 - 前驱到终点的值}
    活动GI最迟应该在第X天出发?
    18-8=10,其中GIJ为 8 ,关键路径为18
    GFJ为11,则18-11=7,10与7取最大,则活动GI最迟应该在10天出发

    五、松弛时间

    松弛时间=关键路径的总时间-包含该任务的关键路径花的时间
    还有一种说法不知道对不对,松弛时间=前驱的最晚时间 - 前驱的最早时间

    展开全文
  • 关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(最早最晚时间、时差)等。...
  • 场景:一张定单有多个环节,一个环节可能出现多次,计算每个环节从派发到完成时间1.介绍 LAST_VALUE 和 FIRST_VALUE 函数2.sql实战示例 1.介绍 LAST_VALUE 和 FIRST_VALUE 函数 函数的作用恰如其名,取出首尾记录...
  • 活动i的最早时间 = 头节点的最早时间; 活动i的最晚时间 = 尾节点的最晚时间 - 活动i的持续时间; 也就是将e(i)和l(i)转换到计算Event的ee值和le值上面去,这两个值就是最早时间和最晚时间,它们可以...
  • 关键路径:最早开始时间 计算方式:每个节点找它到下个节点的最大路径 具有最大路径长度的路径为关键路径。因为你得保证每个人都到场才能去看电影嘛,那你肯定得等到最后一个人到了才能走。图中就是v...
  • 信息系统项目管理师计算题

    千次阅读 2020-12-18 20:06:50
    一、 时间管理:关键路径法(重点)、完工概率(难点) 关键路径法:上下午都可能考核,涉及到:ES、EF、LS、LF计算;关键路径计算、总时差、自由时差。 完工概率:考核基础是三点估算法,标准差,在此基础上进行...
  • (1):根据各项活动的活动时间计算各个事件的最早时间与最迟时间,并填入图中事件2-8相应位置。 (2):写出关键事件。 答:最早时间:从前往后计算; 最迟时间:从后往前计算。 关键事件:即开始时间和结束时间...
  • 最早截止时间优先(EDF)

    千次阅读 2018-11-12 19:28:49
    最早截止期限优先(EDF)调度根据截止期限动态分配优先级。截止期限越早,优先级越高;截止期限越晚,优先级越低。 根据 EDF 策略,当一个进程可运行时,它应向系统公布截止期限要求。优先级可能需要进行调整,以便...
  • 原图: 1.选中要隐藏的工期、开始时间、完成时间; 2.右键选择“字体”; 3.字体设置为"Cambria Math"; 4.点击“确定”。 最终效果:
  • 最早截止时间优先算法(Earliest Deadline First,EDF) 定义:EDF算法是指根据任务的截止时间来确定任务的优先级的算法,任务截止时间越早,其优先级愈高。 作用对象:即可用于抢占式调度方式中,也可以用于非...
  • 轮转调度算法和最早截止时间优先调度算法
  • 对于每个活动,列出它的前驱,并计算最早开始时间、最晚开始时间和时差,然后确定出关键路径。 —— 《软件工程 第 4 版》中的原题 写文缘由 网上的文章大都是对于 “点” 求最早开始时间和最晚开始时间。在我看来...
  • 估算完成整项工程至少需要多少时间 判断哪些活动是影响工程进度的关键 分析 整个工程只有一个开始点和一个完成点,所以在正常的情况(无环)下,网中只有一个入度为零的点,称为源点,也只有一个出度为零的点,...
  • 最早完成工作M的时间是第21天,下次项目开始的最早是第25天,所以自由时差是25-21=4天。 (自由时差,简称FF(Free Float),指一项工作在不影响其紧后工作最早开始时间的条件下,本工作可以利用的机动时间。 ) 总...
  • 构造PERT图,需要明确四个概念:事件、活动、松弛时间和关键路线。1、事件(Events)表示主要活动结束的那一点;2、活动(Activities)表示从一个事件到另一个事件之间的过程;3、松弛时间(slack t...
  • 关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(最早最晚时间...
  • 最早截止时间优先即EDF算法

    万次阅读 2014-05-12 16:40:14
    1. 最早截止时间优先EDF(Earliest DeadlineFirst)算法是非常著名的实时调度算法之一。在每一个新的就绪状态,调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务,并将执行该任务所需的...
  • PERT图相关计算

    千次阅读 2017-08-29 14:49:49
    在关键路径上,从开始到该任务的最早执行的时间最晚开始时间: 关键路径的总时间-反向得出该任务的时间松弛时间(最多延迟执行的时间): 注意:在关键路径上的任务的松弛时间为0 第一种求法: 最晚开始时间-...
  • 最早截止时间有限(EDF)算法: 截止时间越早,优先级越高 最低松弛度优先(LLF)算法: 松弛度=完成截止时间-仍需运行时间-当前时间 松弛度越低优先级越高,当正在执行时有其他松弛度更低的进程进入队列也不会暂停当前...
  • PERT图

    千次阅读 2018-09-01 21:56:14
    1.结点(事件):图中的圆,...最早时刻:此刻之前从该事件出发的任务不可能开始。   4.最迟时刻:从该事件出发的任务必须在此时刻之前开始,否则整个工程不能如期完成。   5.松弛时间:表示不影响整个工期前提...
  • 进度安排——Pert 图

    千次阅读 2016-10-31 23:23:03
    时间管理(进度管理)中,甘特图和 Pert 图是常用的两种图形。...Pert 图是一个有向图,能清晰地描述子任务之间的依赖关系,起点到终点之间路径值最长的路径为关键路径(其路径值为完成此工程项目需要的最少时间)。
  • 有若干个活动,第i个开始时间和结束时间是[Si,fi),只有一个活动场地可以利用,活动之间不能交叠,求最多安排多少个活动? 问题分析 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用...
  • 【庖丁解牛系列】【项目时间管理】前导图/单代号网络图
  • 瀑布模型是最早出现的 软件开发模型 ,在软件工程中占有重要的地位,它提供了软件开发的基本框架。其过程是从上一项活动接收该项活动的工作对象作为输入,利用这一输入实施该项活动应完成的内容给出该项活动的工作...
  • Git使用详细教程

    万次阅读 多人点赞 2018-01-02 15:41:45
     Git是目前世界上先进的分布式版本控制系统。  二:SVN与Git的主要的区别?  SVN是集中式版本控制系统,版本库是集中放在中央服务器的,而干活的时候,用的都是自己的电脑,所以首先要从中央服务器哪里得到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 440,078
精华内容 176,031
关键字:

最早完成时间