AOE網檢視原始碼討論檢視歷史
| AOE網 |
|
中文名: AOE網 外文名: Activity On Edge Network 形 式: 圖 目 的: 描述和分析工程的計劃和過程 |
在現代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在帶權有向圖中若以頂點表示事件，有向邊表示活動，邊上的權值表示該活動持續的時間，這樣的圖簡稱為AOE網。[1] 一個無環的有向圖稱作有向無環圖(directed acyclic graph)，簡稱DAG圖。假設以有向圖表示一個工程的施工圖或程序的數據流圖，則圖中不允許出現迴路，如果出現迴路，說明了某項活動以它自己為先決條件，顯然是荒謬的，工程將無法進行。
拓撲排序
拓撲排序是一種對非線性結構的有向圖進行線性化的重要手段。在給定的有向圖G中，若頂點序列Vi1，Vi2，Vi3，....,Vin，。滿足下列條件：若在有向圖G中從頂點Vi，到頂點Vj有一條路徑，則在序列中頂點Vi必在頂點Vj之前，便稱這個序列為一個拓撲序列。求一個有向圖拓撲序列的過程稱為拓撲排序。 拓撲排序的方法如下： (1)從圖中選擇一個入度為O的頂點並輸出； (2)從圖中刪掉該頂點及其所有以該頂點為弧尾的弧。 反覆執行這兩個步驟，直到所有的頂點都被輸出，輸出的序列就是這個無環有向圖的拓撲序列。 如果在帶權有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權值表示活動的開銷，則此帶權有向圖稱為邊活動網(activity on edge network)，簡稱AOE網。AOE網是一個有向無環圖。AOE網是用來描述由許多交叉活動組成的複雜計劃和工程的方法，比如某工程的AOE網。 在工程中用邊表示活動，邊上的權表示完成這項活動所需要的時間，頂點表示某項活動的開始，頂點1稱為源點（或起點），表示整個工程開始，頂點2稱為匯點（或終點），表示整個工程的結束。用AOE網來估算工程的最短工期（完成整個工程至少需要多少時間）以及哪些活動是影響工程進展的關鍵。
幾個術語
路徑長度：路徑上各活動持續時間的總和（即路徑上所有權之和）。 完成工程的最短時間：從工程開始點（源點）到完成點（匯點）的最長路徑稱為完成工程的最短時間。 關鍵路徑：路徑長度最長的路徑稱為關鍵路徑。
性質
（1）只有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。 （2）只有在進入某點的各有向邊所代表的活動都已結束，該頂點所代表的時事件才能發生。 關鍵路徑（臨界路徑）：在AOE網絡中從源點到匯點（結束頂點）的最長路徑。關鍵路徑上的活動為關鍵活動。