AOE網

AOE網（Activity On Edge Network），是一個帶權的有向無環圖，邊表示活動，其中頂點表示事件（Event），權重表示活動持續的時間。關鍵路徑法（CPM）是一種基於AOE網路的最長路徑方法。AOE網可用來估算工程的完成時間。由於整個工程只有一個開始點和一個完成點，故在正常的情況（無環）下，網中只有一個入度為零的點（源點）和一個出度為零的點（匯點）。

AOE網有待研究的問題

1. 完成整項工程至少需要多少時間？
2. 哪些活動是影響工程進度的關鍵？

由於在AOE網中有些活動可以並列地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度（路徑上各活動持續時間之和）。路徑長度最長的路徑叫做關鍵路徑。假設開始點是$v_{1}$，從$v_{1}$到$v_{i}$的最長路徑長度叫做事件$v_{i}$的最早發生時間，這個時間決定了所有以$v_{i}$為尾的弧所表示的活動的最早開始時間。用e(i)表示活動$a_{i}$的最早開始時間，l(i)為一個活動的最遲開始時間，這是在不推遲整個工程完成的前提下，活動$a_{i}$最遲必須開始進行的時間。兩者之差l(i)-e(i)意味著完成活動$a_{i}$的時間餘量。l(i)=e(i)的活動叫做關鍵活動。關鍵路徑上的所有活動都是關鍵活動，提前完成非關鍵活動（不在關鍵路徑的活動）並不能加快工程的進度。為了求得AOE網中活動的e(i)和l(i)，首先應求得事件的最早發生時間ve(j)和最遲發生時間vl(j)。如果活動$a_{i}$由弧<j, k>表示，其持續時間記為dut(<j, k>)，則有：e(i) = ve(j), l(i) = vl(k) - dut(<j, k>)。求ve(j)和vl(j)需分兩步進行：

1. 從ve(0)=0開始向前遞推，其中T是所有以第j個頂點為頭的弧的集合。

$ve(j)=Max\left\{ve(i)+dut(<i,j>)\right\}\quad <i,j>\in T,j=1,2,...n$

1. 從vl(n-1)=ve(n-1)起向後遞推，其中S是所有以第i個頂點為尾的弧的集合。

$vl(i)=Min\left\{vl(j)-dut(<i,j>)\right\}\quad <i,j>\in S,i=n-2,n-3,...0$

活動$a_{i}$的最早開始時間e[i]

• 若活動$a_{i}$是由弧<$v_{i}$,$v_{j}$>表示，根據AOE網的性質，只有事件$v_{i}$發生了，活動$a_{i}$才能開始。也就是說，活動$a_{i}$的最早開始時間應等於事件$v_{i}$的最早發生時間。因此，有：e[i]=ve[i]

活動$a_{i}$的最晚開始時間l[i]

• 活動$a_{i}$的最晚開始時間指，在不推遲整個工程完成日期的前提下，必須開始的最晚時間。若 由弧< $v_{i}$,$v_{j}$>>表示，則$a_{i}$的最晚開始時間要保證事件$v_{j}$的最遲發生時間不拖後。因此，應該有：l[i]=vl[j]-dut(<$v_{i}$,$v_{j}$>)

由此得到求關鍵路徑的演算法：

1. 輸入e條弧<j, k>，建立AOE網的儲存結構；
2. 從源點出發，令ve[0]=0，按拓撲順序求其餘各頂點的最早發生時間ve[i]（$1\leq i\leq n-1$）。如果得到的拓撲有序序列中頂點個數小於網中頂點數n，則說明網中存在環，不能求關鍵路徑，演算法終止，否則轉到步驟（3）；
3. 從匯點vn出發，令vl[n-1]=ve[n-1]，按逆拓撲順序求其餘各頂點的最遲發生時間vl[i]（$n-2\geq i\geq 2$）；
4. 根據各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某弧滿足條件e(s)=l(s)，則為關鍵活動。