排程是一組不等式
項目活動未必都能同時開始。由 指向 的箭頭表示 完成後 才能開始。工期和先後關係共同決定完成時間的下界;排程計算也應給出達到該下界的可行方案。
假設圖有限、非空且有向無環,每個頂點代表一項活動,工期 已確定,資源無限,沒有釋出日期,項目由時間零開始。活動不可拆分或加速;資源衝突及不確定性不在本模型內。
定義 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
(工期為零的里程碑)
設 的工期為 ,里程碑 的工期為 , 的工期為 ,箭頭為 、、。正向得 、、,。反向得 、、、。 的浮時為 。最長路徑 的長度為 。里程碑雖不耗時,卻是關鍵活動:它記錄了 必須等待的同步點。
限制
若有環,拓撲算法不適用;環上所有工期均為正時,不等式互相矛盾。零工期的環可能滿足不等式,但已被無環假設排除。人手、機器、隨機工期及非最短完成時間的期限均需其他模型。關鍵路徑是確定性、僅先後約束問題的證書,不是真實項目準時完成的保證。
練習
快速檢查
(驗證第一個例子的全最遲方案滿足每條先後約束。)
解答 · 答案
最遲開始為 。五條箭頭上的前驅完成時間依次為 ,均不遲於後繼開始。
快速檢查
(在第一個例子中,僅把 的工期由二改為四,求新的最早完成時間和一條最長路徑。)
解答 · 答案
均於四開始, 於八開始,完成時間是十一; 長 。
快速檢查
(在 和 例子中,求全最遲開始時間並驗證可行性。)
解答 · 答案
。 在三時完成,正好是 開始; 均在四時完成。
快速檢查
(為何兩項工期嚴格為正、互相先於對方的活動不能滿足先後不等式?)
解答 · 答案
若 且 ,相加 和 得 ,矛盾。