第2章 網(wǎng)絡(luò)圖繪制與關(guān)鍵路徑

甘特圖例子1精選ppt甘特圖優(yōu)缺點優(yōu)點：每項活動時間定位非常準(zhǔn)確；圖形簡單、清晰；缺點：活動之間關(guān)系不夠清晰；活動的重要度不夠明確；對大型復(fù)雜工程，甘特圖顯得不太適用2精選ppt單代號網(wǎng)絡(luò)圖法單代號網(wǎng)絡(luò)圖法〔PDM,PrecedenceDiagrammingMethod、節(jié)點法、順序圖法〕大多數(shù)工程管理軟件所采用,軟件工程中PDM更通用3精選ppt活動之間的邏輯關(guān)系A(chǔ)結(jié)束后B才開始〔FS〕一種活動結(jié)束后，另一種活動才能開始這是應(yīng)用最普遍的一種關(guān)系例如：軟件的分析，設(shè)計，編碼活動ABB開始前A必須開始〔SS〕后續(xù)活動不需要等待前導(dǎo)活動結(jié)束后才開始這經(jīng)常表示某種并行，但具有一定依賴關(guān)系的活動例如：軟件的測試活動，往往依賴開發(fā)活動的結(jié)果，但又獨立于開發(fā)活動AB4精選ppt活動之間的邏輯關(guān)系A(chǔ)結(jié)束前B必須結(jié)束〔FF〕例如：熱水器安裝〔B〕廚房粉刷〔A〕A開始后B才結(jié)束〔SF〕這是一種最特殊的活動邏輯先后關(guān)系，即后續(xù)活動的結(jié)束依賴于前導(dǎo)活動的開始日常的生活中，例如：找到新的工作后，才可能放棄原來的工作；許多人再找到新愛后才會放棄舊愛ABAB5精選ppt單代號網(wǎng)絡(luò)方案圖的繪制與計算一、單代號網(wǎng)絡(luò)方案圖的構(gòu)成１.節(jié)點：用圓圈或方框表示，一個節(jié)點表示一項具體的工作。２.箭線：只表示工作之間的相互關(guān)系。箭線的箭頭方向表示工作的前進方向。３.代號：一項工作只能有一個代號。箭頭節(jié)點的號碼應(yīng)大于箭尾節(jié)點的號碼。NO：n工作名稱持續(xù)時間123ESLSEFLF6精選ppt單代號網(wǎng)絡(luò)圖法特點1〕單代號搭接網(wǎng)絡(luò)圖必須正確表述已定的邏輯關(guān)系。2)單代號搭接網(wǎng)絡(luò)圖中，嚴(yán)禁出現(xiàn)循環(huán)回路。3)單代號搭接網(wǎng)絡(luò)圖中，嚴(yán)禁出現(xiàn)雙向箭頭或無箭頭的連線。4)單代號搭接網(wǎng)絡(luò)圖中，嚴(yán)禁出現(xiàn)沒有箭尾節(jié)點的箭線和沒有箭頭節(jié)點的箭線。5)繪制網(wǎng)絡(luò)圖時，箭線不宜交叉。6)單代號搭接網(wǎng)絡(luò)圖只應(yīng)有一個起點節(jié)點和一個終點節(jié)點。當(dāng)網(wǎng)絡(luò)圖中有多項起點節(jié)點或多項終點節(jié)點時，應(yīng)在網(wǎng)絡(luò)圖的兩端分別設(shè)置一項虛工作，作為該網(wǎng)絡(luò)圖的起點節(jié)點(St)和終點節(jié)點(Fin)7精選ppt單代號網(wǎng)絡(luò)圖法特點1)工作之間的邏輯關(guān)系容易表達(dá)，繪圖較簡單；2)網(wǎng)絡(luò)圖便于檢查和修改；3)由于工作持續(xù)時間表示在節(jié)點之中，沒有長度，故不夠形象直觀；4)表示工作之間邏輯關(guān)系的箭線可能產(chǎn)生較多的縱橫交叉現(xiàn)象。8精選ppt例：繪制如下表工作關(guān)系的單代號網(wǎng)絡(luò)方案圖工序ABCDEFGHI緊后工作CDEFEFGHHI---始BFIHGECAD終9精選ppt雙代號網(wǎng)絡(luò)圖法箭線式網(wǎng)絡(luò)圖(ArrowDiagrammingMethod) 以箭線表示活動，每個活動都由兩個數(shù)字來定義。節(jié)點代表關(guān)系虛活動我國應(yīng)用比較多，國內(nèi)采用該方法的軟件較多A45312CBD10精選ppt雙代號網(wǎng)絡(luò)圖圖例總體設(shè)計需求確認(rèn)需求獲取系統(tǒng)測試集成測試編碼詳細(xì)設(shè)計計劃評審項目規(guī)劃12369875411精選ppt如何編制進度方案0建立企業(yè)和工程資源庫1設(shè)置工程日歷、資源日歷2設(shè)置工程的主要里程碑點3在WBS以下出工作清單〔Task，Activity〕4估計每個Task的工期5計算每個Task之間的邏輯關(guān)系6加載完成每個Task所需要的資源和資源數(shù)量7進度計算后，看開工/完工里程碑是否符合合同或業(yè)主要求，看資源負(fù)荷是否過大？8需要調(diào)整嗎？9調(diào)整的方法：壓縮關(guān)鍵路徑上Task的工期：多投入資源以縮短工期，分解工期較長的作業(yè)10適宜了嗎？適宜了，那么把第一份方案保存為目標(biāo)方案〔Baseline〕11公布第一版方案，通知工程干系人12精選ppt關(guān)鍵路線：CPM從工程開始到結(jié)束占用時間最長的路線工作總時差為零的工作，也就是其開始時間或結(jié)束時間沒有任何機動余地的工作。工程的總工期是由關(guān)鍵路線的工作總時間決定的CPM上任一節(jié)點假設(shè)不按期完成，那么整個方案的完工假設(shè)要縮短工程的方案完工期限，應(yīng)當(dāng)設(shè)法縮短某個或某些關(guān)鍵工作的作業(yè)時間某個工程關(guān)鍵路線可能不止一條13精選ppt正推法(Forwardpass)按照時間順序計算最早開始時間和最早完成時間的方法,稱為正推法.首先建立工程的開始時間工程的開始時間是網(wǎng)絡(luò)圖中第一個活動的最早開始時間從左到右，從上到下進行任務(wù)編排當(dāng)一個任務(wù)有多個前置時，選擇其中最大的最早完成日期作為其后置任務(wù)的最早開始日期公式:ES+Duration=EF14精選ppt正推法實例StartLFLSEFESDuration=7TaskA18LFLSEFESDuration=3TaskB14LFLSEFESDuration=6TaskC814LFLSEFESDuration=3TaskD47LFLSEFESDuration=3TaskG1417LFLSEFESDuration=3TaskE710LFLSEFESDuration=2TaskH1719LFLSEFESDuration=2TaskF46Finish當(dāng)一個任務(wù)有多個前置時，選擇其中最大的最早完成日期作為其后置任務(wù)的最早開始日期15精選ppt逆推法(Backwardpass)按照逆時間順序計算最晚開始時間和最晚結(jié)束時間的方法,稱為逆推法.首先建立工程的結(jié)束時間工程的結(jié)束時間是網(wǎng)絡(luò)圖中最后一個活動的最晚結(jié)束時間從右到左，從上到下進行計算當(dāng)一個前置任務(wù)有多個后置任務(wù)時，選擇其中最小最晚開始日期作為其前置任務(wù)的最晚完成日期公式:LF-Duration=LS16精選ppt逆推圖示StartLFLSEFESDuration=7TaskA1818LFLSEFESDuration=3TaskB14811LFLSEFESDuration=6TaskC814814LFLSEFESDuration=3TaskD471114LFLSEFESDuration=3TaskG14171417LFLSEFESDuration=3TaskE7101417LFLSEFESDuration=2TaskH17191719LFLSEFESDuration=2TaskF461214Finish當(dāng)一個前置任務(wù)有多個后置任務(wù)時，選擇其中最小最晚開始日期作為其前置任務(wù)的最晚完成日期CP:A->C->G->HCpPath:1817精選ppt課堂練習(xí)作為工程經(jīng)理，你需要給一個軟件工程做方案安排，經(jīng)過任務(wù)分解后得到任務(wù)A，B，C，D，E，F(xiàn)，G，假設(shè)各個任務(wù)之間沒有滯后和超前，以下圖是這個工程的PDM網(wǎng)絡(luò)圖。通過歷時估計已經(jīng)估算出每個任務(wù)的工期，現(xiàn)已標(biāo)識在PDM網(wǎng)絡(luò)圖上。假設(shè)工程的最早開工日期是第０天，請計算每個任務(wù)的最早開始時間，最晚開始時間，最早完成時間，最晚完成時間，同時確定關(guān)鍵路徑，并計算關(guān)鍵路徑的長度.18精選ppt課堂練習(xí)LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF確定ＣＰ以及ＣＰ的長度？19精選ppt課堂練習(xí)-答案LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF44104121219192412202427272424241619191212612440CP:A->E->C->D->GCPPath:2720精選ppt1、邊表示活動的網(wǎng)(ActivityOnEdgeNetwork，簡稱為AOE網(wǎng))為帶權(quán)有向無環(huán)圖，其中：頂點表示事件，邊表示活動，邊的權(quán)值表示活動持續(xù)的時間。其中：AOE網(wǎng)中頂點表示的事件實際上表達(dá)了一種狀態(tài)，即該頂點的所有入邊表示的活動均已完成，出邊表示的活動可以開始。v1v2v3v4v53813223一個AOE網(wǎng)a1a2a3a4a5a6a7關(guān)鍵路徑程序?qū)崿F(xiàn)一、根本概念21精選ppt2、源點、匯點：表示實際工程的AOE網(wǎng)應(yīng)該只有一個入度為0的頂點和一個出度為0的頂點，前者稱作為源點，后者稱作為匯點。研究的問題：對于表示工程方案的AOE網(wǎng)，需要研究的問題是：完成整個工程至少需要多少時間？哪些活動是影響工程進度的關(guān)鍵？22精選pptv1v2v3v4v53813223a1a2a3a4a5a6a73、關(guān)鍵路徑：由于AOE網(wǎng)中的假設(shè)干活動是可以并行進行的，所以完成工程的最短時間是從源點到匯點的最長路徑的長度，即最長路徑上各邊權(quán)值之和。從源點到匯點的最長路徑稱為關(guān)鍵路徑。AOE網(wǎng)中的關(guān)鍵路徑可能不止一條。23精選ppt

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

