跳至內容

AOE網

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

AOE網(Activity On Edge Network)即邊表示活動的網,是一個帶權的有向無環圖,其中頂點表示事件(Event),每個事件表示在它之前的活動已經完成,在它之後的活動可以開始,表示活動,表示活動持續的時間。AOE網可用來估算工程的完成時間。由於整個工程只有一個開始點和一個完成點,故在正常的情況(無環)下,網中只有一個入度為零的點(源點)和一個出度為零的點(匯點)。

AOE網有待研究的問題

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

由於在AOE網中有些活動可以並行地進行,所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(路徑上各活動持續時間之和)。路徑長度最長的路徑叫做關鍵路徑。假設開始點是,從的最長路徑長度叫做事件最早發生時間,這個時間決定了所有以為尾的所表示的活動的最早開始時間。用e(i)表示活動的最早開始時間,l(i)為一個活動的最遲開始時間,這是在不推遲整個工程完成的前提下,活動最遲必須開始進行的時間。兩者之差l(i)-e(i)意味着完成活動時間餘量。l(i)=e(i)的活動叫做關鍵活動。關鍵路徑上的所有活動都是關鍵活動,提前完成非關鍵活動(不在關鍵路徑的活動)並不能加快工程的進度。為了求得AOE網中活動的e(i)和l(i),首先應求得事件的最早發生時間ve(j)和最遲發生時間vl(j)。如果活動由弧<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個頂點為頭的弧的集合。

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

活動最早開始時間e[i]

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

活動最晚開始時間l[i]

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

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

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