第2章 網(wǎng)絡圖繪制與關鍵路徑課件

甘特圖例子1第2章網(wǎng)絡圖繪制與關鍵路徑甘特圖優(yōu)缺點優(yōu)點：每項活動時間定位非常準確；圖形簡單、清晰；缺點：活動之間關系不夠清晰；活動的重要度不夠明確；對大型復雜項目，甘特圖顯得不太適用2第2章網(wǎng)絡圖繪制與關鍵路徑單代號網(wǎng)絡圖法單代號網(wǎng)絡圖法（PDM,PrecedenceDiagrammingMethod、節(jié)點法、順序圖法）大多數(shù)項目管理軟件所采用,軟件項目中PDM更通用3第2章網(wǎng)絡圖繪制與關鍵路徑活動之間的邏輯關系A結束后B才開始（FS）一種活動結束后，另一種活動才能開始這是應用最普遍的一種關系例如：軟件的分析，設計，編碼活動ABB開始前A必須開始（SS）后續(xù)活動不需要等待前導活動結束后才開始這經(jīng)常表示某種并行，但具有一定依賴關系的活動例如：軟件的測試活動，往往依賴開發(fā)活動的結果，但又獨立于開發(fā)活動AB4第2章網(wǎng)絡圖繪制與關鍵路徑活動之間的邏輯關系A結束前B必須結束（FF）例如：熱水器安裝（B）廚房粉刷（A）A開始后B才結束（SF）這是一種最特殊的活動邏輯先后關系，即后續(xù)活動的結束依賴于前導活動的開始日常的生活中，例如：找到新的工作后，才可能放棄原來的工作；許多人再找到新愛后才會放棄舊愛ABAB5第2章網(wǎng)絡圖繪制與關鍵路徑單代號網(wǎng)絡計劃圖的繪制與計算一、單代號網(wǎng)絡計劃圖的構成１.節(jié)點：用圓圈或方框表示，一個節(jié)點表示一項具體的工作。２.箭線：只表示工作之間的相互關系。箭線的箭頭方向表示工作的前進方向。３.代號：一項工作只能有一個代號。箭頭節(jié)點的號碼應大于箭尾節(jié)點的號碼。NO：n工作名稱持續(xù)時間123ESLSEFLF6第2章網(wǎng)絡圖繪制與關鍵路徑單代號網(wǎng)絡圖法特點1）單代號搭接網(wǎng)絡圖必須正確表述已定的邏輯關系。2)單代號搭接網(wǎng)絡圖中，嚴禁出現(xiàn)循環(huán)回路。3)單代號搭接網(wǎng)絡圖中，嚴禁出現(xiàn)雙向箭頭或無箭頭的連線。4)單代號搭接網(wǎng)絡圖中，嚴禁出現(xiàn)沒有箭尾節(jié)點的箭線和沒有箭頭節(jié)點的箭線。5)繪制網(wǎng)絡圖時，箭線不宜交叉。6)單代號搭接網(wǎng)絡圖只應有一個起點節(jié)點和一個終點節(jié)點。當網(wǎng)絡圖中有多項起點節(jié)點或多項終點節(jié)點時，應在網(wǎng)絡圖的兩端分別設置一項虛工作，作為該網(wǎng)絡圖的起點節(jié)點(St)和終點節(jié)點(Fin)7第2章網(wǎng)絡圖繪制與關鍵路徑單代號網(wǎng)絡圖法特點1)工作之間的邏輯關系容易表達，繪圖較簡單；2)網(wǎng)絡圖便于檢查和修改；3)由于工作持續(xù)時間表示在節(jié)點之中，沒有長度，故不夠形象直觀；4)表示工作之間邏輯關系的箭線可能產生較多的縱橫交叉現(xiàn)象。8第2章網(wǎng)絡圖繪制與關鍵路徑例：繪制如下表工作關系的單代號網(wǎng)絡計劃圖工序ABCDEFGHI緊后工作CDEFEFGHHI---始BFIHGECAD終9第2章網(wǎng)絡圖繪制與關鍵路徑雙代號網(wǎng)絡圖法箭線式網(wǎng)絡圖(ArrowDiagrammingMethod)

