4.6 - AOE Network

Activity-on-Edge Network

AOE Network中， $G=<V,E>$為有向圖:

• V(vertex): 代表事件(Event)

• E(edge): 代表工作(Activity)

• Edge上的數值代表工作完成所花時間

• a1, a2均完工，x才會發生

• x發生後，a3, a4才可開工

e.g.

• 完成此計劃，最快需花多少時間？(1~8最長的時間＝Critical Path Length)

  $\Rightarrow$ 事件的最早發生時間

  1. 0

  2. 4+5+4=13

  3. 4+5=9

  4. 4

  5. 13+6=19

  6. 13+5=18

  7. 4+7=11

  8. 18+5=23

  所以需要23個單位時間才有辦法完成整個計畫。

Critical Path Length: 起點到終點所花最長時間

• 列出所有Critical Path: (從6到8的皆是Critical Path)

  1. 1→4→3→6→8

  2. 1→4→3→2→6→8

• 哪些工作不可延遲(delay)？

  $\Rightarrow$所有Critical Path上的vertex均不可delay

  $\Rightarrow$ {3, 4, 5, 7, 8, 12}

• 求各工作最早開工、最晚開工時間？

  $\Rightarrow$最晚開工時間從終點最快完成時間往回推，算出事件(vertex)最早發生時間(取最小值)