登錄

關鍵路徑

百科 > 項目管理術語 > 關鍵路徑

1.什么是關鍵路徑

項目管理中,關鍵路徑是指網(wǎng)絡終端元素的元素的序列,該序列具有最長的總工期并決定了整個項目的最短完成時間。

關鍵路徑的工期決定了整個項目的工期。任何關鍵路徑上的終端元素的延遲將直接影響項目的預期完成時間(例如在關鍵路徑上沒有浮動時間)。

一個項目可以有多個,并行的關鍵路徑。另一個總工期比關鍵路徑的總工期略少的一條并行路徑被稱為次關鍵路徑。

最初,關鍵路徑方法只考慮終端元素之間的邏輯依賴關系。關鍵鏈方法中增加了資源約束。

關鍵路徑方法是由杜邦公司發(fā)明的。

2.關鍵路線的特點

關鍵路線具有以下特點:

1、關鍵路線上的活動的持續(xù)時間決定項目的工期,關鍵路線上所有活動的持續(xù)時間加起來就是項目的工期。

2、關鍵路線上的任何一個活動都是關鍵活動,其中任何一個活動的延遲都會導致整個項目完成時間的延遲。

3、關鍵路線是從始點到終點的項目路線中耗時最長的路線,因此要想縮短項目的工期,必須在關鍵路線上想辦法,反之,若關鍵路線耗時延長,則整個項目的完工期就會延長。

4、關鍵路線的耗時是可以完成項目的最短的時間量。

5、關鍵路線上的活動是總時差最小的活動。

3.探尋關鍵路徑[1]

用頂點表示事件,弧表示活動,弧上的權值表示活動持續(xù)的時間的有向圖叫AOE(Activity On Edge Network)網(wǎng) 。AOE網(wǎng)常用于估算工程完成時間。例如:

圖1 是一個網(wǎng)。其中有9個事件v1,v2,…,v9;11項活動a1,a2,…,a11。每個事件表示在它之前的活動已經(jīng)完成,在它之后的活動可以開始。如 v1表示整個工程開始,v9 表示整個工程結束。V5表示活動,a4和a5已經(jīng)完成,活動a7和a8可以開始。與每個活動相聯(lián)系的權表示完成該活動所需的時間。如活動a1需要6天時間可以完成。

Image:AOE網(wǎng)圖1.jpg

1)AOV 網(wǎng)具有的性質

  • 只有在某頂點所代表的事件發(fā)生后,從該頂點出發(fā)的各有向邊所代表的活動才能開始。
  • 只有在進入某一頂點的各有向邊所代表的活動都已經(jīng)結束,該頂點所代表的事件才能發(fā)生。
  • 表示實際工程計劃的AOE網(wǎng)應該是無環(huán)的,并且存在唯一的入度過為0的開始頂點和唯一的出度為0的完成頂點。

2)由事件vj的最早發(fā)生時間和最晚發(fā)生時間的定義,可以采取如下步驟求得關鍵活動:

A、從開始頂點 v 1 出發(fā) , 令 ve(1)=0, 按拓樸有序序列求其余各頂點的可能最早發(fā)生時間。

  • Ve(k)=max{ve(j)+dut(<j,k>)} ( 1.1 )
  • j ∈ T

其中T是以頂點vk為尾的所有弧的頭頂點的集合(2 ≤ k ≤ n) 。

如果得到的拓樸有序序列中頂點的個數(shù)小于網(wǎng)中頂點個數(shù)n,則說明網(wǎng)中有環(huán),不能求出關鍵路徑,算法結束。

B、從完成頂點 v n 出發(fā),令vl(n)=ve(n),按逆拓樸有序求其余各頂點的允許的最晚發(fā)生時間:

  • vl(j)=min{vl(k)-dut(<j,k>)}
  • k ∈ S

其中 S 是以頂點vj是頭的所有弧的尾頂點集合(1 ≤ j ≤ n-1) 。

C、求每一項活動ai(1 ≤ i ≤ m)的最早開始時間e(i)=ve(j);最晚開始時間:

  • l(i)=vl(k)-dut(<j,k>)

若某條弧滿足 e(i)=l(i) ,則它是關鍵活動。

對于圖1所示的 AOE 網(wǎng),按以上步驟的計算結果見表1,可得到a1 , a4 , a7 , a8 , a10 , a11 是關鍵活動。

Image:AOE網(wǎng)表1.jpg

3)求出 AOE 網(wǎng)中所有關鍵活動后,只要刪去AOE網(wǎng)中所有的非關鍵活動,即可得到 AOE 網(wǎng)的關鍵路徑。

這時從開始頂點到達完成頂點的所有路徑都是關鍵路徑。一個AOE網(wǎng)的關鍵路徑可以不止一條,如圖7.21的AOE網(wǎng)中有二條關鍵路徑,(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它們的路徑長度都是16 。如圖2所示:

Image:AOE網(wǎng)圖2.jpg

注意:并不是加快任何一個關鍵活動都可以縮短整個工程完成的時間,只有加快那些包括在所有的關鍵路徑上的關鍵活動才能達到這個目的。只有在不改變AOE網(wǎng)的關鍵路徑的前提下,加快包含在關鍵路徑上的關鍵活動才可以縮短整個工程的完成時間。

評論  |   0條評論