第九章CPM

與PERT

(工程網絡計劃)引例：沏茶1324燒水（10）備茶（3）沏茶（2）洗碗（2）一、問題描述一項工程，已知各工序完成時間t及其先后關系求：工程完工期及關鍵工序關鍵工序：主矛盾工序，不能延期完工路線：從始點到終點的一條路關鍵路線：由關鍵工序組成的路線，是所有路線中時間最長的路線。相關概念：1324燒水（10）備茶（3）沏茶（2）洗碗（2）(1)、網絡計劃方法（統籌方法），是一種科學的組織管理技術。(2)、應用：工業、農業、政府、科研、軍事例：阿波羅載人登月計劃“北極星”導彈研制計劃新產品的研制開發設備維修二、求解方法——網絡計劃方法(4)、關鍵路線法——CPM(CriticalPathMethod)

項目評審技術——PERT(ProgramEvaluationandReviewTechnique)

(3)、我國于1991年發布了《網絡計劃技術》三個國家標準（術語，畫法和應用程序），進一步推進了網絡計劃技術在我國的研究，應用。CPM與PERT網絡計劃，這二種方法的主要區別是：1）CPM方法對工程中各工序完工時間的估計是確定的，而PERT方法對時間估計是概率型的。2）PERT方法主要注重工程計劃中的時間問題，而CPM方法在把費用概念引入計劃控制過程中，不僅注重時間問題，而且還考慮工程的費用和成本問題，考慮工程時間的均衡問題。

網絡計劃方法包括繪制計劃網絡圖、進度安排、網絡優化等環節，下面進行分別討論.

網絡計劃方法的第一步工作就是繪制計劃網絡圖，也就是將工序（或稱為活動）進度表轉換為網絡計劃方法的網絡圖。

工序緊前工序緊后工序基本概念:雙代號有向圖：ij(i,j)abc2134e.g.i工序起點j工序終點事項:網絡圖的基本組成：二、求解方法——網絡計劃圖法（CPM）分為三步：繪制工程網絡圖標號法求工期T

標號法求關鍵路線

網絡圖（箭頭圖）的組成要素一般表示工程計劃的網絡圖由三部分組成：箭線、結點和線路。實箭線它表示一道具體工序，箭頭表示工序進行方向，通常稱為雙代號表示法。虛箭線它表示一道虛工序。虛工序不是實際中的具體工序，它僅用于表示工序與工序之間的關聯關系結點它表示一個事項。事項又稱事件，表示一些工序的結束或開始。。線路它是指從最初結點（總開工事項）開始順著箭頭方向連續不斷地到達終點（總完工事項）的通路，其中時間和最大的線路為關鍵線路，相應有次關鍵線路，關鍵線路上的序稱為關鍵工序。

將整個工程分解為若干工序確定各工序的前后順序（緊前、緊后）確定工序完成時間三點估計法：最樂觀時間a、最可能時間m、最悲觀時間btij=6a+4m+b一點估計法繪制網絡圖的準備工作方向，時序，編號。bij7a兩個結點間只允許畫一條線。繪制網絡圖規則:緊前，緊后工序—表示工序前后銜接的邏輯關系．cabd12453繪制網絡圖規則:不允許出現回路123abc繪制網絡圖規則:虛工序的運用120①解決畫法中問題②正確表達工序的前行、后續關系(連結、隔離)③

表達平行作業繪制網絡圖規則:②四個工序A、B、C、D有如下關系：

A是X的緊前工序，A和B同時又是Y的緊前工序123456ABXYA'虛工序

兩種情況需要引入虛工序：12AB12A3B虛工序①兩個工序A、B有相同的始點和終點B'例1、a,b,c,d,

