AOV网(activity on edge netwo)(边表示活动的网):在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间。
源点:整个工程的开始点,其入度为0。
终点:整个工程的结束点,其出度为0。
事件 | 事件含义 |
v0 | 工程的开始,事件a0和a1开始 |
v1 | 事件a0完成后,事件a2和a4开始 |
v2 | 事件a1和a2完成后,事件a3开始 |
v3 | 事件a3和a4完成后,工程结束 |
AOE网的性质:
- 只有在进入某顶点的各活动都已经结束,该顶点所代表的事件才能发生
- 只有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始
关键路径:AOE网中从源点到终点的最长路径
关键活动:关键路径上的活动
不按期完成关键活动就会影响整个工程的进度,要缩短整个工期,必须加快关键活动的进度
算法:关键路径算法
输入:带权有向图 G=(V,E)
输出:关键活动
1. 计算各个活动的最早开始时间和最晚开始时间
2. 计算各个活动的时间余量,时间余量为 0 即为关键活动
小结论:
- 任意一个关键活动延期,活动延期 T
- 任意一个关键活动加快,活动一定加快 F
- 任意一个非关键活动延期,活动也可能延期 T
- 任意一个非关键活动加快,活动一定不加快 T