管理運籌學講義：網(wǎng)絡計劃

1、上海電力學院管文上海電力學院管文整理課件1運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外運運 籌籌 學學 課課 件件網(wǎng)絡計劃技術網(wǎng)絡計劃技術Network Program TechniqueNetwork Program Technique上海電力學院管文上海電力學院管文整理課件2 網(wǎng)絡計劃技術網(wǎng)絡計劃技術 1957年，美國杜邦公司運用網(wǎng)絡計劃技術來統(tǒng)籌各項工作，并找出編年，美國杜邦公司運用網(wǎng)絡計劃技術來統(tǒng)籌各項工作，并找出編制與執(zhí)行計劃的關鍵路線，稱為制與執(zhí)行計劃的關鍵路線，稱為(Critical Path Method)，簡，簡稱稱CPM。 1958年，美國海軍武器局

2、在制定研制年，美國海軍武器局在制定研制“北極星北極星”導彈計劃時，開發(fā)出導彈計劃時，開發(fā)出了了(Program Evaluationand Review Technique)，簡稱，簡稱PERT。 1962年產(chǎn)生了能夠體現(xiàn)隨機因素作用的年產(chǎn)生了能夠體現(xiàn)隨機因素作用的(Graphic Evaluation and Review Technique)，簡稱，簡稱GERT。 20世紀世紀70年代，美國年代，美國G.L.穆勒等人，在穆勒等人，在GERT基礎上提出了基礎上提出了(Venture Evaluation Review Technique)，簡稱，簡稱VERT。 這些技術方法均這些技術方法均以

3、網(wǎng)絡描述工序及工序之間的關系以網(wǎng)絡描述工序及工序之間的關系。上海電力學院管文上海電力學院管文整理課件3 工序工序 一項需要人力、物力或時間等資源的相對獨立的活動過程，一項需要人力、物力或時間等資源的相對獨立的活動過程， 又稱作業(yè)；又稱作業(yè)； 在網(wǎng)絡圖中用箭線在網(wǎng)絡圖中用箭線“” 表示；表示； 與某道工序前面直接相連的工序稱為緊前工序；與某道工序前面直接相連的工序稱為緊前工序； 其后直接相連的后繼工序為緊后工序。其后直接相連的后繼工序為緊后工序。 結點結點(事項事項) 結點結點(事項事項)是相鄰工序的分界點；是相鄰工序的分界點； 一般用圓圈來表示，每個結點編上順序號：一般用圓圈來表示，每個結點編

4、上順序號：箭尾結點表示工序的開始，箭頭結點表示工序的完成。 結點結點(事項事項)既不消耗人力、物力，也不占用時間。既不消耗人力、物力，也不占用時間。 網(wǎng)絡圖網(wǎng)絡圖 由工序、事項及由工序、事項及時間參數(shù)（工序時間）時間參數(shù)（工序時間）所構成的賦權有向圖即為網(wǎng)絡圖。所構成的賦權有向圖即為網(wǎng)絡圖。 用箭線表示工序，結點表示工序間相互關系的網(wǎng)絡圖，稱箭線式網(wǎng)絡圖。用箭線表示工序，結點表示工序間相互關系的網(wǎng)絡圖，稱箭線式網(wǎng)絡圖。 一、網(wǎng)絡圖的概念一、網(wǎng)絡圖的概念 上海電力學院管文上海電力學院管文整理課件4工序表示的規(guī)定工序表示的規(guī)定 一條箭線和它的相關事項只能代表一道工序，不能代表多道工序，一條箭線和它

