排程是一组不等式
项目活动未必都能同时开始。由 指向 的箭头表示 完成后 才能开始。工期和先后关系共同决定完成时间的下界;排程计算也应给出达到该下界的可行方案。
假设图有限、非空且有向无环,每个顶点代表一项活动,工期 已确定,资源无限,没有释放日期,项目从时间零开始。活动不可拆分或加速;资源冲突及不确定性不在本模型内。
定义 8.2.1
(可行排程与完成时间)
排程为每项活动 指定开始时间 。若每条箭头 均有 ,排程便是可行的。其完成时间是 。有向路径的长度是路径上各活动工期之和。
正向及反向计算
定义 8.2.2
(最早开始、最迟开始与总时差)
按拓扑次序,对源点设 ,其他顶点设 ;令 。按逆拓扑次序,对汇点设 ,其他顶点设 。活动 的总时差是 。总时差为零的活动称为关键活动。
定理 8.2.3
(正向计算给出最短完成时间)
每个可行排程对所有 都有 ,而排程 可行。因此 是最短完成时间,并等于有向路径长度的最大值。
证明
(沿拓扑次序归纳)
按拓扑次序归纳,每个可行排程均有 :源点有 ;若 的每个前驱 都已成立,则对每个 有 ,故 。排程 可行,因为由定义中的最大值,每条箭头 都有 。所以每个可行完成时间都至少是 ,而 达到它。
同一归纳也说明 是恰在 之前结束的有向路径的最大长度:递推把 接到在 之前结束的最长路径之后,再对前驱取最大值。因此 是以 结尾的路径的最大长度,而 是所有有向路径的最大长度。
概念视角代数
关键路径作为对偶证书
最短完成时间是一个线性规划:在每条箭头 上 、对每个 有 及 的约束下,最小化 。对有向路径 ,把 、路径上的箭头约束及 相加,开始时间逐项抵消,剩下 。这些单位权重构成一个可行对偶解,其值为路径长度。正向计算给出原问题最优解,最长路径给出对偶最优解,两者的共同值 就是该问题的强对偶性。
要求在保持 时个别活动最迟可何时开始,反向计算把同一论证倒过来进行。
命题 8.2.4
(最迟开始时间可以达到)
每个在 前完成的可行排程,对所有 都有 。向量 本身是在 前完成的可行排程,且 ,所以每个总时差都非负。
证明
(从汇点开始反向归纳)
取一个在 前完成的可行排程。汇点必须在 前完成,故 。若 的每个后继 都有 ,则对每个这样的 有 ,故 。
其次,反向归纳给出 :在汇点,;否则对每个后继 有 ,取最小值即得 。于是 。由定义,每条箭头 都有 ,所以 可行;而每条后继链都终止于一个满足 的汇点,所以 在 前完成。因此每个 都是真正可达的最迟开始时间,而不只是一个上界。
命题 8.2.5
(关键活动恰好是最长路径上的活动)
一项活动的总时差为零,当且仅当它位于一条长度为 的有向路径上。
证明
(把最长前段与最长后段接起来)
由两次计算, 是以 结尾的路径的最大长度, 是从 开始的路径的最大长度,两者都计入 。从源点到 的路径再接上从 到汇点的路径,只计一次 ,长度至多为 ;两段最长路径达到此值,而在有向无环图中它们只共用 ,所以合起来是一条路径。若 ,这就是经过 、长度为 的路径。反过来,若 位于长度为 的路径 上,则 到 为止(含 )的部分长度至多为 ,从 起的部分长度至多为 ;两部分只重叠 ,故 ,迫使 。
证明透视
零时差活动与其路径
证明的基础是把每次计算读作最长路径的值:正向计算度量以 结尾的最长前段,反向计算度量从 开始的最长后段。唯一的步骤是把两者相加并只计一次 ,由此看出总时差恰好等于 减去经过 的最长路径所差的数量。无环性保证两段能接成真正的路径,因为在有向无环图中,经过同一顶点的前段和后段不可能再共用其他顶点。两个方向随即同时成立:差额为零即有经过 的最长路径,而经过 的最长路径即表示差额为零。没有任何条件迫使最长路径唯一。
例子
例题 8.2.6
(只有一条关键路径的五项活动)
活动 的工期依次为 ,箭头为 、、、、。正向计算得到 、、、,完成时间 。由 反推得到 、、、,按活动次序时差为 。
路径 的工期为 ,证明下界;所有活动在最早时间开始便达到它。全最迟方案中 可于时间一开始而不延迟完成,全最迟方案是可行的,但在各自时差范围内独立选择活动延误,所得方案未必可行。
下面的互动图可让你修改工期,读出 E、L、时差及最长路径,再用自己给定的开始时间逐条检查先后约束,包括各自都在时差范围内的延误。
反例模式
时差不是互不影响的延误额度
考虑 ,另有独立活动 ,工期依次为 。项目需时四。 的最早开始为 ,最迟开始为 ,各有时差二。二者都比最早时间延迟二而于 开始是可行的;但若只把 延迟二, 却仍在最早时间一开始,便违反 。个别时差上界不能消除先后约束。
以下两个例子展示边界情形:最长路径并列,以及工期为零的活动。
例题 8.2.7
(共用一项活动的两条最长路径)
在五项活动的网络中,把 的工期改为三。则 、、,。反向得到 、、、、。时差为 ,而 与 的长度都是 。关键活动 组成两条最长路径,而不是一条。
常见错误
(只缩短一条关键路径便期望项目缩短)
有两条最长路径时,只缩短其中一条路径上的活动,项目不会缩短。在并列的网络中,把 从三缩短为二,得到 ;完成时间仍是 ,因为 仍是长度十的路径。只有使每条最长路径都缩短的改动,才可能降低 。
例题 8.2.8
(工期为零的里程碑)
设 的工期为 ,里程碑 的工期为 , 的工期为 ,箭头为 、、。正向得到 、、,。反向得到 、、、。 的时差为 。最长路径 的长度为 。里程碑虽不耗时,却是关键活动:它记录了 必须等待的同步点。
限制
若有环,拓扑算法不适用;环上所有工期均为正时,不等式相互矛盾。零工期的环可能满足不等式,但已被无环假设排除。人力、机器、随机工期及非最短完成时间的期限均需其他模型。关键路径是确定性、仅含先后约束问题的证书,不是真实项目准时完成的保证。
练习
快速检查
(验证第一个例子的全最迟方案满足每条先后约束。)
解答 · 答案
最迟开始为 。五条箭头上的前驱完成时间依次为 ,均不晚于后继开始。
快速检查
(在第一个例子中,仅把 的工期从二改为四,求新的最早完成时间和一条最长路径。)
解答 · 答案
均于四开始, 于八开始,完成时间是十一; 长 。
快速检查
(在 和 例子中,求全最迟开始时间并验证可行性。)
解答 · 答案
。 在三时完成,正好是 开始; 均在四时完成。
快速检查
(为什么两项工期严格为正、相互先于对方的活动不能满足先后不等式?)
解答 · 答案
若 且 ,相加 和 得 ,矛盾。