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

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

事件vj可能得最早發(fā)生時間ve(j)應(yīng)為從源點(diǎn)到頂點(diǎn)vj得最長路徑長度弧<vj,vk>表示得活動ai得最早開始時間e(i)等于ve(j)。在不推遲整個工程完成得前提下,事件vk允許得最遲發(fā)生時間vl(k)應(yīng)等于匯點(diǎn)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)v1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,

vl(2)=11-8=3

e(1)=0

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

5、關(guān)鍵活動:對活動ai而言,l(i)-e(i)為其在不延誤整個工程工期情況下,可以延遲得時間。若e(i)=l(i)則稱活動ai為關(guān)鍵活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動?？s短或延誤關(guān)鍵活動的持續(xù)時間將提前或推遲整個工程的完工時間。二、如何求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>)因為:若活動ai由<vj,vk>表示,其權(quán)值記為dut(<j,k>),則有如下關(guān)系:求ve(j)和vl(j)需分兩步進(jìn)行:(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)是按頂點(diǎn)的某一拓?fù)湫蛄械拇涡蜻M(jìn)行的。(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)是按頂點(diǎn)的某一拓?fù)湫蛄械哪嫘蜻M(jìn)行的。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、求關(guān)鍵活動得算法:(1)對AOE網(wǎng)進(jìn)行拓?fù)渑判?并按排序得次序求各頂點(diǎn)事件得ve值,若網(wǎng)有回路,則算法終止,否則執(zhí)行步驟(2);(2)按拓?fù)渑判虻媚嫘蚯蟾黜旤c(diǎn)事件得vl值;(3)根據(jù)各頂點(diǎn)事件得ve值和vl值,求各活動ai得e(i)和l(i)。

若e(i)=l(i),則ai為關(guān)鍵活動。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