5、的相關事項只能代表一道工序，不能代表多道工序， 兩個結點之間只能有一條箭線相連。兩個結點之間只能有一條箭線相連。不允許出現(xiàn)缺口與回路不允許出現(xiàn)缺口與回路 網(wǎng)絡圖中只能有一個始點和一個終點，使得自網(wǎng)絡圖的始點經(jīng)由任何路徑都網(wǎng)絡圖中只能有一個始點和一個終點，使得自網(wǎng)絡圖的始點經(jīng)由任何路徑都可以到達終點?？梢缘竭_終點。 虛工序虛工序 虛工序是為了表達相鄰工序之間的邏輯關系而虛設的工序。虛工序是為了表達相鄰工序之間的邏輯關系而虛設的工序。 不消耗時間、費用和資源，一般用虛箭線表示。不消耗時間、費用和資源，一般用虛箭線表示。方向方向的規(guī)定的規(guī)定 網(wǎng)絡圖是有方向的，工序應按工藝流程順序或工作的邏輯關系從左

6、向右排列。網(wǎng)絡圖是有方向的，工序應按工藝流程順序或工作的邏輯關系從左向右排列。編號編號的規(guī)定的規(guī)定 編號應從始結點開始，按照時序依次從小到大對結點編號，直到終結點。編號應從始結點開始，按照時序依次從小到大對結點編號，直到終結點。 編號時不允許箭頭編號小于箭尾編號。編號時不允許箭頭編號小于箭尾編號。 二、繪制網(wǎng)絡圖的規(guī)則二、繪制網(wǎng)絡圖的規(guī)則 上海電力學院管文上海電力學院管文整理課件5 某工程的工序一覽表如下，試繪制網(wǎng)絡圖。某工程的工序一覽表如下，試繪制網(wǎng)絡圖。工序工序緊前工序緊前工序a-b-c-da,bea,cfa,b,c123abc4def56上海電力學院管文上海電力學院管文整理課件6 關鍵路

7、線法是在網(wǎng)絡圖的基礎上，通過計算時間參數(shù)，確定關鍵路線法是在網(wǎng)絡圖的基礎上，通過計算時間參數(shù)，確定關鍵路線，從而對工程項目進行更有效的協(xié)調與計劃。關鍵路線，從而對工程項目進行更有效的協(xié)調與計劃。 關鍵路線法適用于常規(guī)性生產(chǎn)項目的計劃安排，各項工作重關鍵路線法適用于常規(guī)性生產(chǎn)項目的計劃安排，各項工作重復性發(fā)生，有確定的操作規(guī)程和時間定額，有較完備的統(tǒng)計復性發(fā)生，有確定的操作規(guī)程和時間定額，有較完備的統(tǒng)計資料。資料。 關鍵路線：關鍵路線：網(wǎng)絡中所有路線最長的路線。網(wǎng)絡中所有路線最長的路線。 上海電力學院管文上海電力學院管文整理課件7 結點的最早時間結點的最早時間tE(j) 結點結點j的最早時間的最

