1、運籌學（第三版） 運籌學 教材編寫組 編第 11 章 網絡計劃清華大學出版社碩 第11章 網絡計劃第1節 網絡計劃圖第2節 網絡計劃圖的時間參數計算。第3節 時標網絡計劃圖第4節 網絡計劃的優化第5節 網絡計劃軟件第1節 網絡計劃圖網絡計劃圖的基本思想是：首先應用網絡計劃圖來表示工程項目中計劃要完成的各項工作，完成各項工作必然存在先后順序及其相互依賴的邏輯關系；這些關系用節點、箭線來構成網絡圖。網絡圖是由左向右繪制，表示工作進程。并標注工作名稱、代號和工作持續時間等必要信息。通過對網絡計劃圖進行時間參數的計算，找出計劃中的關鍵工作和關鍵線路；通過不斷改進網絡計劃，尋求最優方案，以求在計劃執行過

2、程中對計劃進行有效的控制與監督，保證合理地使用人力、物力和財力，以最小的消耗取得最大的經濟效果。1.1 基本術語 網絡計劃圖是在網絡圖上標注時標和時間參數的進度計劃圖，實質上是有時序的有向賦權圖。表述關鍵路線法（CPM）和計劃評審技術（PERT）的網絡計劃圖沒有本質的區別，它們的結構和術語是一樣的。僅前者的時間參數是確定型的，而后者的時間參數是不確定型的。于是統一給出一套專用的術語和符號。描述工程項目網絡計劃圖有兩種表達的方式：雙代號網絡計劃圖和單代號網絡計劃圖。雙代號網絡計劃圖在計算時間參數時，又可分為：工作計算法和節點計算法。 基本術語： 節點，（2）工作 節點，箭線是網絡計劃圖的基本組成

3、元素。箭線是一線段帶箭頭實射線,虛射線（用“”,“ ”表示）。 節點用“”或“”表示箭線之間的連接點。 工作（曾稱工序、活動、作業）將整個項目按需要粗細程度分解成若干需要耗費時間或需要耗費其他資源的子項目或單元。它們是網絡計劃圖的基本組成部分。 (3) 雙代號網絡計劃圖。在雙代號網絡計劃圖中，用箭線表示工作，箭尾的節點表示工作的開始點，箭頭的節點表示工作的完成點。用（i-j）兩個代號及箭線表示一項工作。在箭線上標記必須的信息，如表示圖11-1為： (4) 單代號網絡計劃圖 用節點表示工作，箭線表示工作之間的先完成與后完成的關系為邏輯關系。 在節點中標記必須的信息，如圖11-2所示： 以下主要介

4、紹雙代號網絡計劃圖 1.2 雙代號網絡計劃圖以下通過例題來說明雙代號網絡計劃圖的繪制和時間參數的計算,并按工作計算時間參數的方法介紹。例1開發一個新產品，需要完成的工作和先后關系，各項工作需要的時間匯總在邏輯關系表中，見表11-1。要求編制這項目的網絡計劃圖和計算有關參數。 表11-1序號工作名稱工作代號工作持續時間（天）緊后工作1產品設計和工藝設計A60B,C,D,E2外購配套件B45L3鍛件準備C10F4工裝制造1D20G, H5鑄件E40H6機械加工1F18L7工裝制造2G30K8機械加工2H15L9機械加工3K25L10裝配與調試L35/第1步根據表11-1中數據，繪制以下網絡圖，見圖

5、11-3。圖11-3正確表述工程項目中各個工作的相互連接關系和正確繪制網絡計劃圖，應遵循以下規則和了解有關術語:1. 網絡計劃圖的方向、時序和節點編號網絡計劃圖是有向、有序的賦權圖，按項目的工作流程自左向右地繪制。在時序上反映完成各項工作的先后順序。節點編號必須按箭尾節點的編號小于箭頭節點的編號來標記。在網絡圖中只能有一個起始節點，表示工程項目的開始。一個終點節點，表示工程項目的完成。從起始節點開始沿箭線方向順序自左往右，通過一系列箭線和節點，最后到達終點節點的通路，稱為線路。2. 緊前工作和緊后工作緊前工作是指緊排在本工作之前的工作；且開始或完成后，才能開始本工作。緊后工作是指緊排在本工作之

6、后的工作；本工作開始或結束后，才能開始或結束的工作。如圖11-3中，只有工作A 完成后工作B,C,D,E 才能開始，工作A 是B,C,D,E 的緊前工作；而工作 B,C,D,E 則是工作A 的緊后工作。在復雜的工程項目中，它們之間的有三種關系：結束后，才開始（FS）；開始后，才開始(SS)；結束后，才結束。(FF)本例只涉及結束后，才開始(FS)的關系。 從起始節點至本工作之前在同一線路的所有工作，稱為先行工作；自本工作到終點節點在同一線路的所有工作，稱為后繼工作。工作G的先行工作有工作A,D;工作K,L是工作G的后繼工作。 。 3. 虛工作在雙代號網絡計劃圖中，虛工作只表示相鄰工作之間的邏輯