以箭線表示活動，每個活動都由兩個數(shù)字來定義。節(jié)點代表關系虛活動我國應用比較多，國內采用該方法的軟件較多A45312CBD10第2章網(wǎng)絡圖繪制與關鍵路徑雙代號網(wǎng)絡圖圖例總體設計需求確認需求獲取系統(tǒng)測試集成測試編碼詳細設計計劃評審項目規(guī)劃12369875411第2章網(wǎng)絡圖繪制與關鍵路徑如何編制進度計劃0建立企業(yè)和項目資源庫1設置項目日歷、資源日歷2設置項目的主要里程碑點3在WBS下列出工作清單（Task，Activity）4估計每個Task的工期5計算每個Task之間的邏輯關系6加載完成每個Task所需要的資源和資源數(shù)量7進度計算后，看開工/完工里程碑是否符合合同或業(yè)主要求，看資源負荷是否過大？8需要調整嗎？9調整的方法：壓縮關鍵路徑上Task的工期：多投入資源以縮短工期，分解工期較長的作業(yè)10合適了嗎？合適了，則把第一份計劃保存為目標計劃（Baseline）11公布第一版計劃，通知項目干系人12第2章網(wǎng)絡圖繪制與關鍵路徑關鍵路線：CPM從項目開始到結束占用時間最長的路線工作總時差為零的工作，也就是其開始時間或結束時間沒有任何機動余地的工作。項目的總工期是由關鍵路線的工作總時間決定的

