AOE網 (Activity On Edge Network)即邊表示活動 的網,是一個帶權的有向無環圖 ,其中頂點 表示事件 (Event),每個事件表示在它之前的活動已經完成,在它之後的活動可以開始,弧 表示活動,權 表示活動持續的時間。AOE網可用來估算工程 的完成時間。由於整個工程只有一個開始點和一個完成點,故在正常的情況(無環)下,網中只有一個入度 為零的點(源點 )和一個出度 為零的點(匯點 )。
AOE網有待研究的問題
完成整項工程至少需要多少時間?
哪些活動是影響工程進度的關鍵?
由於在AOE網中有些活動可以並行 地進行,所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(路徑 上各活動持續時間之和)。路徑長度最長的路徑叫做關鍵路徑 。假設開始點是
v
1
{\displaystyle v_{1}}
,從
v
1
{\displaystyle v_{1}}
到
v
i
{\displaystyle v_{i}}
的最長路徑長度叫做事件
v
i
{\displaystyle v_{i}}
的最早發生時間 ,這個時間決定了所有以
v
i
{\displaystyle v_{i}}
為尾的弧 所表示的活動的最早開始時間 。用e(i)表示活動
a
i
{\displaystyle a_{i}}
的最早開始時間,l(i)為一個活動的最遲開始時間 ,這是在不推遲整個工程完成的前提下,活動
a
i
{\displaystyle a_{i}}
最遲必須開始進行的時間。兩者之差l(i)-e(i)意味着完成活動
a
i
{\displaystyle a_{i}}
的時間餘量 。l(i)=e(i)的活動叫做關鍵活動 。關鍵路徑上的所有活動都是關鍵活動 ,提前完成非關鍵活動 (不在關鍵路徑的活動)並不能加快工程的進度。為了求得AOE網中活動的e(i)和l(i),首先應求得事件的最早發生時間ve(j)和最遲發生時間vl(j)。如果活動
a
i
{\displaystyle a_{i}}
由弧<j, k>表示,其持續時間記為dut(<j, k>),則有:e(i) = ve(j), l(i) = vl(k) - dut(<j, k>)。求ve(j)和vl(j)需分兩步進行:
從ve(0)=0開始向前遞推,其中T是所有以第j個頂點為頭的弧的集合。
v
e
(
j
)
=
M
a
x
{
v
e
(
i
)
+
d
u
t
(
<
i
,
j
>
)
}
<
i
,
j
>∈
T
,
j
=
1
,
2
,
.
.
.
n
{\displaystyle ve(j)=Max\left\{ve(i)+dut(<i,j>)\right\}\quad <i,j>\in T,j=1,2,...n}
從vl(n-1)=ve(n-1)起向後遞推,其中S是所有以第i個頂點為尾的弧的集合。
v
l
(
i
)
=
M
i
n
{
v
l
(
j
)
−
d
u
t
(
<
i
,
j
>
)
}
<
i
,
j
>∈
S
,
i
=
n
−
2
,
n
−
3
,
.
.
.0
{\displaystyle vl(i)=Min\left\{vl(j)-dut(<i,j>)\right\}\quad <i,j>\in S,i=n-2,n-3,...0}
活動
a
i
{\displaystyle a_{i}}
的最早開始時間 e[i]
若活動
a
i
{\displaystyle a_{i}}
是由弧<
v
i
{\displaystyle v_{i}}
,
v
j
{\displaystyle v_{j}}
>表示,根據AOE網的性質,只有事件
v
i
{\displaystyle v_{i}}
發生了,活動
a
i
{\displaystyle a_{i}}
才能開始。也就是說,活動
a
i
{\displaystyle a_{i}}
的最早開始時間應等於事件
v
i
{\displaystyle v_{i}}
的最早發生時間。因此,有:e[i]=ve[i]
活動
a
i
{\displaystyle a_{i}}
的最晚開始時間 l[i]
活動
a
i
{\displaystyle a_{i}}
的最晚開始時間指,在不推遲整個工程完成日期的前提下,必須開始的最晚時間。若 由弧<
v
i
{\displaystyle v_{i}}
,
v
j
{\displaystyle v_{j}}
>>表示,則
a
i
{\displaystyle a_{i}}
的最晚開始時間要保證事件
v
j
{\displaystyle v_{j}}
的最遲發生時間不拖後。因此,應該有:l[i]=vl[j]-dut(<
v
i
{\displaystyle v_{i}}
,
v
j
{\displaystyle v_{j}}
>)
由此得到求關鍵路徑 的算法:
輸入e條弧 <j, k>,建立AOE網的存儲結構;
從源點 出發,令ve[0]=0,按拓撲順序 求其餘各頂點 的最早發生時間ve[i](
1
≤
i
≤
n
−
1
{\displaystyle 1\leq i\leq n-1}
)。如果得到的拓撲有序序列中頂點個數小於網中頂點數n,則說明網中存在環,不能求關鍵路徑,算法終止,否則轉到步驟(3);
從匯點 vn出發,令vl[n-1]=ve[n-1],按逆拓撲順序 求其餘各頂點的最遲發生時間vl[i](
n
−
2
≥
i
≥
2
{\displaystyle n-2\geq i\geq 2}
);
根據各頂點 的ve和vl值,求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某弧 滿足條件e(s)=l(s),則為關鍵活動。