目录
1. 为什么进度计划是一个图
每个项目计划都会做出两类陈述。第一类关于工作：这项任务需要九天。第二类关于顺序：这项任务要等那项完成后才能开始。每类写上一百条，你写下的就不是一份清单，而是一个图。任务是顶点，顺序约束是有向边，工期是权重。
这不是看待项目计划的一种视角，而是项目计划本身的样子，认识到这一点会改变你能提出的问题。任务清单能告诉你有多少工作量。只有图能告诉你项目需要多长时间，这是另一个数字，而且通常大得多，因为不能并行的工作只能依次完成。
其后果直接而又有些出人意料。项目的工期既不是各任务工期之和，也不是其中最大的那个，而是网络中最长路径的长度。正因如此，本文的项目包含七十二天的工作量，却在三十九天内完工。也正因如此，加人并不会自动有帮助，大家最担心的任务往往不是真正要紧的那个，而一个计划可能在内部自相矛盾，无论怎么努力都无法修复。
本文中的方法彼此相隔不到一年就被发明出来，都是在商业和军事压力下诞生的，发明者也都明白自己在解决一个图论问题。1959 年，Remington Rand 的 James Kelley 和 DuPont 的 Morgan Walker 发表了关键路径法，它是为安排化工厂的停车和重新开车而开发的，那里每闲置一天都要付出真金白银。同年，美国海军特别项目办公室发表了 PERT，它是为管理北极星导弹计划而建立的，那里的难题不是成本，而是一项前所未有的工作所带来的纯粹不确定性。两篇论文描述的都是活动网络，计算的也都是最长路径。
下面明确地构建一个小项目，十三项活动，工期真实，并在它上面回答每一个标准的进度问题：需要多久，什么是关键的，什么可以推迟，我们对日期有多大把握，加快进度要花多少钱，以及人手不够时会怎样。每个数字都经过计算，每个结果在写下之前都用第二种方法重新算过。
2. 活动、依赖关系与四种搭接类型
把项目画成图有两种惯例，两种都值得了解，因为较老的那种仍然出现在教科书里。
在单代号网络（activity-on-node，AoN）中，每项活动是一个顶点，每条箭头是一个依赖关系。现代软件用的就是这种，本文也始终使用这种。在双代号网络（activity-on-arrow，AoA）中，每项活动是一条箭头，顶点则是事件，也就是一组活动全部完成的时刻。AoA 是 PERT 和 CPM 最初的惯例，它有一个真正的缺点：表达某些依赖模式时必须插入虚活动，其工期为零，存在的唯一目的是让逻辑正确。AoN 不需要虚活动，这是它在实践中取代 AoA 的原因之一。
依赖关系本身并不总是最简单的那种。标准的搭接类型有四种：
- 完成到开始（FS）： A 完成后 B 才能开始。这是默认类型，也是本文唯一使用的类型。
- 开始到开始（SS）： A 开始后 B 才能开始。适用于并行推进的工作，例如比开发晚几天跟进的文档编写。
- 完成到完成（FF）： A 完成后 B 才能完成。
- 开始到完成（SF）： A 开始后 B 才能完成。很少见，通常说明计划其实想表达别的意思。
搭接关系还可以带有时间间隔（lag），即施加在约束上的延迟：混凝土需要养护三天才能在上面施工，所以这条边带有三天的间隔，尽管期间没有人在工作。时间间隔就是边的权重，本文的一切都可以原样处理它们。负的时间间隔称为提前量，允许一项活动在其紧前活动完成之前开始；这是合法的，但也是造出一个实际上无法执行的计划的常见方式。
有一条规则比这些都重要：图必须是无环的。如果 A 等 B，而 B 又等 A，就不存在任何顺序，第 4 节会准确展示排程工具遇到这种情况时是什么样子。
3. 贯穿全文的项目
示例是一款手机应用的发布：十三项活动，十六个依赖关系，工期以工作日计。它小到可以手工核对，又有足够的结构来展示所有要点，尤其是几条长度几乎相同的路径，而大多数有趣的现象正出现在那里。
要看结构，而不是标签。需求（A）开启了三条并行的工作流：经由数据库模式（C）的产品开发、设计工作（B）和营销工作（G）。开发工作流在后端 API（D）之后再次分成前端（E）、支付（F）和安全评审（I），然后汇合两次，先在集成测试（H），再在 Beta 测试（J）。营销工作直到提交（L）才重新汇入。
难点正集中在这些汇合点。一项有多个紧前活动的活动要等最慢的那个，而当工期不确定时，哪一个最慢并不能事先确定。第 9 节和第 11 节归根到底讲的都是汇合点上发生的事。
4. 这个计划可行吗？
在问项目需要多长时间之前，先问它到底能不能完成。只有当优先关系网络是一个有向无环图时，它才描述了一个有效的计划。如果依赖关系中含有环，就不存在任何能完成这些工作的顺序，这个计划不是延误了，而是根本不可能。
检验方法是拓扑排序，而 Kahn 算法是最值得了解的版本，因为它失败的方式非常有信息量。反复取出任意一个没有未完成紧前活动的活动，输出并删除它。在本项目上，这会得到顺序 A, B, C, D, E, F, G, H, I, J, K, L, M，全部十三项活动都在其中，所以计划是可排程的。
现在假设有人加了一个听起来很合理的依赖：数据库模式（C）要等集成测试（H）揭示出真实的查询模式后才能定稿。加上从 H 到 C 的边，再运行一次。Kahn 算法输出四项活动后就停止了：A、B、G 和 K，这是唯一没有被困在环里的工作。其余九项全部卡住，每一项都在等另一项。算法不只是失败了：它无法输出的那个集合正是死锁本身，而这恰恰是计划人员需要的诊断。
这在实践中很重要，因为真实的计划由许多人拼凑而成，每个人都加上局部看来合理的约束，却没有人把整张图装在脑子里。循环依赖很常见，而图能在线性时间内找到它们。
拓扑顺序的作用不只是验证计划。由于它保证每个紧前活动都排在其后续活动之前，整个进度计划可以在对活动的一遍扫描中算完，无需迭代，也无需搜索。这就是关键路径法在 1959 年的硬件上就已切实可用的原因，也是它在有十万项任务的项目上仍能瞬间完成的原因。
5. 关键路径：在图上走两遍
关键路径法为每项活动计算四个数字，其余一切都由它们推导而来。
所谓正推，就是按拓扑顺序遍历活动，计算每项活动最早能在何时发生。一项活动的最早开始时间，是其所有紧前活动最早完成时间中的最大值，而它的最早完成时间就是这个值加上它的工期。需求在第 0 天开始、第 4 天完成。数据库模式随后在第 4 天开始、第 7 天完成。后端 API 在第 7 天开始、第 16 天完成。前端开发既要等 API（第 16 天完成），也要等 UI 设计（第 14 天完成），所以它在第 16 天开始，而不是第 14 天。走完一遍后，最大的最早完成时间就是项目工期：39 个工作日。
所谓逆推，就是按相反顺序遍历，计算每项活动在不推迟结束日期的前提下最晚能在何时发生。一项活动的最迟完成时间，是其所有后续活动最迟开始时间中的最小值。发布必须在第 39 天完成，所以必须在第 38 天开始；提交必须在第 38 天前完成，所以在第 36 天开始；依此类推，一直回到起点。
两者之间的差距就是总浮动时间，也就是一项活动在项目结束日期被推迟之前可以拖延的量。浮动时间为零的活动构成了关键路径。
关键路径是 A → C → D → E → H → J → L → M，它的长度恰好是正推得出的 39 天。这不是巧合，而是一个定理：项目工期等于最长路径的长度，而浮动时间为零的活动恰好就是位于某条最长路径上的那些活动。当两条路径并列最长时，就像第 10 节中那样，两条都是关键路径。
由此得出的两点值得明确说出来。第一，任何关键活动推迟一天，项目就推迟一天，没有例外，也没有缓冲。第二，加快非关键活动完全没有作用，结束日期纹丝不动。营销网站即使一天就做完，发布仍然在第 39 天。花在关键路径之外的精力买到的是安全余量，而不是时间。
你可以在关键路径法可视化工具中，在自己画的网络上逐步运行这两遍计算。值得注意 CPM 在数学上是什么。在一般的图中寻找最长路径是 NP 难的，因为可以用它来解决哈密顿路径问题。而在有向无环图上，它变得很容易，与活动数和依赖数呈线性关系，正是因为存在拓扑顺序。CPM 的全部实用价值都建立在第 4 节所检验的无环性之上。
6. 浮动时间，以及它真正属于谁
浮动时间是进度计划中最有用的数字，也是最常被误用的数字。混乱源于它有两种。
总浮动时间是一项活动在不推迟项目结束日期的前提下可以延迟的时间。自由浮动时间是它在不推迟任何后续活动最早开始时间的前提下可以延迟的时间。在本项目中，安全评审（I）有 7 天总浮动时间和 7 天自由浮动时间，因为它所衔接的 Beta 测试反正也要等集成测试。内容（G）有 22 天总浮动时间，但自由浮动时间为零：哪怕只推迟一天，营销网站就会晚一天开始。
这个差别正是陷阱所在。内容和营销网站各显示 22 天总浮动时间，一个逐行阅读进度表的项目经理会看到 44 天的表面余量。实际只有 22 天。这些浮动时间属于路径 A → G → K → L → M，这条路径在 39 天的项目中只占 17 天，两项活动共享它。
模型让这一点变得具体。把 22 天全部花在内容上，项目仍在第 39 天完成，但营销网站的总浮动时间从 22 天降到零：它变成了关键活动。再推迟一天，项目就移到第 40 天。没有任何超支，没有哪项任务单独出了问题，日期却推迟了，因为余量早已在上游被消耗掉。
实用的规则是：总浮动时间是路径的属性，自由浮动时间是活动的属性。自由浮动时间是其他人无法占用的部分，也是应该作为真正的回旋余地交给团队的数字。在本项目中只有四项活动有自由浮动时间：B 有 2 天，F 有 1 天，I 有 7 天，K 有 22 天。
7. 关键路径并不总是关键的
关键路径会诱人得出一个舒服的结论：盯住这八项活动，项目就在掌控之中。本项目的路径结构说明了为什么这还不够。
一共有五条路径。关键路径长 39 天。下一条长 38 天，经过支付而不是前端。第三条长 37 天，经过 UI 设计而不是数据库和 API。这两条都不是关键路径，但它们的浮动时间只有一天和两天，比大多数估计的舍入误差还小。
从业者把这称为近关键路径问题，它有一个尖锐的后果：一个计划可能有好几条实际上都是关键的路径，只盯着官方那条的项目经理，会被一条看似安全的路径上的延误打个措手不及。十天的设计任务只有两天浮动时间，这不是余量，而是噪声。
有用的做法是按浮动时间给路径排序，而不是把它们分成关键和非关键两类。在本项目中，39、38、37、32、17 这个排序说出了红色高亮说不出的事：五条路径中有三条需要积极管理，两条不需要。第 9 节会给出每条路径最终决定日期的具体频率。
8. PERT：给日期加上概率
CPM 假设每个工期都是已知的。可谁的工期都不是已知的。PERT 于 1959 年为北极星计划开发，它的做法是对每项活动要求三个估计而不是一个：乐观时间 a、最可能时间 m和悲观时间 b。
由此为每项活动计算期望工期和方差：
te = (a + 4m + b) / 6 以及 σ² = ((b − a) / 6)²
这些权重来自用 beta 分布近似每项活动的工期，这种分布足够灵活，既可以偏斜，两端又都有界，而正态分布则会允许负的工期。这些公式都是近似，之所以被选用，部分原因是它们在 1959 年可以手工计算。
沿关键路径求和，得到项目的期望工期为 39 天，总方差为 3.778，因此标准差为 1.944 天。接着援引中心极限定理：几个独立的活动工期之和近似服从正态分布，即使单个活动并不服从，这样就可以直接从曲线上读出概率。
这个结果远比一个日期有用。40 天内完工的概率为 69.7%；41 天内为 84.8%；42 天内为 93.9%。反过来说：承诺 39 天就是在承诺抛硬币，买三天的应急时间能把把握提高到约 94%，第四天则能提高到 98%。
借助 PERT 可视化工具，可以交互方式完成这一计算，包括任意目标日期的完工概率。这种视角的转换才是 PERT 真正的贡献。只给出单一日期的进度计划会引出“我们能按时完成吗？”这个问题，而它没有诚实的答案。给出一个分布的进度计划则会引出“你想要多大的把握，愿意为此付出多少？”，这个问题有答案。
9. 合并偏差：PERT 为什么偏乐观
PERT 有一个缺陷，它在发表后几年内就被发现，却至今仍被习惯性地忽视。问题在于，PERT 计算的是关键路径的分布，然后把它当作整个项目的分布。这两者并不是一回事。
项目并不等待关键路径。它等待的是那一次实际上最长的路径。当几条路径汇合到一项活动时，这项活动要等最慢的那条到达才能开始，而最大值的期望大于期望的最大值。这就是詹森不等式，在项目调度中它被称为合并偏差。Van Slyke 在 1963 年用蒙特卡洛模拟证明了它，MacCrimmon 和 Ryavec 在 1964 年分析了误差的大小。
为了测量它，本项目的每项活动都从均值恰好等于其 PERT 期望工期的 beta 分布中抽样 200,000 次，因此结果中的任何差异都只来自合并偏差，而不是另一套假设。模拟得到的平均工期是 39.34 天，而 PERT 给出的是 39.00。更有用的是，39 天内完工的概率是 43.8%，而不是 PERT 所暗示的 50%。
路径统计说明了这种差距从何而来。在所有模拟中，名义关键路径只在 64.0% 的运行中是最长的。支付路径在 26.1% 的情况下胜出，设计路径则为 9.9%。每三个项目中就有一个会因为关键路径分析从未提及的原因而延误。
三分之一天的偏差听起来可以忽略，在这个项目上也确实如此。但一般情况下并非如此，而且它恰恰在描述大型项目群的那些情形中增大：许多长度相近的并行路径、许多汇合点和很高的方差。一个有二十条几乎等长的路径汇合到同一个里程碑的进度计划，偏差可能达到数周。
由此得出两个实用的对策。第一，如果网络的并行程度很高，就对它进行模拟，而不是沿着一条路径传播方差；计算只需几行代码，几秒钟就能完成。第二，报一个百分位数，而不是均值。本项目的 P80 是 41.1 天，P90 是 42.0。这些才是团队可以承诺的数字。均值是一个一半时间都会错过的数字，把合并偏差算进去之后，错过的时间还略多于一半。
10. 赶工：买时间就是一个最小割
假设 39 天太长了。许多活动可以花钱缩短：加人、加班、换一个更快的供应商。在进度管理中这叫作赶工（crashing），每项活动会多出两个数字：它最多能缩短多少天，以及每缩短一天的成本，即它的成本斜率。
朴素的做法是压缩最便宜的关键活动。这只奏效一次。前端开发在关键路径上的斜率最低，每天 $350，所以缩短它能以 $350 把项目从 39 天缩到 38 天。接下来是数据库模式，$400，把项目缩到 37 天。
然后朴素规则就失效了。在 37 天时，有两条路径同时是关键路径：原来那条和支付路径，两者现在都是 37 天。再次缩短前端开发毫无收益，因为支付仍然保持原长，项目仍然需要 37 天。要想省下一天，你必须同时缩短每一条关键路径。
结构是这样的。一组活动如果缩短后能让每条关键路径都变短，那么它就是一个在关键子网络内与从项目开始到结束的每条路径都相交的集合。这正是 s-t 割的定义。给每项活动赋予等于其每日成本的容量，买一天的最便宜方式就是这个网络的最小割。根据最大流最小割定理，它可以在多项式时间内求出，Fulkerson 和 Kelley 都在 1961 年发表了这一观察。
如果你对流的论证不熟悉，值得先读一读最大流最小割定理，因为赶工是它在网络领域之外最干净的应用之一。由于活动是顶点而不是边，每项活动都被拆成一个入口副本和一个出口副本，两者之间用一条带有其成本斜率的弧相连，而真实的依赖关系则获得无穷大的容量。这样，最小割就必须由活动组成，而活动正是你真正能买的东西。
在本项目上运行这一方法，得到第三步：从 37 天缩到 36 天需要 $650，并且必须同时压缩前端开发和支付。单独压缩其中任何一个都省不下一天，所以任何“选最便宜的关键任务”式的规则都永远找不到这一对。集成测试单独压缩确实有效，因为它同时位于两条关键路径上，但它要 $800，而这一对只要 $650。
一直推进到极限，就得到完整的时间-成本曲线：27 天是可达到的最短工期，总赶工成本为 $11,950。这条曲线是凸的，也就是说每多省一天的成本都不低于前一天，这是这种构造的一般性质，也是检查别人交给你的任何赶工分析的有用手段。
真正的交付物是这条曲线，而不是终点。它把关于团队能否“加快速度”的争论变成了一张价目表：三天 $1,400，六天 $3,650，十二天 $11,950。其中哪一个值得付钱是业务问题，但现在它是一个有数字的问题。
11. 资源：理论不再够用的地方
到目前为止的一切都假设，两项活动只要可以并行就会并行。这等于假设人手无限，而没有哪个项目的人手是无限的。决定哪些人上哪些班，而不是哪些任务何时进行，是一个相关的排班问题，在员工排班一文中有完整的求解。
给每项活动一个人员需求，再看一遍 CPM 进度计划。如果一切都尽早开始，本项目的需求峰值会达到七个人，从第九天持续到第十四天，那时后端 API、UI 设计和营销网站同时在进行。如果团队只有五个人，这个进度计划就是虚构的。
加上资源限制，就把优先关系图变成了资源受限项目调度问题（RCPSP），而难度的变化不是渐进的。CPM 是线性时间。RCPSP 是 NP 难的，由 Blazewicz、Lenstra 和 Rinnooy Kan 于 1983 年证明，而且它在实践中和理论上一样困难：标准基准库 PSPLIB 中有 60 项活动的实例多年来一直未能求解。
这些数字值得细细体会。有五个人时，项目仍然在 39 天内完工：七人的峰值只是排程造成的假象，把工作挪进浮动时间就能完全消化掉。只有四个人时，最优解是 49 天，超期 26%，而这在网络分析中完全看不出来。这两个数字都通过对所有主动进度计划的穷举分支定界得到验证，而这只因为项目只有十三项活动才可行。
借助资源受限调度可视化工具，你可以设定一个容量，看着进度计划被拉长。由于精确解无法扩展，实践中使用的是优先规则：反复安排按某条规则排名最高的可安排活动。规则的选择比看起来更重要。容量为四时，最小总浮动时间得到 49 天，在这里恰好是最优的，而最早的最迟开始时间、最长工期优先和后继最多优先都得到 53 天。同一个项目，同一个约束，仅仅因为一个大多数工具默默替你做出的建模选择，结果就相差 8%。
更深层的一点是，在资源约束下关键路径失去了意义。两项彼此之间没有任何依赖的活动仍可能无法同时进行，所以真正决定结束日期的链条，可能包含仅仅因为共用一个人而连在一起的活动对。经典的浮动时间数值不再能描述什么可以推迟。
12. 关键链，简述
这一观察正是关键链项目管理的出发点，它由 Eliyahu Goldratt 在 1997 年提出。关键链是同时考虑优先关系和资源冲突的最长活动序列，在人手紧张时，它才是应该盯住的对象。
它的第二个想法关于安全时间放在哪里。单项估计通常都留有余量，而这些余量无论如何都会被用掉，要么是因为工作会膨胀到填满可用时间，要么是因为一个宽裕的开始日期被白白占用。关键链把余量从各项活动中剥离出来，汇集到明确的缓冲中：链尾的项目缓冲，以及非关键路径汇入关键链处的汇入缓冲。汇集在统计上是合理的，不过理由与合并偏差不同：独立工期之和的标准差按其数量的平方根增长，所以一个共享缓冲可以比它取代的各个余量加起来更小，却提供同样的保护。
这种方法确实存在争议。Herroelen 和 Leus 等人认为，它在排程上的主张比宣传的要弱，而诸如“链长的一半”之类的缓冲大小规则没有分析依据。汇集缓冲的洞见是站得住的；围绕它的框架是一种管理方法而不是定理，值得把两者区分开来。
13. 什么容易，什么困难
项目调度有一条异常清晰的复杂度边界，知道它在哪里，就知道一个工具能兑现哪些承诺。
容易，指多项式时间，在任何现实规模下都能瞬间完成。检测环并生成拓扑顺序。正推和逆推，以及由此得到的项目工期、关键路径和每个浮动时间值。按浮动时间列举重要的路径。为赶工一天求最小割，并通过重复求解得到整条时间-成本曲线。对工期分布做蒙特卡洛模拟。所有这些都是线性或近似线性的，一个有十万项活动的项目也不在话下。
困难，指 NP 难，预计不存在多项式算法。几乎所有变体下的资源受限调度：固定容量、多种资源类型、允许或不允许中断。资源平衡，它追求最平滑的资源曲线而不是最短的进度。每项活动只有离散选项而不是连续斜率的时间-成本权衡，这会失去流的表述。列举全部路径，其数量可能随活动数呈指数增长。
这个规律几乎可以当作经验法则：只在时间上求一个最优进度是容易的，而加上一个共享的有限资源就会让它变难。困难清单中的两个例外恰恰印证而不是打破了这条规则，因为它们都不是在求单一最优解：路径列举要求所有答案，离散权衡则要求在每项活动上从菜单中做选择。时间约束构成偏序，而偏序正是有向无环图擅长处理的。共享资源会在彼此没有任何依赖的活动之间产生约束，于是让一切都可解的无环结构不再能描述这个问题。
这就是为什么排程软件给出精确的关键路径和近似的资源平衡计划，而且通常不加说明。前者是定理；后者是质量无人报告的启发式方法。这只是一个大得多的领域的一角：运筹学涵盖了这张清单中较难的一半所需的优化方法。
14. 建模错误以及如何避免
五种错误造成了大多数糟糕的进度计划，而且没有一种与估计失准有关。
把浮动时间当作自己的储备。总浮动时间沿路径共享。在同一条路径上，两个团队各自被告知有三周余量，结果会一共用掉六周，然后对日期的变动感到意外。向团队报告自由浮动时间，把总浮动时间留作计划用的数字。
只盯着关键路径。只有两天浮动时间的路径并不安全，它几乎是关键的，而在本项目中，名义关键路径只在三分之二的运行中决定结果。按浮动时间给路径排序，管理所有浮动时间只差几天就归零的路径。
把均值当作日期报出去。期望工期在考虑合并偏差之前就大致是抛硬币，考虑之后还要更差一点。如果一个日期要写进合同，它应该是一个百分位数，而且要说明是哪一个。
假设相互独立。 PERT 的方差求和和第 9 节的模拟都假设各活动工期相互独立。它们通常并不独立：同一个乐观的估计者给出了其中好几个，同一个团队执行其中好几个，一个糟糕的供应商会同时影响好几个。相关性会让总工期的方差远超两种方法给出的数值，所以要把离散程度当作下限，而不是估计值。
按人手无限来做计划。不考虑资源限制算出的 CPM 日期只是一个下界，而不是计划。发布日期之前先检查资源曲线；在本项目中，检查与不检查之间相差十天。
第六种值得一提，因为它是看不见的：一个并不真实的依赖。计划会不断累积为图省心而加上的约束，这些先后顺序反映的是团队碰巧怎样组织，而不是任何技术上的需要。加一条边只可能让最长路径变长或保持不变，绝不会让它变短，所以每个不必要的依赖都是对进度计划的一次单向押注。逐条审查关键路径上的边，问问每一条是不是真正的约束，往往是现成的最便宜的压缩手段，而且与赶工不同，它不花一分钱。
15. 常见问题
图论在项目管理中是如何应用的？
+
项目计划是一个有向无环图：活动是顶点，依赖关系是有向边，工期是权重。一旦这样写出来，标准问题就变成了标准算法。拓扑排序检查计划到底能否执行。最长路径计算给出项目工期和关键路径。正推与逆推之间的差距给出浮动时间。最小割给出缩短进度的最便宜方式。加上资源限制，它就变成了资源受限项目调度问题，而这是 NP 难的。
关键路径究竟是什么？
+
从项目开始到结束的最长路径，按工期而不是按活动数量来衡量。它的长度就是项目工期，因为其上的每项活动都必须依次进行，没有什么能压缩这一点。等价地说，它是总浮动时间为零的活动集合，这正是正推和逆推所计算的。在本文的项目中，它是 A-C-D-E-H-J-L-M，共 39 个工作日。其上任何活动延误，整个项目就延误同样的时间，而加快其外的任何活动，结束日期都不会有任何变化。
总浮动时间和自由浮动时间有什么区别？
+
总浮动时间是一项活动在项目结束日期变动之前可以拖延的时间。自由浮动时间是它在任何后续活动必须推迟开始之前可以拖延的时间。区别之所以重要，是因为总浮动时间沿路径共享，而不属于某一项活动。在本项目中，内容和营销网站各显示 22 天总浮动时间，但它们的路径总共只有一份 22 天。把它全部花在内容上，营销网站的浮动时间立刻降为零。自由浮动时间是其他人无法占用的部分，所以它才是应该交给团队的数字。
CPM 和 PERT 有什么区别？
+
两者都在同一类网络中计算最长路径，也都在 1959 年发表。CPM 来自 DuPont 和 Remington Rand 的 Kelley 与 Walker，它假设每个工期都是一个已知的确定数字，并增加了成本维度，赶工就由此而来。PERT 来自美国海军的北极星计划，它假设工期不确定，要求每项活动给出乐观、最可能和悲观三个估计，再推导出期望工期和方差，从而可以用概率来表述完工日期。在现代工具中两者已经融合，区别主要是历史性的。
PERT 为什么偏乐观？什么是合并偏差？
+
因为 PERT 计算的是关键路径的分布，然后把它当作项目的分布。实际上项目要等那一次最长的路径，而最大值的期望大于期望的最大值，这就是詹森不等式。对本项目模拟 200,000 次，得到的均值是 39.34 天，而 PERT 给出的是 39.00 天，39 天内完工的概率是 43.8%，而不是 PERT 所暗示的 50%。名义关键路径只在 64.0% 的运行中是最长的。偏差随着长度相近的并行路径数量增加而增大。
为什么压缩进度计划是一个最小割问题？
+
因为要把项目缩短一天，就必须把每条关键路径都缩短一天，所以你付钱压缩的活动集合必须与所有关键路径相交。与从开始到结束的每条路径都相交的集合就是一个 s-t 割，如果每项活动的弧上带有它的每日成本，那么最便宜的这种集合就是最小割，可以用最大流最小割在多项式时间内算出。Fulkerson 和 Kelley 都在 1961 年发表了这一点。它之所以重要，是因为答案往往不是最便宜的那项活动：在本项目中，第三天要花 $650，而且必须同时压缩前端开发和支付。
为什么资源限制会让调度难这么多？
+
因为优先约束构成一个偏序，有向无环图可以在线性时间内处理它，而共享资源会在彼此完全没有依赖的活动之间产生约束。这破坏了整个方法所依赖的结构。资源受限项目调度问题是 NP 难的，由 Blazewicz、Lenstra 和 Rinnooy Kan 于 1983 年证明。在本项目中，不受约束时的答案是 39 天，需求峰值为七个人；四个人时真正的最优解是 49 天，而且在资源限制下，关键路径不再能描述什么可以推迟。
我应该承诺期望工期，还是一个百分位数？
+
承诺一个百分位数，并说明是哪一个。期望工期按构造大致就是抛硬币，合并偏差还会让它更差一点：在本项目中，在期望的 39 天内完工的概率是 43.8%。P80 是 41.1 天，P90 是 42.0 天，所以大约两天的应急时间就能把一个承诺从五五开变成比较有把握。报一个百分位数还会改变讨论的方向：不再争论团队能不能做到，这个问题没有诚实的答案；而是讨论想要多大的把握以及要付出什么代价，这个问题有答案。
16. 参考文献
本文所用方法背后的论文，按时间顺序排列。
- Clark, W. (1922). The Gantt Chart: A Working Tool of Management. Ronald Press.
- Kelley, J. E. and Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
- Malcolm, D. G., Roseboom, J. H., Clark, C. E. and Fazar, W. (1959). “Application of a technique for research and development program evaluation.” Operations Research, 7(5), 646–669.
- Fulkerson, D. R. (1961). “A network flow computation for project cost curves.” Management Science, 7(2), 167–178.
- Kelley, J. E. (1961). “Critical-path planning and scheduling: mathematical basis.” Operations Research, 9(3), 296–320.
- Ford, L. R. and Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
- Van Slyke, R. M. (1963). “Monte Carlo methods and the PERT problem.” Operations Research, 11(5), 839–860.
- MacCrimmon, K. R. and Ryavec, C. A. (1964). “An analytical study of the PERT assumptions.” Operations Research, 12(1), 16–37.
- Klingel, A. R. (1966). “Bias in PERT project completion time calculations for a real network.” Management Science, 13(4), B194–B201.
- Wiest, J. D. (1967). “A heuristic model for scheduling large projects with limited resources.” Management Science, 13(6), B359–B377.
- Elmaghraby, S. E. (1977). Activity Networks: Project Planning and Control by Network Models. Wiley.
- Blazewicz, J., Lenstra, J. K. and Rinnooy Kan, A. H. G. (1983). “Scheduling subject to resource constraints: classification and complexity.” Discrete Applied Mathematics, 5(1), 11–24.
- Kolisch, R. and Sprecher, A. (1997). “PSPLIB: a project scheduling problem library.” European Journal of Operational Research, 96(1), 205–216.
- Goldratt, E. M. (1997). Critical Chain. North River Press.
- Brucker, P., Drexl, A., Möhring, R., Neumann, K. and Pesch, E. (1999). “Resource-constrained project scheduling: notation, classification, models, and methods.” European Journal of Operational Research, 112(1), 3–41.
- Herroelen, W. and Leus, R. (2001). “On the merits and pitfalls of critical chain scheduling.” Journal of Operations Management, 19(5), 559–577.
- Demeulemeester, E. and Herroelen, W. (2002). Project Scheduling: A Research Handbook. Kluwer Academic Publishers.
- Herroelen, W. and Leus, R. (2005). “Project scheduling under uncertainty: survey and research potentials.” European Journal of Operational Research, 165(2), 289–306.
- Kolisch, R. and Hartmann, S. (2006). “Experimental investigation of heuristics for resource-constrained project scheduling: an update.” European Journal of Operational Research, 174(1), 23–37.
- Hartmann, S. and Briskorn, D. (2010). “A survey of variants and extensions of the resource-constrained project scheduling problem.” European Journal of Operational Research, 207(1), 1–14.
- Trietsch, D. and Baker, K. R. (2012). “PERT 21: fitting PERT/CPM for use in the 21st century.” International Journal of Project Management, 30(4), 490–502.