CPM上任一節(jié)點若不按期完成，則整個計劃的完工若要縮短項目的計劃完工期限，應當設法縮短某個或某些關鍵工作的作業(yè)時間某個項目關鍵路線可能不止一條13第2章網(wǎng)絡圖繪制與關鍵路徑正推法(Forwardpass)按照時間順序計算最早開始時間和最早完成時間的方法,稱為正推法.首先建立項目的開始時間項目的開始時間是網(wǎng)絡圖中第一個活動的最早開始時間從左到右，從上到下進行任務編排當一個任務有多個前置時，選擇其中最大的最早完成日期作為其后置任務的最早開始日期公式:ES+Duration=EF14第2章網(wǎng)絡圖繪制與關鍵路徑正推法實例StartLFLSEFESDuration=7TaskA18LFLSEFESDuration=3TaskB14LFLSEFESDuration=6TaskC814LFLSEFESDuration=3TaskD47LFLSEFESDuration=3TaskG1417LFLSEFESDuration=3TaskE710LFLSEFESDuration=2TaskH1719LFLSEFESDuration=2TaskF46Finish當一個任務有多個前置時，選擇其中最大的最早完成日期作為其后置任務的最早開始日期15第2章網(wǎng)絡圖繪制與關鍵路徑逆推法(Backwardpass)按照逆時間順序計算最晚開始時間和最晚結束時間的方法,稱為逆推法.首先建立項目的結束時間項目的結束時間是網(wǎng)絡圖中最后一個活動的最晚結束時間從右到左，從上到下進行計算當一個前置任務有多個后置任務時，選擇其中最小最晚開始日期作為其前置任務的最晚完成日期公式:LF-Duration=LS16第2章網(wǎng)絡圖繪制與關鍵路徑逆推圖示StartLFLSEFESDuration=7TaskA1818LFLSEFESDuration=3TaskB14811LFLSEFESDuration=6TaskC814814LFLSEFESDuration=3TaskD471114LFLSEFESDuration=3TaskG14171417LFLSEFESDuration=3TaskE7101417LFLSEFESDuration=2TaskH17191719LFLSEFESDuration=2TaskF461214Finish當一個前置任務有多個后置任務時，選擇其中最小最晚開始日期作為其前置任務的最晚完成日期CP:A->C->G->HCpPath:1817第2章網(wǎng)絡圖繪制與關鍵路徑課堂練習作為項目經(jīng)理，你需要給一個軟件項目做計劃安排，經(jīng)過任務分解后得到任務A，B，C，D，E，F(xiàn)，G，假設各個任務之間沒有滯后和超前，下圖是這個項目的PDM網(wǎng)絡圖。通過歷時估計已經(jīng)估算出每個任務的工期，現(xiàn)已標識在PDM網(wǎng)絡圖上。假設項目的最早開工日期是第０天，請計算每個任務的最早開始時間，最晚開始時間，最早完成時間，最晚完成時間，同時確定關鍵路徑，并計算關鍵路徑的長度.18第2章網(wǎng)絡圖繪制與關鍵路徑課堂練習LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF確定ＣＰ以及ＣＰ的長度？19第2章網(wǎng)絡圖繪制與關鍵路徑課堂練習-答案LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF44104121219192412202427272424241619191212612440CP:A->E->C->D->GCPPath:2720第2章網(wǎng)絡圖繪制與關鍵路徑1、邊表示活動的網(wǎng)(ActivityOnEdgeNetwork，簡稱為AOE網(wǎng))為帶權有向無環(huán)圖，其中：頂點表示事件，邊表示活動，邊的權值表示活動持續(xù)的時間。其中：AOE網(wǎng)中頂點表示的事件實際上體現(xiàn)了一種狀態(tài)，即該頂點的所有入邊表示的活動均已完成，出邊表示的活動可以開始。v1v2v3v4v53813223一個AOE網(wǎng)a1a2a3a4a5a6a7關鍵路徑程序實現(xiàn)一、基本概念21第2章網(wǎng)絡圖繪制與關鍵路徑2、源點、匯點：表示實際工程的AOE網(wǎng)應該只有一個入度為0的頂點和一個出度為0的頂點，前者稱作為源點，后者稱作為匯點。研究的問題：對于表示工程計劃的AOE網(wǎng)，需要研究的問題是：完成整個工程至少需要多少時間？哪些活動是影響工程進度的關鍵？22第2章網(wǎng)絡圖繪制與關鍵路徑v1v2v3v4v53813223a1a2a3a4a5a6a73、關鍵路徑：由于AOE網(wǎng)中的若干活動是可以并行進行的，所以完成工程的最短時間是從源點到匯點的最長路徑的長度，即最長路徑上各邊權值之和。從源點到匯點的最長路徑稱為關鍵路徑。AOE網(wǎng)中的關鍵路徑可能不止一條。23第2章網(wǎng)絡圖繪制與關鍵路徑

事件vj可能的最早發(fā)生時間ve(j)

應為從源點到頂點vj的最長路徑長度

弧<vj,vk>表示的活動ai的最早開始時間e(i)等于ve(j)。

在不推遲整個工程完成的前提下，事件vk允許的最遲發(fā)生時間vl(k)應等于匯點vn的最遲發(fā)生時間vl(n)減去vk到vn的最長路徑長度。

弧<vj,vk>表示的活動ai的最遲開始時間l(i)等于vl(k)減去弧<vj,vk>的權值。4、

ve(j)、

e(i)、vl(k)、l(i)24第2章網(wǎng)絡圖繪制與關鍵路徑v1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,

vl(2)=11-8=3

e(1)=0

l(1)=vl(2)-3=0

