排程是一組不等式
項目活動未必都能同時開始。由 指向 的箭頭表示 完成後 才能開始。工期和先後關係共同決定完成時間的下界;排程計算也應給出達到該下界的可行方案。
假設圖有限、非空且有向無環,每個頂點代表一項活動,工期 已確定,資源無限,沒有釋出日期,項目由時間零開始。活動不可拆分或加速;資源衝突及不確定性不在本模型內。
定義 8.2.1
(可行排程與完成時間)
排程為每項活動 指定開始時間 。若每條箭頭 均有 ,排程便是可行的。其完成時間是 。有向路徑的長度是路徑上各活動工期之和。
正向及反向計算
定義 8.2.2
(最早開始、最遲開始與總浮時)
按拓撲次序,對源點設 ,其他頂點設 ;令 。按逆拓撲次序,對匯點設 ,其他頂點設 。活動 的總浮時是 。總浮時為零的活動稱為關鍵活動。
定理 8.2.3
(正向計算給出最短完成時間)
每個可行排程對所有 都有 ,而排程 可行。因此 是最短完成時間,並等於有向路徑長度的最大值。
證明
(沿拓撲次序歸納)
按拓撲次序歸納,每個可行排程均有 :源點有 ;若 的每個前驅 都已成立,則對每個 有 ,故 。排程 可行,因為由定義中的最大值,每條箭頭 都有 。所以每個可行完成時間都至少是 ,而 達到它。
同一歸納亦說明 是恰在 之前結束的有向路徑的最大長度:遞推把 接到在 之前結束的最長路徑之後,再對前驅取最大值。因此 是以 結尾的路徑的最大長度,而 是所有有向路徑的最大長度。
概念視角代數
關鍵路徑作為對偶證書
最短完成時間是一個線性規劃:在每條箭頭 上 、對每個 有 及 的約束下,最小化 。對有向路徑 ,把 、路徑上的箭頭約束及 相加,開始時間逐項抵消,剩下 。這些單位權重構成一個可行對偶解,其值為路徑長度。正向計算給出原問題最優解,最長路徑給出對偶最優解,兩者的共同值 就是此問題的強對偶性。
要求在保持 時個別活動最遲可何時開始,反向計算把同一論證倒過來進行。
命題 8.2.4
(最遲開始時間可以達到)
每個在 前完成的可行排程,對所有 都有 。向量 本身是在 前完成的可行排程,且 ,所以每個總浮時都非負。
證明
(由匯點開始反向歸納)
取一個在 前完成的可行排程。匯點必須在 前完成,故 。若 的每個後繼 都有 ,則對每個這樣的 有 ,故 。
其次,反向歸納給出 :在匯點,;否則對每個後繼 有 ,取最小值即得 。於是 。由定義,每條箭頭 都有 ,所以 可行;而每條後繼鏈都終於一個滿足 的匯點,所以 在 前完成。因此每個 都是真正可達的最遲開始時間,而不只是一個上界。
命題 8.2.5
(關鍵活動恰好是最長路徑上的活動)
一項活動的總浮時為零,當且僅當它位於一條長度為 的有向路徑上。
證明
(把最長前段與最長後段接起來)
由兩次計算, 是以 結尾的路徑的最大長度, 是由 開始的路徑的最大長度,兩者都計入 。由源點到 的路徑再接上由 到匯點的路徑,只計一次 ,長度至多為 ;兩段最長路徑達到此值,而在有向無環圖中它們只共用 ,所以合起來是一條路徑。若 ,這就是經過 、長度為 的路徑。反過來,若 位於長度為 的路徑 上,則 到 為止(含 )的部分長度至多為 ,由 起的部分長度至多為 ;兩部分只重疊 ,故 ,迫使 。
證明透視
零浮時活動與其路徑
證明的基礎是把每次計算讀作最長路徑的值:正向計算量度以 結尾的最長前段,反向計算量度由 開始的最長後段。唯一的步驟是把兩者相加並只計一次 ,由此看出總浮時恰好等於 減去經過 的最長路徑所差的數量。無環性保證兩段能接成真正的路徑,因為在有向無環圖中,經過同一頂點的前段和後段不可能再共用其他頂點。兩個方向隨即同時成立:差額為零即有經過 的最長路徑,而經過 的最長路徑即表示差額為零。沒有任何條件迫使最長路徑唯一。
例子
例題 8.2.6
(只有一條關鍵路徑的五項活動)
活動 的工期依次為 ,箭頭為 、、、、。正向計算得 、、、,完成時間 。由 反推得 、、、,依活動次序浮時為 。
路徑 的工期為 ,證明下界;所有活動在最早時間開始便達到它。全最遲方案中 可於時間一開始而不延遲完成,全最遲方案是可行的,但在各自浮時範圍內獨立選擇活動延誤,所得方案未必可行。
下面的互動圖可讓你修改工期,讀出 E、L、浮時及最長路徑,再用自己提出的開始時間逐條檢查先後約束,包括各自都在浮時範圍內的延誤。
浮時按活動逐一達到,不能各自獨立動用
修改小型先後關係網絡的工期,讀出最早開始 E、最遲開始 L、浮時 L − E 及最長路徑;再為每項活動提出開始時間,檢查每條約束 t_j ≥ t_i + d_i。
工期 d(0 至 9)
提出的開始時間 t(0 至 60)
每個方框列出活動、工期、E、L、浮時及提出的開始時間 t。粗實線箭頭連接最長路徑上相鄰的活動,細虛線箭頭則不在關鍵路徑上;箭頭旁的 × 表示該約束被違反。下方表格提供相同資料。
| 活動 | d | 最早開始 E | 最遲開始 L | 浮時 L − E | 零浮時 | 提出的開始時間 t | t 在 [E, L] 內 |
|---|---|---|---|---|---|---|---|
| A | 3 | 0 | 0 | 0 | 是 | 0 | 是 |
| B | 2 | 0 | 1 | 1 | 否 | 0 | 是 |
| C | 4 | 3 | 3 | 0 | 是 | 3 | 是 |
| D | 2 | 2 | 5 | 3 | 否 | 2 | 是 |
| E | 3 | 7 | 7 | 0 | 是 | 7 | 是 |
| 箭頭 i → j | 關鍵箭頭 | i 的完成時間 t_i + d_i | j 的開始時間 t_j | 滿足 |
|---|---|---|---|---|
| A → C | 是 | 3 | 3 | ✓ 是 |
| B → C | 否 | 2 | 3 | ✓ 是 |
| B → D | 否 | 2 | 2 | ✓ 是 |
| C → E | 是 | 7 | 7 | ✓ 是 |
| D → E | 否 | 4 | 7 | ✓ 是 |
| 最長路徑 | 工期總和 |
|---|---|
| A → C → E | 10 |
- 最短完成時間 T*
- 10
- 提出的方案的完成時間
- 10
- 最長路徑條數
- 1
- 零浮時活動
- A, C, E
- 被違反的約束
- 0
- 提出的方案可行
- 是
- 每個開始時間都在自己的 [E, L] 內
- 是
提出的方案可行,並於 10 = T* 完成,因此是最短完成時間的方案。
為何讀數是精確的
按拓撲次序,E_i 是以 i 的前驅結尾的路徑工期總和的最大值,所以每個可行方案都有 t_i ≥ E_i,而 t = E 本身可行。因此 T* = max_i(E_i + d_i) 是最短完成時間。
反向計算,L_i 是各後繼 j 的 L_j 的最小值再減 d_i;匯點取 L_i = T* − d_i。每個在 T* 前完成的方案都有 t_i ≤ L_i,而向量 L 本身可行且於 T* 完成,所以每個 L_i 都是真正可達的最遲開始,不只是上界。
浮時 L_i − E_i 為零,當且僅當 i 在某條最長路徑上:以 i 結尾的最長路徑工期為 E_i + d_i,接往匯點的最長後續工期為 T* − L_i − d_i,兩者之和僅在 E_i = L_i 時等於 T*。七項活動的預設網絡有兩條最長路徑:A B D E G 與 A C D E G。
在 X → Y 與工期為 4 的 Z 中,T* = 4,X 和 Y 的浮時各為 2。開始時間 (2, 3, 0) 可行,但 (2, 1, 0) 令 X、Y 各自留在區間 [0, 2] 和 [1, 3] 內,卻違反 X → Y:X 於 3 完成,Y 卻於 1 開始。方案要檢查成對活動,個別浮時看不出這點。
若每項活動都在自己的 [E, L] 內開始,方案一定可行嗎?
不一定。只有 t = E 與 t = L 這兩個極端向量保證可行。在兩者之間,每條箭頭 i → j 仍要求 t_j ≥ t_i + d_i,檢查器會列出不成立的箭頭。
工期為 0 至 9 的整數,至多八項活動,資源無限,沒有釋出日期,每個預設網絡的圖固定且無環。更改工期或網絡會把提出的開始時間重設為 E。所有數值都是精確整數。
反例模式
浮時不是互不影響的延誤額度
考慮 ,另有獨立活動 ,工期依次為 。項目需時四。 的最早開始為 ,最遲開始為 ,各有浮時二。兩者都比最早時間延遲二而於 開始是可行的;但若只把 延遲二, 卻仍在最早時間一開始,便違反 。個別浮時上界不能消除先後約束。
以下兩個例子展示邊界情況:最長路徑並列,以及工期為零的活動。
例題 8.2.7
(共用一項活動的兩條最長路徑)
在五項活動的網絡中,把 的工期改為三。則 、、,。反向得 、、、、。浮時為 ,而 與 的長度都是 。關鍵活動 組成兩條最長路徑,而不是一條。
常見錯誤
(只縮短一條關鍵路徑便期望項目縮短)
有兩條最長路徑時,只縮短其中一條路徑上的活動,項目不會縮短。在並列的網絡中,把 由三縮短為二,得 ;完成時間仍是 ,因為 仍是長度十的路徑。只有令每條最長路徑都縮短的改動,才可能降低 。
例題 8.2.8
(工期為零的里程碑)
設 的工期為 ,里程碑 的工期為 , 的工期為 ,箭頭為 、、。正向得 、、,。反向得 、、、。 的浮時為 。最長路徑 的長度為 。里程碑雖不耗時,卻是關鍵活動:它記錄了 必須等待的同步點。
限制
若有環,拓撲算法不適用;環上所有工期均為正時,不等式互相矛盾。零工期的環可能滿足不等式,但已被無環假設排除。人手、機器、隨機工期及非最短完成時間的期限均需其他模型。關鍵路徑是確定性、僅先後約束問題的證書,不是真實項目準時完成的保證。
練習
快速檢查
(驗證第一個例子的全最遲方案滿足每條先後約束。)
解答 · 答案
最遲開始為 。五條箭頭上的前驅完成時間依次為 ,均不遲於後繼開始。
快速檢查
(在第一個例子中,僅把 的工期由二改為四,求新的最早完成時間和一條最長路徑。)
解答 · 答案
均於四開始, 於八開始,完成時間是十一; 長 。
快速檢查
(在 和 例子中,求全最遲開始時間並驗證可行性。)
解答 · 答案
。 在三時完成,正好是 開始; 均在四時完成。
快速檢查
(為何兩項工期嚴格為正、互相先於對方的活動不能滿足先後不等式?)
解答 · 答案
若 且 ,相加 和 得 ,矛盾。