7、關系，不占用時間和不消耗人力，資金等的虛設的工作。虛工作用虛箭線 表示。如圖11-3中的 只表示工作D 完成后，工作H 才能開始 的邏輯關系。4.相鄰兩節點之間只能有一條箭線連接的規則。否則將造成邏輯上的混亂。如圖11-4是錯誤畫法，為了使兩節點之間只有一條箭線，可增加一個節點，并增加一項虛工作 。圖11-5是正確的畫法圖11-4圖11-5應改正為5. 網絡計劃圖中不能有缺口和回路。在網絡計劃圖中嚴禁出現從一個節點出發，順箭線方向又回到原出發節點，形成回路。回路將表示這工作永遠不能完成。網絡計劃圖中出現缺口，表示這些工作永遠達不到終點。項目無法完成。 6. 平行工作。可與本工作同時進行的工作7

8、. 起始節點與終點節點。在網絡計劃圖中只能有一個起始節點和一個終點節點。當工程開始或完成時存在幾個平行工作時，可以用虛工作將它們與起始節點或終點節點連接起來。 12s8. 線路：網絡圖中從起點節點沿箭線方向順序通過一系列箭線與節點，最后到達終點節點的通路。本例中有五條線路。并可以計算出各線路的持續時間，見表11-2。線路線路的組成各工作的持續時間之和（天）1604535=140260101835=12336020302535=170460201535=130560401535=150關鍵路線從網絡圖中可以計算出各線路的持續時間。其中有一條線路的持續時間最長線路是關鍵路線。或稱為主要矛盾線。關鍵

9、路線上的各工作為關鍵工作。因為它的持續時間就決定了整個項目的工期。關鍵路線的特征以后再進一步闡述。 9. 網絡計劃圖的布局。盡可能將關鍵路線布置在網絡計劃圖的中心位置，按工作的先后順序將聯系緊密的工作布置在鄰近的位置。為了便于在網絡計劃圖上標注時間等數據，箭線水平線或具有一段水平線的折線。在網絡計劃圖上附有時間坐標或日歷進程。10. 網絡計劃圖的類型。總網絡計劃圖，以整個項目為計劃對象，編制網絡計劃圖。供決策領導層使用；分級網絡計劃圖，這是按不同管理層次的需要，編制的范圍大小不同，詳細程度不同的網絡計劃圖；供不同管理部門使用；局部網絡計劃圖，將整個項目某部分為對象，編制的更詳細的網絡計劃圖。供

10、專業部門使用。當用計算機網絡計劃軟件編制網絡計劃時，可在計算機上可進行網絡計劃圖分解與合并。網絡計劃圖詳細程度，可以根據需要，將工作分解為更細的子工作；也可以將幾項工作合并為綜合的工作。以便顯示不同粗細程度的網絡計劃。當前的軟件都實現這些操作。第2節 網絡計劃圖的時間參數計算。網絡計劃的時間參數計算有幾種類型：雙代號網絡計劃有工作計算法和節點計算法；單代號網絡計劃有節點計算法。以下僅介紹工作計算法。其它的計算法可參考 1。 網絡圖中工作的時間參數。它們是：工作持續時間(D)； 工作最早開始時間（ES）； 工作最早完成時間（EF）；工作最遲開始時間（LS）；工作最遲完成時間（LF）；工作總時差（

11、TF）；工作自由時差（FF）。2.1 工作持續時間(D)。工作持續時間計算是一項基礎工作，關系到網絡計劃是否能得到正確實施。為了有效地使用網絡計劃技術，需要建立相應的數據庫。這需要專項討論的問題。這里簡述計算工作持續時間的兩類數據和兩種方法： 單時估計法（定額法）每項工作只估計或規定一個確定的持續時間值的方法。一般具有工作的工作量，勞動定額資料以及投入人力的多少等，計算各工作的持續時間； 工作持續時間 Q 工作的工作量。以時間單位表示,如小時;或以體積，重量，長度等單位表示；R 可投入人力和設備的數量；S 每人或每臺設備每工作班能完成的工作量；n 每天正常工作班數。或具有類似工作的持續時間的歷

12、史統計資料時，可以根據這些資料，采用分析對比的方法確定所需工作的持續時間。 三時估計法。在不具備有關工作的持續時間的歷史資料時，在較難估計出工作持續時間時，可對工作進行估計三個時間值，然后計算其平均值。這三個時間值是：樂觀時間。在一切都順利時，完成工作需要的最少時間，記作a。最可能時間。在正常條件下，完成工作所需要時間。記作m。悲觀時間。在不順利條件下，完成工作需要最多時間，記作b。顯然上述三種時間發生都具有一定的概率，根據經驗，這些時間的概率分布認為是正態分布。一般情況下，通過專家估計法，給出三時估計的數據。可以認為：工作進行時出現最順利和最不順利的情況比較少。較多是出現正常的情況。按平均意