25第2章網(wǎng)絡圖繪制與關鍵路徑5、關鍵活動：對活動ai而言，l(i)-e(i)為其在不延誤整個工程工期情況下，可以延遲的時間。若e(i)=l(i)則稱活動ai為關鍵活動。關鍵路徑上的所有活動都是關鍵活動。縮短或延誤關鍵活動的持續(xù)時間將提前或推遲整個工程的完工時間。26第2章網(wǎng)絡圖繪制與關鍵路徑二、如何求AOE網(wǎng)的關鍵活動1、分析：由關鍵活動的定義可知，只要求出了某個活動的e(i)和l(i)，便可判斷該活動是否為關鍵活動。而為了求AOE網(wǎng)中活動的e(i)和l(i)，首先需求網(wǎng)中所有事件的ve(j)和vl(j)。e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)因為：若活動ai由<vj,vk>表示，其權值記為dut(<j,k>)，則有如下關系：27第2章網(wǎng)絡圖繪制與關鍵路徑求ve(j)和vl(j)需分兩步進行：(1)從ve(1)=0開始向前遞推

ve(j)=max{ve(i)+dut(<vi,vj>)}

<vi,vj>屬于以vj為頭的弧的集合，2<=j<=nv1v2v3v4v53813223a1a2a3a4a5a6a7ve(1)=0

ve(2)=3

ve(3)=max{ve(1)+2,ve(2)+2}=5

ve(4)=max{ve(1)+1,ve(3)+3}=8

ve(5)=max{ve(2)+8,ve(4)+3}=11AOE網(wǎng)中計算事件的ve(j)是按頂點的某一拓撲序列的次序進行的。28第2章網(wǎng)絡圖繪制與關鍵路徑(2)從vl(n)=ve(n)開始向后遞推

vl(i)=min{vl(j)-dut(<vi,vj>)}

<vi,vj>屬于以vi為尾的弧的集合，1<=i<=n-1v1v2v3v4v53813223a1a2a3a4a5a6a7vl(5)=11

vl(4)=vl(5)-3=8

vl(3)=vl(4)-3=5

vl(2)=min{vl(3)-2,vl(5)-8}=3

vl(1)=min{vl(2)-3,vl(3)-2,vl(4)-1}=0AOE網(wǎng)中計算事件的vl(i)是按頂點的某一拓撲序列的逆序進行的。29第2章網(wǎng)絡圖繪制與關鍵路徑e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)vl(5)=11

vl(4)=8

vl(3)=5

vl(2)=3

vl(1)=0ve(1)=0

ve(2)=3

ve(3)=5

ve(4)=8

ve(5)=11活動a1a2a3a4a5a6a7e0003538l0733538l-e0730

0

0

0v1v2v3v4v53813223a1a2a3a4a5a6a7v1v2v3v4v53813223a1a2a3a4a5a6a730第2章網(wǎng)絡圖繪制與關鍵路徑2、求關鍵活動的算法：(1)對AOE網(wǎng)進行拓撲排序，并按排序的次序求各頂點事件的ve值,若網(wǎng)有回路，則算法終止，否則執(zhí)行步驟(2);(2)按拓撲排序的逆序求各頂點事件的vl值;(3)根據(jù)各頂點事件的ve值和vl值，求各活動ai的e(i)和l(i)。

若e(i)=l(i)，則ai為關鍵活動。31第2章網(wǎng)絡圖繪制與關鍵路徑3、算法描述：StackTopologicalOrder(ALGraphG,StackT){inti,j,k,count;StackS;ArcNode*p;FindInDegree(G,indegree);InitStack(&S);InitStack(&T);for(i=0;i<G.vexnum;i++){if(!indegree[i])Push(&S,i);}count=0;for(i=0;i<G.vexnum;i++)ve[i]=0;while(!StackEmpty(&S)){Pop(&S,&j);Push(&T,j);count++;for(p=G.vertices[j].firstarc;p;p=p->nextrc){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<G.vexnum){}elsereturnT;}32第2章網(wǎng)絡圖繪制與關鍵路徑intCriticalPath(ALGraphG){StackT;inti,j,k,dut,ee,el;ArcNode*p;intvl[n];T=TopologicalOrder(G,T);for(i=0;i<G.vexnum;i++)vl[i]=ve[G.vexnum-1];while(!StackEmpty(&T))for(Pop(&T,&j),p=G.vertices[j].firstarc;p;p=p->nextrc)