8、早時間tE(j)指以該事項為始點的各道工序的最早開始時間指以該事項為始點的各道工序的最早開始時間，等于從始點開始到本結點的最長路線上各道工序時間之和。等于從始點開始到本結點的最長路線上各道工序時間之和。 從始點事項開始，自左向右，順著箭線方向逐個計算從始點事項開始，自左向右，順著箭線方向逐個計算 。一、結點一、結點(事項事項)的時間參數(shù)計算的時間參數(shù)計算 ),()(max)(0)1(jititjttEiEE 結點的最遲時間結點的最遲時間 tL(j) 指以該事項為結束的各道工序最遲必須完工的時刻，否則將會影響后指以該事項為結束的各道工序最遲必須完工的時刻，否則將會影響后續(xù)工序按時開工，以至推遲整

9、個工程的完工時間。續(xù)工序按時開工，以至推遲整個工程的完工時間。 從終點開始，從右向左，逆箭線方向逐個計算。從終點開始，從右向左，逆箭線方向逐個計算。),()(min)()()(jitjtitntntLjLEL上海電力學院管文上海電力學院管文整理課件8 計算結點時間參數(shù)，確定關鍵路線。計算結點時間參數(shù)，確定關鍵路線。1234564a3b6c5d8e10f04646161666660上海電力學院管文上海電力學院管文整理課件9 工序最早可能開工時間工序最早可能開工時間tES(i, j) 一個工序必須在其各緊前工序都完工后才能開工，一個工序必須在其各緊前工序都完工后才能開工， 工序最早可能開工時間等于

10、其箭尾事項的最早時間。工序最早可能開工時間等于其箭尾事項的最早時間。 tES(i, j)= tE(i) 工序最早可能完工時間工序最早可能完工時間 tEF(i, j) 從最早可能開工時間開工，完成本工序的時間從最早可能開工時間開工，完成本工序的時間 。 tEF(i, j)= tES(i, j) +t(i, j) 工序最遲必須開工時間工序最遲必須開工時間 tLS(i, j) 在不影響工程如期完工的前提下，工序最遲必須開工的時刻。在不影響工程如期完工的前提下，工序最遲必須開工的時刻。 等于它的箭頭事項的最遲時間減去本工序的作業(yè)時間等于它的箭頭事項的最遲時間減去本工序的作業(yè)時間 tLS(i, j)=

11、tL( j) - t(i, j) 工序最遲必須完工時間工序最遲必須完工時間 tLF(i, j) 從最遲必須開工時間開工，完成本工序的時間從最遲必須開工時間開工，完成本工序的時間 。 tLF(i, j)= tLS(i, j) +t(i, j) = tL( j) 二二 、工序的時間參數(shù)計算、工序的時間參數(shù)計算 上海電力學院管文上海電力學院管文整理課件10 時差又稱機動時間或寬裕時間時差又稱機動時間或寬裕時間 在不影響如期完成任務的條件下，各道工序可以機動使在不影響如期完成任務的條件下，各道工序可以機動使用的一段時間。用的一段時間。 工序總時差工序總時差R(i, j) 在不影響整個工程在不影響整個工

12、程最早完工日期最早完工日期的前提下，本工序最早可的前提下，本工序最早可能完工時間可以推遲的時間，稱為工序的總時差。能完工時間可以推遲的時間，稱為工序的總時差。 R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j) 三三 、時差與關鍵路線、時差與關鍵路線 上海電力學院管文上海電力學院管文整理課件11 工序單時差工序單時差r(i, j) 在不影響其緊后工序在不影響其緊后工序最早可能開工最早可能開工的前提下，本工序最早的前提下，本工序最早可能完工時間可以推遲的時間。可能完工時間可以推遲的時間。 r(

13、i, j)= tE( j) -tE(i) -t(i, j) 關鍵路線的確定關鍵路線的確定 總時差為零的工序稱為關鍵工序，總時差為零的工序稱為關鍵工序， 關鍵工序組成的路線就是關鍵路線。關鍵工序組成的路線就是關鍵路線。 tES(A)tEF(A)tLS(A)tLF(A)tES(B)tEF(B)tLS(B)tLF(B)R(i,j)r(i,j)上海電力學院管文上海電力學院管文整理課件12 計算時間參數(shù)計算時間參數(shù)1234564a3b6c5d8e10f04646161666660工序工序t(i,j)tES(i,j) tEF(i,j) tLS(i,j)tLF(i,j)R(i,j)r(i,j)關鍵工序關鍵工

14、序a4b3c6d5e8f10000466436914166661616162301186230720010720cf上海電力學院管文上海電力學院管文整理課件13 實際工作中，許多工程項目的工序時間是不確定的，實際工作中，許多工程項目的工序時間是不確定的， 或者是由于隨機因素的影響，或者是由于隨機因素的影響， 或者是屬于開拓性的工作，沒有經(jīng)驗數(shù)據(jù)或統(tǒng)計資料，或者是屬于開拓性的工作，沒有經(jīng)驗數(shù)據(jù)或統(tǒng)計資料， 很難確定工序時間，這時便不宜采用關鍵路線法。很難確定工序時間，這時便不宜采用關鍵路線法。 采用計劃評審技術，對工序時間進行粗略的估計，而后繪采用計劃評審技術，對工序時間進行粗略的估計，而后繪制