四道工序，c在a,b完工后開始，d在b完工后開始。cabd12345abcd124356例2、已知A是B得緊前工序，C是E的緊前工序，A,C是D的緊前工序．ABDCE12345678網絡圖只允許有一個起點和一個終點.123456782433121繪制網絡圖規則:123465782403130201繪制工程網絡圖（1）順序：按工序的先后從左至右（2）圖的結構弧：表示工序、為工序的起點、終點結點：相鄰工序的時間分界點，稱為事項權：工序的完成時間相鄰弧：工序的前后銜接關系，稱為緊前或緊后工序（3）繪圖要求圖中不能出現缺口、回路和多重邊多重邊的處理：12ab12a3bb'虛工序1324燒水（10）備茶（3）沏茶（2）洗碗（2）例某工廠進行技術改造，需要拆掉舊廠房、建造新廠房和安排設備。這項改建工程可以分解為7道工序，其相關資料如下表：工序代號工序名稱緊前工序工序時間（周）A拆遷/2B工程設計/3C土建工程設計B2.5D采購設備B6E廠房土建C、A20F設備安裝D、E4G設備調試F212345A（2）B(3)C(2.5)D(6)E(20)F(4)6G(2)工序代號工序名稱緊前工序工序時間（周）A拆遷/2B工程設計/3C土建工程設計B2.5D采購設備B6E廠房土建C、A20F設備安裝D、E4G設備調試F2解：工序代號緊前工序工序時間（周）A/2B/3C/2DA3EA4工序代號緊前工序工序時間（周）FB7GB6HD、E4IB、C10JG、I3例：繪制工程網絡圖續左表解：1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)例為籌建某餐館，需制定計劃。將工程分為

14道工序，各工序需時及先后關系如下表。試求

該工程完工期T及關鍵路徑。工序ABCDEFGHIJKLMN緊前工序____DEAFGBHBHIJGCIKL所需天數103127354436347CBAD2E3F4G5H6IJI’KLI’’MN1789101191C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)I’’(0)M(4)10N(7)1102912172125253125383825342521311712920網絡時間與關鍵路線在繪制出網絡圖之后，我們可以由網絡圖求出：1、完成此工程項目所需的最少時間。2、每個工序的開始時間與結束時間。3、關鍵路線及其應用的關鍵工序。4、非關鍵工序在不影響工程的完成時間的前提下，其開始時間與結束時間可以推遲多久。

工序時間：完成某一工序所需要的時間，用tij表示．ij(i,j)時間參數計算(1)、事項最早時間tE(1)=0tE(j)=max{tE(i)+tij}tE(n)=工期(2)、事項最遲時間（逆推）tL(n)=tE(n)=工期tL(i)=min{tL(j)-tij}事項時間參數計算(已知tij)時間參數計算工序時間參數計算(已知tij)(1)、工序最早可能開工時間：tES(i,j)=tE(i)(2)、工序最遲允許開工時間tLS(i,j)=tL(j)-tij時間參數計算總時差

Rij=tLS(i,j)-tES(i,j)關鍵工序：Rij=0關鍵路線：從起點至終點由關鍵工序組成的路線．時間參數計算用標號法求工期T步驟：EjⅡ、給任意事項標，Ej=max{以”}為箭頭的各箭之“箭尾+箭長（1）標出各事項的最早開始時間（2）終點即為工期的標號T1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316Ⅰ、給始點①標0用標號法求關鍵路線步驟：1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316（1）標出各事項的最晚開始時間TⅠ、給終點標Li=min{以”}為箭尾的各箭之“箭頭－箭長Ⅱ、給任意事項標，Li1612128133301A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316T161212813330Rij=的－的－（2）計算各工序的時差Rij：則關鍵工序為Rij=0的工序。注：關鍵工序頭尾皆有=（反之未必成立）12c(4)456b(3)a(5)d(2)3f(3)g(3)e(2)例1：0055993779121212c(4)456b(3)a(5)d(2)3f(3)g(3)e(2)00559934791212例：工序內容工時(天)緊前工序

A

初步研究1/B研究選點2AC準備調研方案4AD聯系調研點2BE培訓工作人員3B,CF準備表格1CG實地調研5D,E,FH寫調研報告2GI開會匯總3H00C(4)F(1)E(3)D(2)B(2)A(1)G(5)H(2)I(3)123456789125987634G(5)H(2)I(3)D(2)E(3)F(1)B(2)C(4)00A(1)001135555588131315151818三、工程工期的概率分析——計劃評審技術（PERT）

PERT與CPM的主要區別：

CPM工序時間是確定的；PERT工序時間tij是隨機變量，而完工期T也是隨機的，由概率知識：T服從正態分布TTE