應(yīng)為從源點到頂點vj

的最長路徑長度

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

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

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

ve(j)、

e(i)、vl(k)、l(i)24精選pptv1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,

vl(2)=11-8=3

e(1)=0

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

25精選ppt5、關(guān)鍵活動：對活動ai而言，l(i)-e(i)為其在不延誤整個工程工期情況下，可以延遲的時間。假設(shè)e(i)=l(i)那么稱活動ai為關(guān)鍵活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動?？s短或延誤關(guān)鍵活動的持續(xù)時間將提前或推遲整個工程的完工時間。26精選ppt二、如何求AOE網(wǎng)的關(guān)鍵活動1、分析：由關(guān)鍵活動的定義可知，只要求出了某個活動的e(i)和l(i)，便可判斷該活動是否為關(guān)鍵活動。而為了求AOE網(wǎng)中活動的e(i)和l(i)，首先需求網(wǎng)中所有事件的ve(j)和vl(j)。e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)因為：假設(shè)活動ai由<vj,vk>表示，其權(quán)值記為dut(<j,k>)，那么有如下關(guān)系：27精選ppt求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)是按頂點的某一拓?fù)湫蛄械拇涡蜻M行的。28精選ppt(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)是按頂點的某一拓?fù)湫蛄械哪嫘蜻M行的。29精選ppte(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精選ppt2、求關(guān)鍵活動的算法：(1)對AOE網(wǎng)進行拓?fù)渑判?，并按排序的次序求各頂點事件的ve值,假設(shè)網(wǎng)有回路，那么算法終止，否那么執(zhí)行步驟(2);(2)按拓?fù)渑判虻哪嫘蚯蟾黜旤c事件的vl值;(3)根據(jù)各頂點事件的ve值和vl值，求各活動ai的e(i)和l(i)。

假設(shè)e(i)=l(i)，那么ai為關(guān)鍵活動。31精選ppt3、算法描述：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精選pptintCriticalPath(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