網(wǎng)絡圖繪制與關鍵路徑

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

vl(2)=11-8=3

e(1)=0

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

5、關鍵活動:對活動ai而言,l(i)-e(i)為其在不延誤整個工程工期情況下,可以延遲得時間。若e(i)=l(i)則稱活動ai為關鍵活動。關鍵路徑上的所有活動都是關鍵活動?？s短或延誤關鍵活動的持續(xù)時間將提前或推遲整個工程的完工時間。二、如何求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>),則有如下關系:求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)是按頂點的某一拓撲序列的次序進行的。(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)是按頂點的某一拓撲序列的逆序進行的。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-e0730000v1v2v3v4v53813223a1a2a3a4a5a6a7v1v2v3v4v53813223a1a2a3a4a5a6a72、求關鍵活動得算法:(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為關鍵活動。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;}intCri