15、網(wǎng)絡圖，找出關鍵路線，并可對工程完工期進行概率估制網(wǎng)絡圖，找出關鍵路線，并可對工程完工期進行概率估計。計。 上海電力學院管文上海電力學院管文整理課件14 工序時間的三種可能估計：工序時間的三種可能估計： 最樂觀時間：在最理想的情況下完成工序所需時間最樂觀時間：在最理想的情況下完成工序所需時間a； 最悲觀時間：在最不利的情況下完成工序所需時間最悲觀時間：在最不利的情況下完成工序所需時間b； 最可能時間：在正常情況下完成工序所需時間最可能時間：在正常情況下完成工序所需時間m。 加權平均就是工序時間加權平均就是工序時間t 一、工序時間估計一、工序時間估計 22)664abbmat（，方差工序時間二、

16、工期估計二、工期估計 工程期望工期等于關鍵路線上各道工序的時間之和工程期望工期等于關鍵路線上各道工序的時間之和 。22)6()64(iiiiiiiEabbmaT，方差工期設規(guī)定的工程完工時間為設規(guī)定的工程完工時間為Tk，則完工時間的概率為，則完工時間的概率為EkTTx)(上海電力學院管文上海電力學院管文整理課件15三、應用舉例三、應用舉例 若合同規(guī)定工期為若合同規(guī)定工期為20，如期完工的概率？，如期完工的概率？ 要求要求90%的把握如期完工，可接受的合同工期？的把握如期完工，可接受的合同工期？工序工序緊前工序緊前工序作業(yè)時間估計作業(yè)時間估計樂觀時間樂觀時間 悲觀時間悲觀時間 可能時間可能時間a

17、-354b-243ca,b132da3114ec,d2109fa71310ge,f2106作業(yè)時間作業(yè)時間均值均值方差方差41/931/921/9516/9816/9101616/9上海電力學院管文上海電力學院管文整理課件16 繪制網(wǎng)絡圖繪制網(wǎng)絡圖1234a3b2c45d8e10f566g0449172323179740 參數(shù)計算參數(shù)計算 工程期望工期工程期望工期 TE=23 ，關鍵工序的方差，關鍵工序的方差 2 =49/9，則，則 (x)=-1.29，查表知，查表知 P(x)=9.9% P(x)=90% ，查表知，查表知 (x)=1.3，則可接受的合同工期為，則可接受的合同工期為TE+ (x

18、) =26上海電力學院管文上海電力學院管文整理課件17 縮短工程時間縮短工程時間 改進工藝和技術裝備，壓縮關鍵工序的作業(yè)時間；改進工藝和技術裝備，壓縮關鍵工序的作業(yè)時間； 合理組織平行作業(yè)、交叉作業(yè)；合理組織平行作業(yè)、交叉作業(yè)；指兩道以上相互獨立的工序同時進行。指將緊前工序完成的部分任務分期分批地轉入下道工序。 利用時差，合理調配資源等途徑實現(xiàn)。利用時差，合理調配資源等途徑實現(xiàn)。上海電力學院管文上海電力學院管文整理課件18 時間時間費用優(yōu)化費用優(yōu)化 在時間進度優(yōu)化中，重點在于如何縮短工期，在時間進度優(yōu)化中，重點在于如何縮短工期， 工期的縮短與費用是密切相關的，工期的縮短與費用是密切相關的， 網(wǎng)

19、絡計劃的優(yōu)化中，應考慮不同的完工時間所對應的工程費用，網(wǎng)絡計劃的優(yōu)化中，應考慮不同的完工時間所對應的工程費用， 找到工程費用最低的完工時間找到工程費用最低的完工時間(最低成本日程最低成本日程)。時間時間費用費用極限完工時間正常完工時間直接費用直接費用間接費用間接費用最優(yōu)完工時間工程總費用工程總費用上海電力學院管文上海電力學院管文整理課件19 尋求最低成本日程的思路：從網(wǎng)絡計劃的關鍵工序著手，對增尋求最低成本日程的思路：從網(wǎng)絡計劃的關鍵工序著手，對增加直接費用做少的某些關鍵工序采取措施，縮短其作業(yè)時間。加直接費用做少的某些關鍵工序采取措施，縮短其作業(yè)時間。時間時間直接直接費用費用極限完工時間正常

20、完工時間極限完工作業(yè)時間正常完工作業(yè)時間正常完工費用趕進度極限完工費用費率費用趕單位時間增加的直接-)(上海電力學院管文上海電力學院管文整理課件20 例例工工序序緊前緊前工序工序作業(yè)時間作業(yè)時間(天天)工序的直接費用工序的直接費用(元元)費率費率正常完工正常完工極限完工極限完工正常完工正常完工極限完工極限完工A-33800800-B-5316001900150CA7320002800200DB6320002300100EB52500860120FE3310001000-GD439001100200合計合計8800間接費用間接費用200元元/天天上海電力學院管文上海電力學院管文整理課件21 方案

21、方案I：正常完工：正常完工1233a5b6d47c4g5e563f035111015151211580工程費用工程費用C(I)=正產(chǎn)完工直接費用正產(chǎn)完工直接費用+間接費用間接費用=8800+20015=11800元元上海電力學院管文上海電力學院管文整理課件22方案方案II：在關鍵路線上趕進度：在關鍵路線上趕進度 趕進度的工序：趕進度的工序：關鍵工序d 趕單位時間進度增加的直接費用最少，選擇工序d 趕緊度； 趕進度的時間：趕進度的時間：工序d 最多只能趕3天，非關鍵路線時差為2和5，故工序d 只能趕2天。1233a5b4d47c4g5e563f0359101313109560工程費用工程費用C(

22、II)=正產(chǎn)完工直接費用正產(chǎn)完工直接費用+趕進度增加的直接費用趕進度增加的直接費用+間接費用間接費用 =8800+2100+20013=11600元元上海電力學院管文上海電力學院管文整理課件23方案方案III：在關鍵路線上趕進度：在關鍵路線上趕進度 趕進度的工序：趕進度的工序：關鍵工序b趕單位時間進度增加的直接費用最少，選擇工序b 趕緊度； 趕進度的時間：趕進度的時間：工序b 最多只能趕2天，非關鍵路線時差為3，故工序b 只能趕2天。1233a3b4d47c4g5e563f03378111187340工程費用工程費用C(III)=正產(chǎn)完工直接費用正產(chǎn)完工直接費用+趕進度增加的直接費用趕進度增加

23、的直接費用+間接費用間接費用 =8800+2100 +2150 +20011=11500元元上海電力學院管文上海電力學院管文整理課件24 方案方案IV：在關鍵路線上趕進度：在關鍵路線上趕進度 趕進度的工序：趕進度的工序：選擇工序d,e同時各 趕緊度； 趕進度的時間：趕進度的時間：工序d 最多只能趕1天，故工序d,e只能同時各趕1天。1233a3b3d47c4g4e563f03367101076330工程費用工程費用C(IV)=正產(chǎn)完工直接費用正產(chǎn)完工直接費用+趕進度增加的直接費用趕進度增加的直接費用+間接費用間接費用 =8800+2100 +2150 +1(100 +120 )+20010=1

24、1520元元上海電力學院管文上海電力學院管文整理課件25時間時間資源優(yōu)化資源優(yōu)化 在一定工期下，通過平衡資源，取得工期與資源的最優(yōu)配置。在一定工期下，通過平衡資源，取得工期與資源的最優(yōu)配置。 平衡原則：平衡原則：優(yōu)先保證關鍵路線上關鍵工序對資源的需求量。向非關鍵工序要資源，利用時差調整非關鍵工序的開工時間，達到與其它工序在占用資源的時間上錯開，拉平資源需要量的高峰。 例，某工程工序一覽表如下，每天只有例，某工程工序一覽表如下，每天只有13人上班，計劃人上班，計劃10天內完成，天內完成，試合理安排生產(chǎn)。試合理安排生產(chǎn)。工序工序abcdefg緊前工序緊前工序-aab,ce,da作業(yè)時間作業(yè)時間3123415每天所需人數(shù)每天所需人數(shù)135826125上海電力學院管文上海