關(guān)鍵路徑-詳細(xì)解讀

關(guān)鍵路徑-詳細(xì)解讀

關(guān)鍵路徑(重定向自關(guān)鍵線(xiàn)路)關(guān)鍵路徑（CriticalPath）目錄1什么是關(guān)鍵路徑2關(guān)鍵路線(xiàn)的特點(diǎn)3探尋關(guān)鍵路徑[1]4Reference什么是關(guān)鍵路徑在項(xiàng)目管理中，關(guān)鍵路徑是指網(wǎng)絡(luò)終端元素的元素的序列，該序列具有最長(zhǎng)的總工期并決定了整個(gè)項(xiàng)目的最短完成時(shí)間。關(guān)鍵路徑的工期決定了整個(gè)項(xiàng)目的工期。任何關(guān)鍵路徑上的終端元素的延遲將直接影響項(xiàng)目的預(yù)期完成時(shí)間（例如在關(guān)鍵路徑上沒(méi)有浮動(dòng)時(shí)間）。一個(gè)項(xiàng)目可以有多個(gè)，并行的關(guān)鍵路徑。另一個(gè)總工期比關(guān)鍵路徑的總工期略少的一條并行路徑被稱(chēng)為次關(guān)鍵路徑。最初，關(guān)鍵路徑方法只考慮終端元素之間的邏輯依賴(lài)關(guān)系。關(guān)鍵鏈方法中增加了資源約束。關(guān)鍵路徑方法是由杜邦公司發(fā)明的。關(guān)鍵路線(xiàn)的特點(diǎn)關(guān)鍵路線(xiàn)具有以下特點(diǎn)：1、關(guān)鍵路線(xiàn)上的活動(dòng)的持續(xù)時(shí)間決定項(xiàng)目的工期，關(guān)鍵路線(xiàn)上所有活動(dòng)的持續(xù)時(shí)間加起來(lái)就是項(xiàng)目的工期。2、關(guān)鍵路線(xiàn)上的任何一個(gè)活動(dòng)都是關(guān)鍵活動(dòng)，其中任何一個(gè)活動(dòng)的延遲都會(huì)導(dǎo)致整個(gè)項(xiàng)目完成時(shí)間的延遲。3、關(guān)鍵路線(xiàn)是從始點(diǎn)到終點(diǎn)的項(xiàng)目路線(xiàn)中耗時(shí)最長(zhǎng)的路線(xiàn)，因此要想縮短項(xiàng)目的工期，必須在關(guān)鍵路線(xiàn)上想辦法，反之，若關(guān)鍵路線(xiàn)耗時(shí)延長(zhǎng)，則整個(gè)項(xiàng)目的完工期就會(huì)延長(zhǎng)。4、關(guān)鍵路線(xiàn)的耗時(shí)是可以完成項(xiàng)目的最短的時(shí)間量。5、關(guān)鍵路線(xiàn)上的活動(dòng)是總時(shí)差最小的活動(dòng)。探尋關(guān)鍵路徑[1]用頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間的有向圖叫AOE（ActivityOnEdgeNetwork）網(wǎng)。AOE網(wǎng)常用于估算工程完成時(shí)間。例如：圖1是一個(gè)網(wǎng)。其中有9個(gè)事件v1，v2，…，v9；11項(xiàng)活動(dòng)a1，a2，…，a11。每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。如v1表示整個(gè)工程開(kāi)始，v9表示整個(gè)工程結(jié)束。V5表示活動(dòng)，a4和a5已經(jīng)完成，活動(dòng)a7和a8可以開(kāi)始。與每個(gè)活動(dòng)相聯(lián)系的權(quán)表示完成該活動(dòng)所需的時(shí)間。如活動(dòng)a1需要6天時(shí)間可以完成。1)AOV網(wǎng)具有的性質(zhì)只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動(dòng)才能開(kāi)始。只有在進(jìn)入某一頂點(diǎn)的各有向邊所代表的活動(dòng)都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。表示實(shí)際工程計(jì)劃的AOE網(wǎng)應(yīng)該是無(wú)環(huán)的，并且存在唯一的入度過(guò)為0的開(kāi)始頂點(diǎn)和唯一的出度為0的完成頂點(diǎn)。2)由事件vj的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間的定義，可以采取如下步驟求得關(guān)鍵活動(dòng)：A、從開(kāi)始頂點(diǎn)v1出發(fā),令ve(1)=0,按拓樸有序序列求其余各頂點(diǎn)的可能最早發(fā)生時(shí)間。Ve(k)=max{ve(j)+dut(<j,k>)}（1.1）j∈T其中T是以頂點(diǎn)vk為尾的所有弧的頭頂點(diǎn)的集合(2≤k≤n)。如果得到的拓樸有序序列中頂點(diǎn)的個(gè)數(shù)小于網(wǎng)中頂點(diǎn)個(gè)數(shù)n，則說(shuō)明網(wǎng)中有環(huán)，不能求出關(guān)鍵路徑，算法結(jié)束。B、從完成頂點(diǎn)vn出發(fā)，令vl(n)=ve(n)，按逆拓樸有序求其余各頂點(diǎn)的允許的最晚發(fā)生時(shí)間:vl(j)=min{vl(k)-dut(<j,k>)}k∈S其中S是以頂點(diǎn)vj是頭的所有弧的尾頂點(diǎn)集合(1≤j≤n-1)。C、求每一項(xiàng)活動(dòng)ai(1≤i≤m)的最早開(kāi)始時(shí)間e(i)=ve(j)；最晚開(kāi)始時(shí)間：l(i)=vl(k)-dut(<j,k>)若某條弧滿(mǎn)足e(i)=l(i)，則它是關(guān)鍵活動(dòng)。對(duì)于圖1所示的AOE網(wǎng)，按以上步驟的計(jì)算結(jié)果見(jiàn)表1，可得到a1,a4,a7,a8,a10,a11是關(guān)鍵活動(dòng)。3）求出AOE網(wǎng)中所有關(guān)鍵活動(dòng)后，只要?jiǎng)h去AOE網(wǎng)中所有的非關(guān)鍵活動(dòng)，即可得到AOE網(wǎng)的關(guān)鍵路徑。這時(shí)從開(kāi)始頂點(diǎn)到達(dá)完成頂點(diǎn)的所有路徑都是關(guān)鍵路徑。一個(gè)AOE網(wǎng)的關(guān)鍵路徑可以不止一條，如圖7.21的AOE網(wǎng)中有二條關(guān)鍵路徑，(v1,v2,v5,v7,v9)和(v1,v2,v5,v8,v9)它們的路徑長(zhǎng)度都是16。如圖2所示：注意:并不是加快任何一個(gè)關(guān)鍵活動(dòng)都可以縮短整個(gè)工程完成的時(shí)間，只有加快那些包括在所有的關(guān)鍵路徑上的關(guān)鍵活動(dòng)才能達(dá)到這個(gè)目的。只有在不改變AOE