13、義可用以下公式計算工作持續時間值： 2.2 計算關系式這些時間參數的關系可以用下圖11-6表示工作的關系狀態。圖11-6手工計算可在網絡圖上進行.計算步驟為:(1) 計算各路線的持續時間(見表11-2).線路線路的組成各工作的持續時間之和（天）1604535=140260101835=12336020302535=170460201535=130560401535=150(2) 按網絡圖的箭線的方向，從起始工作開始，計算各工作的ES,EF.(3) 從網絡圖的終點節點開始，按逆箭線的方向，推算出各工作的LS,LF.(4) 確定關鍵路線(CP)。(5) 計算TF,FF.(6) 平衡資源以下通過例1

14、，計算各工作的時間參數。并將計算結果記入網絡計劃圖的相應工作的中，見圖11-7。圖11-71. 工作最早開始時間ES和工作最早完成時間EF的計算利用網絡計劃圖，從網絡計劃圖的起始點開始，沿箭線方向依次逐項計算。第一項工作的最早開始時間是為0，記作ES1-j=0。(起始點i=1)。第一件工作的最早完成時間EF1-j=ES1-j+D1-j。第一件工作完成后，其緊后工作才能開始。它工作最早完成時間EF就是其緊后工作最早開始時間ES。本工作的持續時間D。 表示為：EFi-j=ESi-j+Di-j計算工作的ES時,當有多項緊前工作情況下，只能這些緊前工作中都完成后才能開始。因此本工作的最早開始時間是：E

15、S=max(緊前工作的EF)其中EF=ES+工作持續時間D，表示為：ESi-j=maxh(EFh-i)=maxh(ESh-iDh-i) ,例1的ES,EF計算值在表11-3的，列中。表11-3表11-3表11-3表11-3表11-3表11-3（續）利用雙代號的特征，很容易在表中確定某工作的緊前工作和緊后工作凡是后續工作的箭尾代號與某工作的箭頭代號相同者，便是它的緊后工作；凡是先行工作的箭頭代號與某工作的箭尾代號相同者，便是它的緊前工作。在表11-3中首先填入、兩列數據，然后由上往下計算ES與EF。若某工作(i-j)的先行工作中存在幾個(h-i),從中選擇最大的EFh-i進行計算ESi-j=ma

16、xhEFh-i,緊即計算EFi-j,如計算ES7-8時，可從表11-3的第列已有的EF6-7,EF5-7,EF3-7中找到最大的EF6-7=135。將它填入表11-3的列，對應的L(7-8)行，即可。如此計算也很方便。2. 工作最遲開始時間LS與工作最遲完成時間LF 應從網絡圖的終點節點開始，采用逆序法逐項計算。即按逆箭線方向，依次計算各工作的最遲完成時間LF和最遲開始時間LS，直到第一項工作為止。網絡圖中最后一項工作(i-n)(j=n)的最遲完成時間應由工程的計劃工期確定。在未給定時，可令其等于其最早完成時間,即LFi-n=EFi-n。EFi-n由表11-3中的計算結果是已知的了。并且應當小

17、于或等于計劃工期規定的時間 Tr。LF=min(緊后工作的LS)，LS=LF-工作持續時間D 其它工作的最遲開始時間LSi-j=LFi-j-Di-j;當有多個緊后工作時，最遲完成時間LF=min(緊后工作的LS),或表示為LFi-j=mink(LFj-kDj-k)。可在表11-4中進行。計算從下到上地進行，從工作（7-8）開始，令表11-4的列最后一行LF7-8=EF7-8=170.表11-4表11-4（繼續）3. 工作時差：是指工作有機動時間。常用有兩種時差。即工作總時差和工作自由時差。 工作總時差TFi-j是指：在不影響工期的前提下，工作所具有的機動時間，按工作計算法時：工作總時差TFi-

18、j=EFi-jESi-jDi-j=LSi-jESi-j 或TFi-j=LFi-jEFi-j 。在表11-4中=的數據。注意：工作總時差往往為若干項工作共同擁有的機動時間，如工作（2-3）和工作（3-7），其工作總時差為47，當工作（2-3）用去一部分機動時間后，工作（3-7）的機動時間將相應地減少。 工作自由時差FF是指：在不影響其緊后工作最早開始的前提下，工作所具有機動時間:FFi-j=ESj-kESi-jDi-j; 或 FFi-j=ESj-kEFi-j計算結果見表11-4 列和圖11-7 工作自由時差是某項工作單獨擁有的機動時間，其大小不受其它工作機動時間的影響。關鍵路線的特征：在線路上從

