AOE关键路径步骤+例题

• 算法结构

一、 基本概念

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)

AOE网具有以下两个性质：

  1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
  2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生

    另外，有些活动是可以并行进行的

在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为

关键路径，而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度

eg1.

在这里插入图片描述

图中，源点为V1，汇点为V4。从V1到V4有两条路径，2更长。故2为关键路径。长度为6

1.1 ve(k),e(i),vl(k),l(i)的定义

事件

v

k

v_k

vk​（结点）的最早发生时间设为

v

e

(

k

)

ve(k)

ve(k)。只有指向该结点的所有活动

a

i

a_i

ai​都完成后，才可发生事件

v

k

v_k

vk​。

活动

a

i

a_i

ai​（边）的最早开始时间设为

e

(

i

)

e(i)

e(i)。只有活动的弧头的时事件完成后，才可进行活动

a

i

a_i

ai​

事件

v

k

v_k

vk​的最迟发生时间

v

l

(

k

)

vl(k)

vl(k)。它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

活动

a

i

a_i

ai​的最迟开始时间

l

(

i

)

l(i)

l(i)。它是指该活动弧的终点所表示事件

v

k

v_k

vk​的最迟发生时间

v

l

(

k

)

vl(k)

vl(k)与该活动所需时间

a

(

i

)

a(i)

a(i)之差。

活动

a

i

a_i

ai​的时间余量

d

(

i

)

=

l

(

i

)

−

e

(

i

)

d(i)=l(i)-e(i)

d(i)=l(i)−e(i)，表示在不增加完成整个工程所需总时间的情况下，活动

a

i

a_i

ai​,可以拖延的时间。

若一个活动的时间余量为零，则说明该活动必须要如期完成，

d

(

i

)

=

0

d(i)=0

d(i)=0即

l

(

i

)

=

e

(

i

)

l(i)=e(i)

l(i)=e(i)的活动

a

i

a_i

ai​是关键活动

二、例题

在这里插入图片描述

  1. 求最早发生时间
0 1 2 3 4
ve(k) 0 1 4 6
e(i) 0 0 1 4

e(i)通过ve(k)得出

  1. 若必须在6分钟之后结束

    求各个事件和活动的最迟发生时间

01234
vl(k)0146
l(i)2014

三、求关键路径的步骤

思路：通过

d

(

i

)

=

0

d(i)=0

d(i)=0求得关键活动

d

(

i

)

=

0

d(i)=0

d(i)=0通过求ve()…等四个量得出

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

3.1关键活动、关键路径的特性

  • 若关键活动耗时增加，则整个工程的工期将增长
  • 缩短关键活动的时间，可以缩短整个工程的工期
  • 当缩短到一定程度时，关键活动可能会变成非关键活动
  • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期。只有加快那些包括在所有关键路径上的关键话动才能达到缩短工期的目的。

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/c51b9f7378.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