关键路径
AOE网络必须是拓扑图,
其中的每一条边被称为一个活动,每一个结点被称为一个事件,一般来说整个网络会有一个源点,和一个汇点,多个也没关系,但必须要是一个拓扑图,如果不是拓扑图就没有AOE网络和关键路径这一说了。(因为可能会存在环)
每一个事件对应AOE网络中的一个结点,结点是没有时间的,而每一个活动对应于AOE网络中的一条边,活动都会有一个时间,即就是AOE网络中的每条边会有一个大于等于0的权值。
在AOE网中如果想到达某个事件的话,需要把该事件前面所有的边都走完才可以。即结点和边是有依赖关系的,要到达该点则就需要把通往该点的所有边都走完才能到。(整个工程是可以并行做的,几条边(几个事件)可以同时一起做)
Eg:
需要把图中1、2、3这三条路径都走完,才能够到达右上角的那个点。
从最左边的起点(源点)出发,有两条,路径可以选择:即 1 和 2、3 ,则易知,到达右上角终点(汇点)所需要经过的最少时间,就是这两条路径的边权和,取最大值,因为取最大值才能保证,另外一条路径已经走完。
关键路径:在以上限制的情况下,整个工程最少需要多少时间才能完成。
其中最少需要多少时间,其实就是从源点到汇点的一个最长路。要想让整个工程完工,则要保证这个路径(时间) 大于等于 所有能到达汇点路径的长度(时间)。只要让最长的一条路径的时间满足了,那么中间所有路径都可以满足。
注:任意一条最长路都是关键路径,关键路径不一定唯一。
几个概念
首先需要明确:事件是点,活动是边
事件最早开始时间:每个点最早从什么时候开始做,即从源点到当前点的所有路径,最长一条路径的长度是多少,即这个事件最早可以开始的时间。
事件最晚开始时间(保证不延期的情况下,最晚开始时间):先看一下整个工程的工期是多少,然后再看一下当前点到终点的所有路径中最长的一条路径,用整个工期的时间,减去该点到终点最长路径的长度,就是该点最晚开始的时间。因为要给最长的路径留足时间。
活动最早开始时间:活动的最早开始时间就是活动的起点的这个事件最早开始的时间。
活动最晚开始时间:与事件最晚开始时间不同,活动(即图中的一条边),不一定等于其弧尾结点(事件)的最晚开始时间。
eg:
容易发现该图的关键路径长度是27(1,2,5,6或1,3,5,6),现在来研究事件2和活动d的最早最晚开始时间。
最早开始时间比较容易分析,从源点1到事件2的最长距离12,即为事件2和活动d的最早开始时间。
事件2的最晚开始时间:从经过事件2的关键路径可以推得,事件2的最晚开始时间应该为27 - h - e = 12,再晚开始事件2则会影响整个工程的进度,使得关键路径长度增加。
活动d的最晚开始时间:活动d的最晚开始时间和事件2没有直接的联系,由整个工程的关键路径可知,活动d最晚开始时间需要保证之后d + g <= 27,即最晚不能推迟整个工程的进度,所以活动d最短开始时间即为:27 - d - g = 14
(虽然事件2的最晚最早开始时间都是12,但并不意味事件2结束它所直接连接的活动就需要立即开工)
关键活动:最早开始时间和最晚开始时间相等的时间。
关键事件:最早开始时间和最晚开始时间相等的事件。