关键路径

  • AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应，它通常表示一个工程的计划或进度。
  • AOE网是一个带权的有向无环图，图中的：
    • 边：表示活动(子工程)，
    • 边上的权：表示该活动的持续时间，即完成该活动所需要的时间；
    • 顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。
  • 其中有两个特殊的顶点(事件)
    • 一个称做源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边；
    • 另一个称做汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出边。除这两个顶点外，其余顶点既有人边，也有出边，是入边活动和出边活动的转接点。
  • AOE网中有些活动可以并行，完成工程的最短时间是源点到汇点最长路径长度，这条路径称为关键路径
  • 对于一个AOE网，研究得问题是
    • 整个工程需要多长时间完成
    • 哪些活动是影响进度的关键
      • 正推最早开始时间
      • 逆推最晚开始时间
      • 如果相等就是关键