求图的关键路径

1. 工程和时间说明

一个工程可以由多个活动和里程碑构成。活动可能对里程碑存在依赖性。在活动可并行的情况下,可以通过每个活动所需要的时间和依赖关系,计算出完成整个项目所需要的时间。

如以节点为里程碑,箭头为活动,一个项目的数据如下:

可以从一个入度为0的节点开始宽度优先顺序计算时间,也可以通过拓扑排序顺序进行计算,得到

比较容易得到每个里程碑的最早完成时间。

2. 关键路径说明

仅知道每个事件的可以的完成时间往往并不足够。工程中还想知道更多的关键信息,如:

  • 哪些活动可以随意延期而不影响项目总进度?
  • 哪些活动必须重点关注,一旦延期会拖延整个项目进度?
  • 如果想提前整个项目的完成时间,可以最小地压缩哪几个活动?

这种问题在工程或者项目管理中非常常见,也因此引入了关键路径这个概念:

  • 关键路径上的活动影响着整个项目的进度
    • 关键活动延期一定会影响项目
    • 关键活动缩减有两种情况
      • 使自己不再是关键活动
      • 或缩短了整个项目完成时间
  • 非关键的活动可以一定程度延期(但延期过多也可能成为关键路径,所以需要根据调整实时重新计算和权衡)

在omniPlan等常见项目管理工具中,可以轻松计算出关键路径。

3. 关键路径计算

当计算出各个里程碑的最短完成时间后,为各活动标注其最早开始时间,由于活动的起点只会有一个里程碑,计算也非常简单,就是起点里程碑的最早开始时间:

之后,需要计算各个活动的最晚开始时间:

计算方式为

  1. 获得最晚的最早完成时间,记 globalLatestStartTime
  2. 逆拓扑排序顺序进行处理
    1. 如果里程碑还没有记录其 最晚开始时间,则令其 最晚开始时间 为 globalLatestStartTime
    2. 以其为终点的活动的最晚开始时间 = 其最晚开始时间 – 活动所需时间
  3. 处理完毕后可以获得每个里程碑和活动的最晚开始时间。
  4. 对于里程碑,如果其 最早完成时间 与 最晚开始时间一致,则意味着没有延期的空间,是关键里程碑
  5. 对于活动,如果其 最早开始时间 与 最晚开始时间一致,也意味着此活动没有延期空间,是关键活动
  6. 将标注的关键活动和里程碑串成路径,即为关键路径。注意有可能会有多种串的方式,即多条关键路径。这种情况下意味着有活动并列为关键,并列的关键活动任意延期都会使项目延期,而任意提前完成会使其不再关键。

Leave a Comment