第十一章網絡計劃章節大綱工程計劃網絡圖的繪制網絡時間的計算關鍵路線與網絡優化一、工程計劃網絡問題（關鍵路徑法）問題的一般提法設：有一項工程，分為若干道工序；已知各工序間的先后關系，以及各工序所需時間t。問：（1）工程完工期T=？（2）工程的關鍵工序有哪些？解法——關鍵路徑法（CPM）繪制工程網絡圖求完工期（用標號法）求關鍵路（用標號法）1.1

網絡計劃圖·

網絡計劃圖的基本思想是：首先應用網絡計劃圖來表示工程項目中計劃要完成的各項工作，完成各項工作必然存在先后順序及其相互依賴的邏輯關系；這些關系用節點、箭線來構成網絡圖。網絡圖是由左向右繪制，表示工作進程。并標注工作名稱、代號和工作持續時間等必要信息。通過對網絡計劃圖進行時間參數的計算，找出計劃中的關鍵工作和關鍵線路；通過不斷改進網絡計劃，尋求最優方案，以求在計劃執行過程中對計劃進行有效的控制與監督，保證合理地使用人力、物力和財力，以最小的消耗取得最大的經濟效果。·網絡計劃圖是在網絡圖上標注時標和時間參數的進度計劃圖，實質上是有時序的有向賦權圖。表述關鍵路線法（CPM）和計劃評審技術（PERT）的網絡計劃圖沒有本質的區別，它們

的結構和術語是一樣的。僅前者的時間參數是確定型的，而后者的時間參數是不確定型的。1.1

網絡計劃圖工

序·

在網絡計劃圖中，用箭線表示工作，箭尾的節點表示工作的開始點，箭頭的節點表示工作的完成點。用（i-j）兩個代號及箭線表示一項工作。在箭線上標記必須的信息，如下圖：箭尾事項箭頭事項工序之間的關系緊前工序：緊排在本工作之前的工作；且開始或完成后，才能開始本工作。緊后工序：緊排在本工作之后的工作；本工作開始或結束后，才能開始或結束的工作。虛工序：不占用時間和不消耗人力，資金等的虛設的工作。虛工序只表示相鄰工序之間的邏輯關系。網絡圖的要求相鄰節點只能是一個工序的相關事項；網絡圖中不能有缺口和回路應改正為TS123AB4C123456ABCDE繪制工程網絡圖順序：按工序先后從左至右；圖中弧（箭線）：表示工序；頂點（結點）：表示相鄰工序的時間分界點，稱事項，用

i表示。相鄰弧：表示工序前后銜接關系，稱緊前（后）工序；要求：圖中不得有缺口、回路和多重邊。缺口：多個始點或多個終點的現象。（應當只有一個始點和終點）處理方法：增加虛工序。多重邊：兩點間有多于一條的邊。AB處理方法：增加虛工序。AA’B例1

為籌建某餐館，需制定計劃。將工程分為14道工序，各工序需時及先后關系如下表。試求該工程完工期T及關鍵路徑。回路：方向一致的閉合鏈。工序內容緊前工序所需天數A購買爐灶及材料——10B購買室內設備——3C招集工人——1D選擇開業地點——2E申請許可得到執照D7F修理門窗、粉刷墻壁E3G砌爐灶、水池A、F5H接通上下水道G4I安裝室內設備B、H4J做好室內裝飾B、H3K購進米面及副食品I、J6L張貼開業廣告G3M人員訓練C、I4N開業前操作試驗K、L7工序ABCDEFGHIJKLMN緊前工序____DEAFGBHBHIJGCIKL所需天數1031273544363471CBAD2E3F4G5H6IJ7I’8KL9I’’M10N11網絡計劃圖的時間參數計算網絡圖中工作的時間參數。它們是：工作持續時間(D)；工作最早開始時間（ES）；工作最早完成時間（EF）；工作最遲開始時間（LS）；工作最遲完成時間（LF）；工作總時差（TF）；工作自由時差（FF）。·工作持續時間(D)——作業時間Ti-j⑴單時估計法（定額法）每項工作只估計或規定一個確定的持續時間值的方法。一般具有工作的工作量，勞動定額資料以及投入人力的多少等，計算各工作的持續時間；工作持續時間Q—工作的工作量。以時間單位表示,如小時;或以體積，重量，長度等單位表示；R—可投入人力和設備的數量；S—每人或每臺設備每工作班能完成的工作量；n—每天正常工作班數。或具有類似工作的持續時間的歷史統計資料時，可以根據這些資料，采用分析對比的方法確定所需工作的持續時間。⑵三時估計法在不具備有關工作的持續時間的歷史資料時，在較難估計出工作持續時間時，可對工作進行估計三個時間值，然后計算其平均值。這三個時間值是：樂觀時間。在一切都順利時，完成工作需要的最少時間，記作a。最可能時間。在正常條件下，完成工作所需要時間。記作m。悲觀時間。在不順利條件下，完成工作需要最多時間，記作b。·

顯然上述三種時間發生都具有一定的概率，根據經驗，這些時間的概率分布認為是正態分布。一般情況下，通過專家估計法，給出三時估計的數據。可以認為：工作進行時出現最順利和最不順利的情況比較少。較多是出現正常的情況。按平均意義可用以下公式計算工作持續時間值：工作最早開始時間ES和工作最早完成時間EF工作的最早開始時間ES是緊前工序最早結束時間。ES=TE（i）EF=ES+tij工作最遲開始時間LS與工作最遲完成時間LF工作的最遲完成時間LF是工作在不影響工期下最遲結束時間。LF=TL（j）

