跳转到内容

AOE网

本页使用了标题或全文手工转换
维基百科,自由的百科全书

AOE网(Activity On Edge Network)即边表示活动的网,是一个带权的有向无环图,其中顶点表示事件(Event),每个事件表示在它之前的活动已经完成,在它之后的活动可以开始,表示活动,表示活动持续的时间。AOE网可用来估算工程的完成时间。由于整个工程只有一个开始点和一个完成点,故在正常的情况(无环)下,网中只有一个入度为零的点(源点)和一个出度为零的点(汇点)。

AOE网有待研究的问题

  1. 完成整项工程至少需要多少时间?
  2. 哪些活动是影响工程进度的关键?

由于在AOE网中有些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(路径上各活动持续时间之和)。路径长度最长的路径叫做关键路径。假设开始点是,从的最长路径长度叫做事件最早发生时间,这个时间决定了所有以为尾的所表示的活动的最早开始时间。用e(i)表示活动的最早开始时间,l(i)为一个活动的最迟开始时间,这是在不推迟整个工程完成的前提下,活动最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动时间余量。l(i)=e(i)的活动叫做关键活动。关键路径上的所有活动都是关键活动,提前完成非关键活动(不在关键路径的活动)并不能加快工程的进度。为了求得AOE网中活动的e(i)和l(i),首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动由弧<j, k>表示,其持续时间记为dut(<j, k>),则有:e(i) = ve(j), l(i) = vl(k) - dut(<j, k>)。求ve(j)和vl(j)需分两步进行:

  1. 从ve(0)=0开始向前递推,其中T是所有以第j个顶点为头的弧的集合。

  1. 从vl(n-1)=ve(n-1)起向后递推,其中S是所有以第i个顶点为尾的弧的集合。

活动最早开始时间e[i]

  • 若活动是由弧<,>表示,根据AOE网的性质,只有事件发生了,活动才能开始。也就是说,活动的最早开始时间应等于事件的最早发生时间。因此,有:e[i]=ve[i]

活动最晚开始时间l[i]

  • 活动的最晚开始时间指,在不推迟整个工程完成日期的前提下,必须开始的最晚时间。若 由弧< ,>>表示,则的最晚开始时间要保证事件的最迟发生时间不拖后。因此,应该有:l[i]=vl[j]-dut(<,>)

由此得到求关键路径的算法:

  1. 输入e条<j, k>,建立AOE网的存储结构;
  2. 源点出发,令ve[0]=0,按拓扑顺序求其余各顶点的最早发生时间ve[i]()。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止,否则转到步骤(3);
  3. 汇点vn出发,令vl[n-1]=ve[n-1],按逆拓扑顺序求其余各顶点的最迟发生时间vl[i]();
  4. 根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某满足条件e(s)=l(s),则为关键活动。