確定平均工序時間的三點估計法：

總工期其中：（I為關鍵路線）TTE標準化1.給定時間T*，求工期T≤T*內完工的概率PERT的內容方法：首先計算，

然后查表求。912.837.838.17410.3312.1711ABCDEFGH2135764例、已知某工程網絡圖，以及各工序的時間參數。工序ambA101315B5810C7810D7911E246F81014G101215H91113TE=42.330.44/1.00//0.25/0.691112.1710.33498.177.8312.83tij求工程在40天內完工的概率。關鍵路線I為:A→C→F→H；解：2.給定概率p，求完工可能性為p的工期方法：首先查表求，使；再由解出例、上例中，求完工可能性達95%的工期。解：由，查表再由解出

四、網絡優化

通過繪制網絡圖，計算網絡時間參數和確定關鍵路線，得到一個初始的計劃方案。但通常還要對初始計劃方案進行調整和完善，尋求時間更短、資源更省、成本更低的方案，即進行網絡優化。網絡優化包括：時間優化時間－資源優化時間－費用優化

時間優化網絡計劃編制后，最常遇到的問題是所需時間大于規定的時間要求，因此需要改變計劃的技術方案或組織方案。最常用的途徑是縮短工序的持續時間。方法：采取技術措施，縮短關鍵工序的作業時間。采取組織措施，充分利用非關鍵工序的總時差，合理調配資源，縮短關鍵工序的作業時間。1.時間-資源優化（資源的均衡配置）在編制網絡計劃時，通常需要多次的綜合平衡，才能得到在時間進度及資源利用等方面都比較合理的計劃方案。做法：盡量保證關鍵工序的日資源需求量。利用非關鍵工序的時差錯開各工序的使用資源時間，拉平資源需要量的高峰．統籌兼顧工程進度的要求和現有資源的限制，多次綜合平衡。

下面列舉一個拉平資源需要量最高峰的實例。在例5中，若加工工人為65人，并假定這些工人可完成這5個工序任一個，下面來尋求一個時間-資源最優方案。如下表所示：工序需要人數最早開始時間所需時間時差d5860200f22701847g4280300h391001520i26110250

若上述工序都按最早開始時間安排，那么從第60天至第135天的75天里，所需的機械加工工人人數如圖所示。

在圖的上半部中，工序代號后的數字是人數，線下面的數字是非關鍵工序時差長度。圖的下半部表示從第60天至135天內的75天里，所需機械加工工人數，這樣的圖稱為資源負荷圖。

274635f(22人）18h(39人)1558人64人80人81人42人26人65人6080100115135d(58人）i(26人）g(42人）302025

同時我們應優先安排關鍵工序所需的工人，再利用非關鍵工序時差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經過調整，我們讓非關鍵工序f從第80天開始，工序h從第110天開始。找到了時間-資源優化的方案，如圖所示，在不增加工人的情況下保證了工程按期完成。246753f(22人）h(39人）d(58人）i(26人）g(42人）工人數65人608010012013058人42人64人26人65人2.時間-費用優化

在編制網絡計劃中，研究如何使得工程完工時間短，費用少；或者在保證既定工期的前提下，完成任務所需費用最少；或者在限制費用的條件下，工程完工時間最短．

名詞：費用：直接費用和間接費用直接費用：建造工程本身所需材料、人工間接費用：工程所需管理費用、設備租金極限時間正常時間最低成本日程費用工期間接費用直接費用總費用OＴ’極限時間正常時間直接費用變動率(成本斜率)直接費用極限正常tdijDijMijCij==mij-MijDij-dij1500-10005-3=250元/天Cij：單位工時的直接費用變動率(成本斜率)基本步驟：選關鍵工序中成本斜率最低工序趕工，確定可縮天數．重新計算網絡計劃關鍵路線．計算相應總費用．時間－費用優化(3)、例：已知網絡計劃T=74(天)12224563024263181824

正常時間極限時間工時費用工時費用(1,2)

24501670

2.5(1,3)

309018102

1(2,4)

22401848

2(3,4)

2610024103

1.5(3,5)

24802090

2.5(4,6)

18541854

/