LS=LF-TL(j)最后一項工作的最遲完成時間LF等于其最早完成時間EF工序(i,j)的時間參數x

y事件最早可能發生時間Tei事件最遲必須發生時間Tl網絡時間的圖示法1.節點時間（事件時間）TE（j）=Max(TE(i)+tij)ji箭尾事項箭頭事項A（D）tijc

d事件最遲必須發生時間TL：反向求差取小TL（i）TL（n）=TE(n)

Max(+)

Min(-)TL（i）=Min(TL(j)-tij)a

b事件最早可能發生時間TE：順向求和取大TE(i)TE（1）=0ij開始完成可能必須最早最遲ad-tija+tijdji箭尾事項箭頭事項A（D）tija

bc

d2.工序時間ESⅠⅡLSEFⅣⅢLFⅠⅡⅢⅣ工序A3.工作時差：指工作有機動時間。⑴工作總時差TF（i-j）——在不影響工期的前提下，工作所具有的機動時間i箭尾事項事項A（D）tija

jd-tija+tij箭d頭a

bc

dLS-ES=LF-EFⅠ

ⅡⅢⅣ工序A總時差為零的工序即關鍵工序ji箭尾事項頭項ad-t箭事ija+tijdA（D）tija

bc

d（2）工作自由時差FF（i-j）——在不影響其緊后工作最早開始的前提下，工序最早可能完工時間所具有機動時間ⅠⅡⅢⅣ工序Aji箭尾事項頭項A（D）tija

bc

dad-ti箭ja+tijd

事（3）工作安全時差SF（i-j）——在不影響其緊后工作的最遲開始的前提下，工作所具有機動時間ⅠⅡⅢⅣ工序A（2）求完工期（用標號法）1）標出各事項的最早開始時間，為箭頭的各箭之-給始點

1

標

0

；-給任意點

j

標

Ej

,Ej=Max{以j“箭尾 +箭長tij”}2)

終點

n

的

T 中的T即完工期。C(1)B(3)A(10)D(2)F(3)3

45I(4)J(3)78K(6)L(3)9M(4)10N(7)0122E(7)9G(5)1217I’’(02)16H(4)25I’(0)2531253811順向求和取其大（3）求關鍵路（用標號法）1）標出各事項的最晚開始時間i2）計算各工序

j

的時差R(i,j)j=

的 -tiji

-

的

。的路。為箭尾的各箭之“箭頭 -箭長tij”}-給終點

n

標

； -給任意點T至n3）關鍵路徑：由R(i,j)=0的關鍵工序組成的由19C(1)B(3)A(10)D(2)F(3)3

45H(4)I(4)J(3)7I’(K(6)L(3)M(4)1022E(7)9G(5)1217I’’(0)216250)253125381138253425

82131171292001Min(25,34)N(7)反向求差取其小，i

標

Li

,Li=Min{以

i工序箭尾節點i所需天數箭頭節點jESEFLSLF總時差d-t-a單時差c-t-a自由時差

d-t-babcdA00101212010212222B0032121031921191818C0012534013334332433D002220202000E227992929000F9931212912912000G12125171712171217000H17174212117211721000I21214252521252125000J21213252521242225111K25256313125312531000L17173313117202831111111M25344383825293438990N31317383831383138000ESLSEFLF1791181062345A(

10

)B(

3

)C(

1

)D(

2

)E(

7

)F(

3

)G(

5

)H(

4

)I(

4

)J(

3

)L(

3

)K(

6

)M(

4

)N(

7

)ESLSEFLF完工期T=38（天）；關鍵路：D-E-F-G-H-I-K-N。由本例可見：關鍵工序 頭尾皆有

=，但反之未必。關鍵工序時間之和=工期T。2534253425252525課堂習題求下面網絡計劃圖中的關鍵路徑和完工期。要求使用標號法，給出節點的TE和TL，工序的ES、EF、LS、LF以及總時差TF和自由時差FF312546789A(3

)B(4

)C(5

)D(6

)F(2

)H(3

)E(1

)G(4

)I(5

)小結虛工序的網絡時間也應計算，以判斷其是否為關鍵工序。（虛工作為無機動時間的關鍵工作；否則該虛工作即為有機動時間的非關鍵工作。）關鍵工序有2條：ADEGI和ADFHI·完工期TE為19天。33011001243689B(4

)C(5

)D(6

)H(3

)E(1)00F(2)59

9G(4

)0

03

39

910

10711

1110

1014

1419

19000000I(5

)0000

00011A(3

)iTE

TLTF

FF二、工序時間不確定的工程計劃網絡問題（計劃評審技術PERT）=關鍵工序的平均工序時間之和；=關鍵工序時間方差之和。例2

某工程可分為11項工作，有關資料如下表：工作緊前工作a工序時間mbA-123B-123C-123DA110.517EB2514FB3615GC2310HC129IG、H147JD、E129KF、I、J444畫出施工網絡圖，確定關鍵路線及完工期TE；估計工程在20周內完工的概率。工作緊前工作a工序時間mbA-12320.330.11B-12320.330.11C-12320.330.11DA110.517102.677.13EB251462.004.00FB361572.004.00GC231041.331.77HC12931.331.77IG、H14741.001.00JD、E12931.331.77KF、I、J444400B(2)C(2)2E(6)3467G(4)H(3)J(3)K(4)199012A(2)22125F(7)5615191581211I(4)11762D(10)0E期望工期T

=19；關鍵路：A-D-J-K。0.310.320.330.340.350.62170.62550.629