19、起點到終點都由關鍵工作組成。在確定型網絡計劃中是指線路中工作總持續時間最長的線路。在關鍵線路上無機動時間，工作總時差為零。在非確定型網絡計劃中是指估計工期完成可能性最小的線路第3節 時標網絡計劃圖 時間坐標，簡稱時標。在網絡計劃圖的上方或下方，加表示工程進度時間的坐標軸。根據需要規定時間單位為：小時、天、周、月或季。 標注有時間坐標的網絡計劃圖稱為：時標網絡計劃圖。在該圖中箭線的長度就表示工作持續時間的長度。 并且在圖中可以用實粗箭線或實紅色的箭線表示關鍵工作和關鍵線路。并且可用不同的線型表示出工作的總時差和自由時差。例1的時標網絡計劃圖如圖所示。圖11-8第4節 網絡計劃的優化繪制網絡計劃圖

20、，計算時間參數和確定關鍵線路，僅得到一個初始計劃方案。然后根據上級要求和實際資源的配置，需要對初始方案進行調整和完善。即進行網絡計劃優化。目標是綜合考慮進度，合理利用資源，降低費用等。包括：4.1 工期優化。4.2 資源優化4.3 時間費用優化 4.1 工期優化若網絡計劃圖的計算工期大于上級要求的工期時。必須根據要求計劃的進度，縮短工程項目的完工工期。主要從：采取技術措施，提高工效，縮短關鍵工作的持續時間，使關鍵線路的時間縮短。采取組織措施，充分利用非關鍵工作的總時差，合理調配人力、物力和資金等資源。增加對關鍵工作的投入，以便縮短關鍵工作的持續時間，實現工期縮短。4.2 資源優化在編制初始網絡

21、計劃圖后，需要進一步考慮盡量利用現有資源的問題。即在項目的工期不變的條件下，均衡地利用資源。實際工程項目包括工作繁多，需要投入資源種類很多，均衡地利用資源是很麻煩的事，要用計算機來完成。為了簡化計算，具體操作可以： 優先安排關鍵工作所需要的資源。 利用非關鍵工作的總時差，錯開各工作的開始時間，避開在同一時區內集中使用同一資源，以免出現高峰。 在確實受到資源制約，或在考慮綜合經濟效益的條件下，在許可時，也可以適當地推遲工程的工期。實現錯開高峰的目的。下面通過例1的例子說明平衡人力資源的方法。假設在例1中，現有機械加工工人數65人，要完成工作D,F,G,H,K。各工作需要工人人數列于表11-4表1

22、1-4由于機械加工工人數的限制若上述工作若都按最早開始時間安排，在完成各關鍵工作的75天工期中，每天需要機械加工工人人數如圖11-9所示。圖11-9 有10天需要80人，另10天需要81人。超過了現有機械工人人數的約束必須進行調整。以線表示的非關鍵路線上非關鍵工作F,H有機動時間，若將工作F延遲10天開工，就可以解決第7080天的超負荷問題；將工作H推遲10天開工，可以解決第100110天的超負荷問題。于是新的負荷圖（見圖11-10）能滿足機械工人的人數65人約束條件。圖11-10以上人力資源平衡是利用非關鍵工作的總時差，可以錯開資源負荷的高峰。也可以采用將非關鍵工作分段作業或采用技術措施減少

23、所需要資源。也可以根據計劃規定適當延長項目的工期。 4.3 時間費用優化編制網絡計劃時，要研究如何使完成項目的工期盡可能縮短，費用盡可能少；或在保證既定項目完成時間條件下，所需要的費用最少；或在費用限制的條件下，項目完工的時間最短。這就是時間費用優化要解決的問題。完成一項目的費用可以分為兩大類：1. 直接費用2. 間接費用。 1. 直接費用直接與項目的規模有關的費用。包括材料費用，直接生產工人工資等。為了縮短工作的持續時間和工期，就需要增加投入，即增加直接費用。 2. 間接費用 包括管理費等。一般按項目工期長度進行分攤。工期愈短，分攤的間接費用就愈少。一般項目的總費用與直接費用和間接費用與項目工期之間存在一定關系，可以用圖11-11表示T1 最短工期，項目總費用最高；T2 最經濟的工期；T3 正常的工期當總費用最少工期短于要求工期時，這就是最佳工期。進行時間費用優化時，首先要計算出不同工期下最低直接費用率，然后考慮相應的間接費用。費用優化的步驟： 計算工作費用增加率 （簡稱費用率）費用增加率是指：縮短工作持續時間每一單位時間（如一天）所需要增加的費用。 按工作的正常持續時間計算各關鍵工作的費用率通常可表示為：Ci-j 工作i-j的費用率CCi-j 將工作i-j持續時間縮短為最短持續時間后，完成該工作所需要的直接費