软考复习:关键路径与总时差怎样手算

项目中最耗时的任务未必在关键路径上。

edyang · 2013-02-15

项目中最耗时的任务未必在关键路径上。关键路径由依赖关系和累计工期决定,不能按单项任务排序得到。

本文使用经典算法与关系数据库的纸面例题。复习时把概念放进一个可手算的小问题:先声明假设,再列状态变化,最后检查反例。题目中的边界条件往往比公式本身更容易失分。

1. 从现象推到机制

先正向计算最早开始和最早完成,再反向计算最迟开始和最迟完成。汇合节点必须等所有前置完成,所以正向取最大值;反向受多个后继限制,取最小值。总时差为零的任务需要连成路径判断。

软考复习:关键路径与总时差怎样手算的处理、反馈与观察关系

图中的四个节点分别表示活动网络、正向计算、反向计算、时差判断。顺着实线检查输入如何变成输出,再沿虚线核对反馈条件。图示表达的是本文讨论的关系,不是实测曲线或现场截图。

2. 最小实现与输入条件

构造两条从起点到终点的分支,所有工期统一为工作日。先不考虑资源冲突,让网络计划与人员排班的问题保持分离。

1
2
3
4
5
A(2) -> B(4) -> D(3)
A(2) -> C(2) -> D(3)
path A-B-D = 9
path A-C-D = 7
slack(C) = 2

例题中的规模和耗时都是教学输入。先手算一遍,再用短程序核对;记录推导过程,避免只背住选项或最终数字。实际系统的性能不能直接从纸面复杂度推出。

3. 用对照区分原因

下表列出需要主动改变的条件。预期行为来自机制分析,复现时还需记录运行环境和原始输出,不能将预期当作已经测得的结果。

改变的条件 需要验证的行为
短分支延长一天 总工期仍可能保持九天
关键任务延长一天 无补救时总工期同步增加
两个分支共用一人 纸面工期可能无法执行

对照 1:短分支延长一天

总工期仍可能保持九天。观察时记录剩余时差是否已经用完。把这个条件与基准情形分开,有助于判断变化来自哪一层;若得到相反结果,应先核对前提,再修改实现。

对照 2:关键任务延长一天

无补救时总工期同步增加。观察时记录最长路径的累计长度。把这个条件与基准情形分开,有助于判断变化来自哪一层;若得到相反结果,应先核对前提,再修改实现。

对照 3:两个分支共用一人

纸面工期可能无法执行。观察时记录资源占用与依赖约束分别检查。把这个条件与基准情形分开,有助于判断变化来自哪一层;若得到相反结果,应先核对前提,再修改实现。

4. 适用条件与取舍

关键路径法假设给定工期和依赖可用,不自动处理需求变化或不确定性。压缩一个任务之前,要先确认它是否仍在当前关键路径上。

一次正常运行只覆盖了这组输入。继续扩展前,应把上面的异常对照保留下来,尤其关注“两个分支共用一人”这一分支。后续方案若改变了图中任意一处依赖,原来的判断就要重新验证,不能仅凭界面相似或返回值相同沿用结论。

同月延伸

参考资料

  1. MIT 算法课程资料
  2. Java SE 7 API 文档