關鍵路徑

定義

曆史

推導過程

應用

影響及意義

介紹

關鍵路徑通常(但并非總是)是決定項目工期的進度活動序列。它是項目中最長的路徑，即使很小浮動也可能直接影響整個項目的最早完成時間。關鍵路徑的工期決定了整個項目的工期，任何關鍵路徑上的終端元素的延遲在浮動時間為零或負數時将直接影響項目的預期完成時間(例如在關鍵路徑上沒有浮動時間)。但特殊情況下，如果總浮動時間大于零，則有可能不會影響項目整體進度。

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

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

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

探尋

AOE網

用頂點表示事件，弧表示活動，弧上的權值表示活動持續的時間的有向圖叫AOE(ActivityOnEdgeNetwork)網。在建築學中也

稱為關鍵路線。AOE網常用于估算工程完成時間。例如:圖1是一個網。其中有9個事件v1，v2，…v9;11項活動a1，a2，…，a11。每個事件表示在它之前的活動已經完成，在它之後的活動可以開始。如v1表示整個工程開始，v9表示整個工程結束。V5表示，活動a2和a3已經完成，活動a7和a8可以開始。與每個活動相聯系的權表示完成該活動所需的時間。如活動a1需要6個時間單位可以完成。

AOE網性質

隻有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。

隻有在進入某一頂點的各有向邊所代表的活動都已經結束，該頂點所代表的事件才能發生。表示實際工程計劃的AOE網應該是無環的，并且存在唯一的入度過為0的開始頂點和唯一的出度為0的完成頂點。

可以采取如下步驟求得關鍵活動:

A、從開始頂點v1出發，令ve(1)=0，按拓撲有序序列求其餘各頂點的可能最早發生時間。Ve(k)=max{ve(j)+dut()}(1.1)j∈T其中T是以頂點vk為尾的所有弧的頭頂點的集合(2≤k≤n)。

如果得到的拓樸有序序列中頂點的個數小于網中頂點個數n，則說明網中有環，不能求出關鍵路徑，算法結束。

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

vl(j)=min{vl(k)-dut()}k∈S其中S是以頂點vj是頭的所有弧的尾頂點集合(1≤j≤n-1)。

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

l(i)=vl(k)-dut()若某條弧滿足e(i)=l(i)，則它是關鍵活動。

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

關鍵路徑

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

研究的問題

(1)完成整個工程至少需要多少時間;

(2)哪些活動是影響工程的關鍵。

1956年，美國杜邦公司提出關鍵路徑法，并于1957年首先用于1000萬美元化工廠建設，工期比原計劃縮短了4個月。杜邦公司在采用關鍵路徑法的一年中，節省了100萬美元。

關鍵路徑術語

(1)關鍵路徑:從源點到彙點的路徑長度最長的路徑叫關鍵路徑。

(2)活動開始的最早時間e(i)

(3)活動開始的最晚時間l(i)定義e(i)=l(i)的活動叫關鍵活動。

(4)事件開始的最早時間ve(i)

(5)事件開始的最晚時間vl(i)

設活動ai由弧;(即從頂點j到k)表示，其持續時間記為dut(;)，則

e(i)=ve(j)

l(i)=vl(k)-dut()(6_6_1)

求ve(i)和vl(j)分兩步:

從ve(1)=0開始向前遞推

ve(j)=Max{ve(i)+dut()}(6_6_2)

T,2<=j<=n

其中，T是所有以j為弧頭的弧的集合。

從vl(n)=ve(n)開始向後遞推

vl(i)=Min{vl(j)-dut()}(6_6_3)

S,1<=i<=n-1

其中，S是所有以i為弧尾的弧的集合。

兩個遞推公式是在拓撲有序和逆拓撲有序的前提下進行。

4、求關鍵路徑的算法

(1)輸入e條弧;，建立AOE網的存儲結構。

(2)從源點v1出發，令ve(1)=0，求ve(j)2<=j<=n。

(3)從彙點vn出發，令vl(n)=ve(n)，求vl(i)1<=i<=n-1。

(4)根據各頂點的ve和vl值，求每條弧s(活動)的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關鍵活動。

求關鍵路徑是在拓撲排序的前提下進行的，不能進行拓撲排序，自然也不能求關鍵路徑。

StatusToplogicalSort(ALGraphG,stack&T){

FindInDegree(G,indegree);

InitStack(S);count=0;ve[0..G.vexnum-1]=0;

while(!StackEmpty(S))

{Pop(S,j);Push(T,j);++count;

for(p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p>adjvex;

if(--indegree[k]==0)Push(S,k);

if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);

}

}

if(count

elsereturnOK;

}

statusCriticalPath(ALGraphG){

if(!ToplogicalOrder(G,T))returnERROR;

vl[0..G.vexnum-1]=ve[G.vexnum-1];

while(!StackEmpty(T))

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p->adjvex;dut=*(p->info);

if(vl[k]-dut

}

for(j=0;j

for(p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p>adjvex;dut=*(p->info);

ee=ve[j];el=vl[k];

tag=(ee==el)?'*':'';

printf(j,kdut,ee,el,tag);

}

}

算法分析

C++完整代碼

#include

#include

#include

usingnamespacestd;

intn,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];

voidinit()

{

inti,a,b,c;

scanf("%d%d",&n,&m);

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&a,&b,&c);

w[a][b]=c;

prev[b]++;

}

}

inlinevoidNewq(intv)

{

r++;

queue[r]=v;

}

inlinevoidDel(intv)

{

inti;

for(i=1;i<=n;i++)

if(w[v][i])

{

prev[i]--;

if(!prev[i])

Newq(i);

}

}

voidtopo()

{

for(inti=1;i<=n;i++)

if(!prev[i])

Newq(i);

while(r

{

l++;

Del(queue[l]);

}

}

voidcrucialpath()

{

inti,j;

memset(Time,0,sizeof(Time));

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((w[j][queue[i]])&&(Time[j]+w[j][queue[i]]>Time[queue[i]]))

{

Time[queue[i]]=Time[j]+w[j][queue[i]];

Pos[queue[i]]=j;

}

}

voidprint()

{

printf("%dn",Time[n]);

inti=n,k=0;

while(i!=1)

{

k++;

path[k]=i;

}

for(i=k;i>1;i--)

printf("%d",path[i]);

printf("%dn",path[1]);

}

intmain()

{

init();

topo();

crucialpath();

print();

return0;

}