1、2022-3-81運籌學網絡計劃技術（統籌法）2022-3-821計劃管理與統籌法計劃管理與統籌法 1. 定義1：對于任何一項生產制造、科學實驗、工程實施、軍事作戰等活動，為了充分利用有限的時間、空間與資源（人力、物力、財力），都必須編制一個科學的工作組織計劃來有效地組織、調度與控制該項活動的進程，以實現最佳的效應和效益。而這種為編制科學的組織計劃的有效方法統稱為統籌方法。2022-3-83l例1 甲、乙兩工程師從早上六時起床到上班前有一系列活動要做。對于同樣的活動過程，有人忙亂不堪，甚至遲到，有人則又快又好，關鍵在于一個科學的活動實施計劃。穿衣刷牙洗臉做稀飯熱饅頭吃早飯收拾房間整理出門上班甲

2、穿衣洗臉刷牙收拾房間整理吃早飯出門上班做稀飯熱饅頭乙2022-3-84l例2 大型工程實施（三峽工程、南水北調工程、人造衛星工程、宇航工程等）有如下活動：u產品設計、仿真、試制、中試u原材料設備定貨、采購、運輸、入庫u廠房、設備施工建筑、安裝u產品計劃、生產、銷售、安裝、調試、維護參與單位涉及國家各部門、各行業、事業單位，為高速度、低成本、高質量，并在規定期限內完成該工程項目，其關鍵在：u 抓好科學技術u 抓好項目管理，組織協調好各單位、各任務、各工序的完成。2022-3-85l例3 三軍聯合作戰演習u空軍奪取制空權，對敵實施地面攻擊，運送空降兵u海軍艦艇護衛，運送陸軍、海軍陸戰隊登陸奪取灘頭

3、陣地u登陸完成后的鞏固陣地與縱深發展u電子對抗部隊實施情報收集分析與電子對抗l參與兵種：海軍航空兵、海軍陸戰隊、水面艦艇部隊、空軍殲擊機、攻擊機、轟炸機、電子對抗機各團、大隊，坦克、炮兵、步兵、防化兵、通訊兵、偵察兵、導彈部隊等。l需迅速訂好科學的作戰演習計劃，以便對作戰演習過程演習過程進行有效的管理與控制。2022-3-86l統籌法研究內容uPERT (Program Evaluation and Review Technique) 計劃評審技術uCPM (Critical Path Method) 關鍵路線法uGERT (Graphical Evaluation and Review Te

4、chnique) 隨機網絡技術（直譯為圖示的評價與評審技術）uPERT/CRM，GERT/CPM2022-3-87l統籌法發展歷史uCPM：1956年在美杜邦公司化工廠建立過程中由美蘭德公司提出。uPERT：1958年美海軍特種計劃局在研制“北極星”導彈核潛艇過程中在哈密爾頓公司及洛克菲勒公司協助下提出了一個“北極星計劃”以管理整個工程過程中的8家總承包公司，250家分承包公司，3000家三包公司，9000家廠商，由于使用PERT技術，提高了工作效率使整個工期提前兩年完成。目前PERT/CPM在日、英、法、德中相繼推廣使用并由 我國在寶鋼施工，與鋼（8489年）512項工程，南陽油田工程管理均

5、獲較大效益。目前國家經貿委、計委已要求重大工程必須采用此技術方法。uGERT/CPM 在1966年由美國提出，并在阿波羅登月計劃中首次使用成功，在英、阿的馬島之戰中，1982年4月，英軍三天完成計劃網絡，2003年美軍攻擊伊拉克（30萬大軍用三個月制訂計劃）建筑施工設備維修鋼鐵、造船、汽車制造、石油、地質勘探航空、航天、新材料、信息工程（含軟件工程）2022-3-88l統籌法功能u完成工程需做哪些工序，各工序需多長時間完成？總工期預計多長時間？u完成工程的各工序采用什么樣的邏輯順序關系？關鍵工作是什么？如何加快工程的完成。u環境發生變化時，該工程的風險分析。2022-3-89l計劃網絡圖及其諸

6、要素u定義2：反映一個工程項目中各項作業（工序）的內在邏輯關系的一種有向圖稱為計劃網絡圖，又稱統籌圖，工序流線圖，網絡圖等，以符號G表示。此中“內在邏輯關系”是指由于工程本身的工藝與組織性要求，而對各工序提出的在時間上和空間上所要求的先后處理關系。u定義3：如下表2022-3-810要素定義符號及含義事件（事項）一個或多個作業發生變化（開始或結束）的瞬間狀態 圓圈內為事項名（編號）， 圓圈上方數字為瞬間狀態發 生時刻工序（活動、作業）一個工程通?？蓜澐譃槿舾呻A段來完成，使在每一階段中來完成全部工程的部分內容，這一階段完成的部分工程內容稱為工序或作業、活動。 有向線段上方標號為工序名， 其下方數

7、字表為完成工序a所 需的資源（時間、人力、物 力）數或工序長度路長每一網絡只有一個起點和一個終點，從起點開始經過一系列工序直到終點為止的一條通路稱為路線。路線中所經由的各工序長度之和稱為路長。t (i, j)緊前工序與緊后工序：b的緊前工序為a， 工序a結束后方能完成工序b, a的緊后工序為b關鍵路線，關鍵工序在G的所有路線中，路長最大對應的路線稱為關鍵路線；在關鍵路線上的各工序稱為關鍵工序、序號工序代號工序名稱工序長度緊前工序1a15-2b2a作業明細表反映G中各工序間的前后邏輯關系的表格稱為作業明細表（詳見右表）3c10b312a10ab2022-3-811l例4 某公司研制新產品的部分工

8、序明細表如下，試畫出統籌圖。工序代號 工序名稱（或內容）工序長度緊前工序a產品設計與工藝設計60-b外購配套零件15ac外購生產原料13ad自制主件38ce主配件可靠性試驗8b, d12453abced6015133882022-3-8121.每一作業用一箭線及前后兩節點連接，箭線上標出作業標號，箭線下寫上完成該作業的資源數（通常用時間表示）2.一對結點間只能有一條箭線，且不允許出現回路；若出現并行作業可引入虛工序或人為地將工序一分為二。（虛作業不消耗資源，用虛線表示）并行作業并行作業12ab46a12b46回路回路132ac40b6132a/222b6a/22022-3-8133.不允許出現

9、交叉作業，若出現交叉作業時應引入虛工序123451A1A2A3B1B2B32345A1A2A3B1B2B312345A1A2A3B1B2B3雙向箭頭 可畫成2022-3-8144.結點編號自左向右增長，工序的終止結點編號大于起始結點編號5.統籌圖只有一個起點與一個終點（圖的封閉性）2022-3-815l例5 (例4基礎上再加三道工序f、g、h) 某工程項目作業明細表如下 ，（1）繪制計劃網絡圖 ；（2）求關鍵路線與路長；（3）求關鍵工序序號 工序代號所需時間緊前工序 路線路長1a60-a, b, e, h882b15aa, c, d, e, h 1243c13aa, c, d, f, h 12

10、64d38ca, c, d, g, h關鍵路線1325e8b、d可從最終工序開始逆向完成網絡圖6f10d緊后工序列中沒有標明的工序即為最終的工序7g16d8h5e、f、g2022-3-816l解：若已知緊后工序之作業明細表，故用正象（順向）搜索法，已知緊前工序之作業明細表，故可采用反向搜索法。 （f g h）1253476abedghfc1254376abedghfc8601513388101652022-3-817工程項目任務分解工程項目任務分解確定工程全部事項（工序）的邏輯關系確定工程全部事項（工序）的邏輯關系確定每一工序的延續時間，制定作業明細表確定每一工序的延續時間，制定作業明細表繪制

11、計劃網絡圖，并作調整繪制計劃網絡圖，并作調整對網絡圖各節點，箭線編號對網絡圖各節點，箭線編號計算關鍵路線與關鍵工序，形成計劃初步方案計算關鍵路線與關鍵工序，形成計劃初步方案是否有潛力可挖是否有潛力可挖是否滿足要求是否滿足要求優化計劃方案優化計劃方案編制日程計劃并執行編制日程計劃并執行執行中發生偏差執行中發生偏差是否在允許范圍內是否在允許范圍內結束結束YNYNNY2022-3-818l經驗法與專家法（平均值）：適用于重復性工作，不確定經驗法與專家法（平均值）：適用于重復性工作，不確定性因素少性因素少l三點估計法（又稱六分法）三點估計法（又稱六分法） 其中其中a對工序對工序e延續時間的最樂觀時間（

12、在順利情況下工序延續時間的最樂觀時間（在順利情況下工序e完成的最短可能時間）完成的最短可能時間） b對工序對工序e延續時間的最悲觀時間（最不順利下工序延續時間的最悲觀時間（最不順利下工序e完完成的最長可能時間）成的最長可能時間） M對工序對工序e延續時間的最可能時間（在正常情況下工序延續時間的最可能時間（在正常情況下工序e完成耗費時間）完成耗費時間）驗值）延續時間的估計（或試次試驗）對工序（或重復進行的第為專家其中ejjtntTnjjje164bMaTe2022-3-819l三點估計法 這是由于通常認為工序延續時間）；，（rsba36)(64) 1()()()(2) 1() 1()(max00

13、,)()(),()(222112abDbMaEMsrsrrsabDsrrabaEsrsarbxfMsrbaxxbaxsrBabfsrsr得如下近似等式代入上述兩式經化簡可以從而有，2022-3-820l三點估計法 分布隨機變量的概率密度函數見右Mabxf(x)Mabxf(x)2022-3-821l時間參數的標識與關聯ttES (i, j)EF (i, j)t (i ,j)R (i ,j)TE (i)t (i ,j)TL (j)LS (i, j)LF (i, j)t (i ,j)00工工序序參參數數節節點點參參數數2022-3-822ij ES (i, j), EF (i, j) TE (i)T

14、E (j) LS (i, j), LF (i, j) TL (i)TL (j)minmaxES (i, j)工序（i, j）最早開始時間EF (i, j)工序（i, j）最早完成時間LS (i, j)工序（i, j）最晚開始時間LF (i, j)工序（i, j）最晚完成時間設起始節點序號為1，終點節點序號為n，1ijnTE (i)節點(事項) i 最早開始時間TL (i)節點(事項) i 最遲完成時間R (i, j)工序 (i, j) 的時差(反映該工序的機動時間)R (i)節點 i 的時差(反映該節點的機動時間)2022-3-823各時間參數的相互關系如下:)()()(),(),(),()8

15、()(),(),(),()7(),()(),(),(),()6(),()()5(),(max),()(max)()4(),(min),()(min)()3(),()(2)(, 0) 1 (1iTEiTLiRjiESjiLSjiRjTLjitjiLSjiLFjitiTEjitjiESjiEFjiLFjTLjiEFjitiTEjTEjiLSjitjTLiTLjiESiTESSnTETEiijjDD）（為工期）（待求）（2022-3-824l例6 某公司裝配一新生產線，該工程作業明細表如下，求完成該工程的關鍵路線和相應關鍵工序工序代號 工序內容所需時間(天)緊前工序a生產線設計60-b外購零配件45

16、ac下料、鍛件10ad工裝制造20ae木模鑄件40af機械加工18cg工裝制造30dh機械加工15d, ei機械加工25gj裝配調試35b, i ,f ,h2022-3-825l順向計算法：（自左向右法）（工期SD未知）（最早最早時間）時間）f70,88 18j135,170 35i110,135 25g80,110 30d60,80 2012857643a0,60 60b0,60 45c60,70 10e 60,100 40h100,115 150607080100110135170),(max)(),(),(),()(),(0) 1 ()4()6()2()1(jiEFjTEjitjiESj

17、iEFiTEjiESTEi2022-3-826l逆向計算法：（自右向左法）（工期SD已知） 10 c107,117（最晚最晚時間）時間） 18 f117,135 35 j135,170 25 i110,135 30 g80,110 20 d60,8012857643 60 a0,60 45 b90,135 40 e 80,120 15 120,13506011780120110135170),(min)(),(),(),()(),()()()3()7()5()1(jiLSiTLjitjiLFjiLSjTLjiLFSnTLnTEjD2022-3-827l命題1：作業路線CP為G的關鍵路線 CP上

18、各工序時差為0，l命題2：作業路線CP為G的關鍵路線 CP上各工序時差為0，l命題3：若G為有限網絡，則G至少有一條關鍵路線，至多有有限條關鍵路線，總工期 不可能提前完成，因為是關鍵路線上的關鍵工序。對于非關鍵工序，工時不全為零，從而有潛力可挖。且關鍵路線是所有路線中最長的路線，故只要關鍵路線中各工序完成，其他非關鍵工序必完成，故有總工期公式。0),(),(0),(),(jiRCPjijiRCPji有或對0)(0)(iRCPiiRCPi有或對CPjijitT),(),(2022-3-828工序 最早開始時間ES最晚開始時間LS最早完成時間EF最晚完成時間LF工序時差R (i, j)關鍵工序a0

19、060600b609010513530c601077011747d606080800e608010012020f701178813547g80801101100h10012011513520i1101101351350j11513517017002022-3-829節點i最早開始時間TE (i)最遲完成時間TL (i)時差100026060037011747480800510012020611011007135135081701700l關鍵路線CL：a d g i jl總工期 T=Ta+Td+Tg+Ti+Tj=170天1246782022-3-8301.繪制計劃網絡圖2.自左向右（順向）計算各

20、節點最早開始時間TE (i)及各工序最早開始時間ES (i, j)，最早完成時間EF (i, j)3.自右向左（逆向）計算各節點最遲完成時間TL (i)及各工序最晚完成時間LF (i, j)和最晚開始時間LS (i, j)4.計算各工序時差R (i, j)=LS (i, j)-ES (i, j) 各節點時差R (i)=TL (i)-TE (i)5.尋找時差為0的節點并聯結，即可得關鍵路線與相應關鍵工序 尋找時差為0的工序并聯結，亦可得關鍵路線CP與相應關鍵工序6.計算工程總工期7.對非關鍵工序進行研究，以挖掘潛力CPjijitT),(),(2022-3-831Hij3j2j1TL (i) t

21、(i, j1)t (i, j2)t (i, j3)LS (i, j1)t (i, j1)LF (i, j1)TL (j1)TL (j2)LS (i, j2)t (i, j2)LF (i, j2)LS (i, j3)t (i, j3)LF (i, j3)TL (j3)TL (i) =),(minjiLSj節點i的最遲完成時間最晚開始時間網絡圖（網絡圖（a)時間圖時間圖 (a)0tttt2022-3-832Kji3i2i1ES (i1, j)t (i1, j)EF (i1, j)TE (i1)TE (i2)ES (i2, j)t (i2, j)EF (i2, j)ES (i3, j)t (i3,

22、j)EF (i3, j)TE (i3)TL (i) =)(),(max),(),(maxjTEjiEFjitjiESii網絡圖（網絡圖（b)時間圖時間圖 (b)0tttt2022-3-833輸入節點數輸入節點數n，各工序長度，各工序長度 t (i, j)，1i1，則有：1. ， 其中 與 分別為關鍵路線CP路長的期望與方差2.對 ，G在規定工期T0內完工的概率有 aij工序（i, j ）的最樂觀時間 bij工序（i, j ）的最悲觀時間 mij工序（i, j ）的最可能時間),(2CPCPNTCP2CP00T2),(2),(200)6(6421)()()(2CPjiijijCPCPjiijij

23、ijCPxtCPCPrabbmadtexTTTP，此中2022-3-840l證：1.大型工程的工序數n1，且各工序對任務總工期的影響均勻地微小，且相互獨立，故由中心極限定理知：2.有)()()()() 1 , 0(),()6(),()(64)(*,*),(0000222),(),(),(),(CPCPCPCPCPCPCPCPCPCPCPCPCPCPjiijijCPjiCPjiCPjiCPijijijTTPTTPTTPNTNTabjitVarTVarbmaTENjitT，或有，其中2022-3-841l例8：在例7中取工期T0分別為15，17，18，20周，求1.該計劃網絡按期T0內完工的概率2

24、.欲使按期完工的概率達到95%或99%，試確定相應的工程任務總工期T。l解：1.由命題4結論知對 有 現取 T0=15，則有 此中CP=15，CP=1.025，已由例7中求得。類似地有00 T)()(00CPCPTTTP21)0()025.11515()15(TP1)878. 4()025. 11520(9982. 0)9269. 2()025. 11518(974. 0)95. 1 ()025. 11517(，2022-3-842)(37.17025. 133. 21533. 2025. 11599. 0)025. 115()()(68.16025. 164. 11564. 1025. 11

25、5) 1 , 0(95. 0)025. 115()(00000000周，故有，查表有又若有周，故有表有，查若有TTTTTTTNTTTPT015171820P(TT0)0.50.9740.9982 1l解2. 到2022-3-843l系5：5 . 0)(5 . 0)(5 . 0)()()(5 . 05 . 05 . 0)()(0)(xFxxFxFxFCPGxxxxTPxFxTETGCPCPCPCPCPCPCPCPCPCPCP時，時，故當的單調不減性，以及證：利用分布函數期望長度的關鍵路線為此中，有，則對，的工期為設F(x)10.5CPx2022-3-844l系6)()()()()()()()(0

26、)()()()()(02000100020102221212121212211212211212121TTPTTTTPxFxTTTTPTTPTTVarTVarTETECPCPTTGCPCPCPCPCPCPCPCPCPCPCPCPCPCPCPCPCPCP的單調不減性知有由證：有則對任何工期，且有路長時的工期與執行為與的關鍵路線，同為，設2022-3-845l定義4：若在G中有關鍵路線CPi，i=1k，此中各關鍵路線有對應路長的期望與方差 ， ，i=1,2k，（此中顯然有 ），若有 ，則稱 為G的最關鍵路線（即方差最大的關鍵路線稱為最關鍵路線）l有系6知，若 表執行最關鍵路線 的對應工期，則有 ，

27、 j=1k，即對任何給定工期T0，執行最關鍵路線時要在T0內完成的可能性最小，而考慮到只有該 （最關鍵路線）上所有工序全部完成后工程方能完工，因此在G設計時應對 上的工序予以特別關注。lCP2iCPiCP212maxjlCPkjCPkCPCPCP21)()(00TTPTTPjllTlCPlCPlCP2022-3-8461)(), 1 () 1 ,692. 0()()6 , 1 ()692. 0 ,308. 0()() 1 , 1()308. 0 , 0()() 1, 6(0)()6,()2(611692. 01308. 060)2()() 1 (2)(705040403030202001000

28、000000002TTPUTTPUTTPUTTPTTPTTPTTTCPGCPGTCPCPCPCP時，當時，當時，當時，當時，當，則有為給定工期作路長的期望與方差。為與的關鍵路線，為的工期（隨機變量），為設系2022-3-8471)3(61692. 0)5 . 0(1692. 0308. 0)5 . 0(1308. 00)3(60)2()(04) 1 (0000000，有知對由命題證：TTPT -6-1160.6920.3082340)2()(00 TTP2022-3-848余地的工程計劃太保守，有說明執行給定工期時，當很大的工程計劃完成可能性說明執行給定工期時，當較大的工程計劃完成可能性說明執

29、行給定工期時，當小的工程計劃完成可能性說明執行給定工期時，當成的工程計劃根本不能完說明執行給定工期時，當上圖易得上述結論。即的單調不減性及利用0050040400303002020001021)(), 1 () 1 ,692. 0()()6 , 1 ()692. 0 ,308. 0()() 1 , 1()308. 0 , 0()() 1, 6(0)()6,(21)()2(2TTTPTUTTPTUTTPTUTTPTTTPdxexxx2022-3-849l定義5：設T為G的工期（隨機變量），CP為G的關鍵路線，CP與 為CP路長的期望與方差，則稱 為執行給定工l期T0的計劃難易系數。l例9 對于例

30、7的計劃網絡G，求解給定工期T0分別取13,15,17,18,20（周）時的計劃難易系數0。l解：代入有取，將有由定義20,18,17,15,13025. 11522)(500000TTTTCPCPT013151718200-3.90 03.905.859.75太保守，有潛力可挖太保守，有潛力可挖完成可能性很大完成可能性很大完成可能性很大完成可能性很大完成可能性較大完成可能性較大完成可能性小完成可能性小2CPCPCPTT0002)(2022-3-850l前述的網絡計劃僅給出了初等的計劃模型，該模型一般是不成熟的，它可能在工期（時間）、資源、或費用上存在種種的問題與矛盾或缺陷，因此需要作進一步的

31、統籌處理，這就是網絡計劃優化的主要目的，也是整個統籌法研究的精華與主要內容。l初步的計劃網絡往往存在著下述矛盾或問題：u時間上計算的總工期有可能超過用戶要求期限；或部分工序的時間潛力來得到充分發揮。（浪費時間）u資源（有限）上有的工序由于資源供應過多而浪費，而另一些工序則出現資源的供不應求現象。u費用上為趕工期而使用的工序增買設備、材料或增發獎金等，但事實上這樣的措施卻可能不是節約的，而仍然有潛力可挖。l優化目的是調整與改善原始計劃，以求得一個時間進度快，資源消耗少，成本低的最優計劃方案。2022-3-851l單目標優化模型，通常有 ：u時間優化u資源（設備、材料、人力等）優化u費用優化l多目

32、標優化模型u時間資源優化模型u時間費用優化模型u時間資源費用優化模型2022-3-852炒菜炒菜 8切菜切菜 12淘米淘米 5l向關鍵路線上要時間u強制壓縮關鍵工序工時（技術革新）u將串聯作業調整為平行作業，如例10，例11。1234淘米淘米 5燒水燒水 10洗菜洗菜 55678蒸飯蒸飯 15炒菜炒菜 8吃飯吃飯 25切菜切菜 121234燒水燒水 10洗菜洗菜 567蒸飯蒸飯 15吃飯吃飯 25G1：G2：T1=80分分T2=55分分例例102022-3-853挖地基挖地基 3012澆柏油澆柏油 534鋪石子鋪石子 12澆柏油澆柏油鋪石子鋪石子挖地基挖地基例例11G3G4T3=60天天T4=

33、42天天6664441010102022-3-854l將富裕線路（非關鍵線路）上的資源調整到關鍵線路上來。u以推遲非關鍵工序的開始時間來換取工期的節省。u以推遲非關鍵工序的延續時間來換取工期的節省。u同時推遲非關鍵工序的開始時間和延續時間。l從計劃G外增撥資源u增撥運輸車輛，工人由二班變為三班等方式。來縮短工期。2022-3-855l優化工序間的邏輯結構u變化G中各工序的邏輯順序關系l直接建立G的優化結構模型u通過線性規劃等的建立與求解124356a8M6c8d6N10b4124356a8M6c8d6N10b4124356a8M6c8d6N10b416MNTa=30天天16NMTb=28天天1

34、6M,N并行并行Tc=22天天(a)(b)(c)例例122022-3-856l合理利用現有資源，以最大限度的縮短工期，這就是網絡計劃的時間資源優化的目的。l設T(G)表網絡計劃G對應的工期 A(G)表網絡G所消耗的資源l則時間資源優化模型為如下雙目標數學規則00)(.)(min)(.)(min)(min)(minTGTt sGAAGAt sGTGAGTVGGGG二種單目標規則并可轉化為如下2022-3-857l時間資源優化準則：u關鍵工序所需資源優先安排u“削峰填谷”原則：利用非關鍵工序的時差推遲某些非關鍵工序的開始時間，以降低某些資源需求高峰時段的資源需求量，同時提高某些資源需求低谷時段的資

35、源需求量，在不影響網絡工期的前提下實現工期內各時段的資源均衡使用。u特殊資源特殊利用，工序資源調配以公共資源為主。2022-3-858G 時間資源優化程序框圖輸入工序明細表，資源需求表輸入工序明細表，資源需求表計算網絡時間參數，確定關鍵路線計算網絡時間參數，確定關鍵路線CP利用橫道圖及逐日（或月、年）資源需求利用橫道圖及逐日（或月、年）資源需求量量A(t)，繪制，繪制tA(t)曲線，并作系統分析曲線，并作系統分析搜索資源需求峰值搜索資源需求峰值Gp及其對應時段（及其對應時段（ta,tb），設置控制水平），設置控制水平G0，作，作ts=tb計算高峰期間（計算高峰期間（ ta,tb ）內開工的非關

36、鍵工序的有效機動）內開工的非關鍵工序的有效機動時間時間Th(i,j)及時差及時差Ta(i,j)=LS(i,j) ts=TL(j) t(i,j) - ts按照削峰填谷原則，對高峰期（按照削峰填谷原則，對高峰期（ ta,tb ）內開工的各非關鍵工）內開工的各非關鍵工序序 ，進行排隊，并從中選出有效機動，進行排隊，并從中選出有效機動時間時間Tn(i,j)大且資源強度大且資源強度V(i,j) 小的對應工序小的對應工序(i,j)將上述工序將上述工序(i,j)的最早開工時間推遲到的最早開工時間推遲到tb，即，即ES(i,j)0即LS(i,j)tb，說明工序(i,j)有后移到tb后的可能R(i,j)=LS

37、ES(i,j)Th(i,j)=LS tb為對后移到tb后的有效機動時間2022-3-862e 60,100 4080,120g(42人人)80,110 30 80，110i(26人人)110,135 25110,135c60,70 10a0,60 60 0，60 f(22人人)70,88 18117,135j135,170 35 135,170d(58人人)60,80 20 60,801857643b 60,105 45 90,135h(39人人)100,115 15 120,13506070801001101351702G圖圖2022-3-863l解1.根據工序明細表及資源需求表計算根據工序

38、明細表及資源需求表計算G的網絡參數，并的網絡參數，并確定關鍵路線確定關鍵路線CP及關鍵工序集為：及關鍵工序集為：a,d,g,i,j，根據向，根據向非關鍵路線上要資源的原則，故應考慮非關鍵工序非關鍵路線上要資源的原則，故應考慮非關鍵工序b,c,e,f,h的資源調整問題，但此中由于工序的資源調整問題，但此中由于工序b,c,e的特殊的特殊性無法用其它資源替代故不予考慮其資源調整。此外性無法用其它資源替代故不予考慮其資源調整。此外又由于公司所擁有的共用資源（機加工工人）共給僅又由于公司所擁有的共用資源（機加工工人）共給僅為為65人，而關鍵工序人，而關鍵工序d,g,i之一。若與其它工序并行工之一。若與其

39、它工序并行工作時還可能會出現資源超負荷問題，綜合上述考慮，作時還可能會出現資源超負荷問題，綜合上述考慮，以下來討論工序以下來討論工序d,f,g,h,i的資源調整與優化問題。的資源調整與優化問題。2.根據工序根據工序d,f,g,h,i的最早開始時間的最早開始時間ES和最早結束時間和最早結束時間LS畫出橫道圖（畫出橫道圖（a）及相應的資源負荷（）及相應的資源負荷（b），其中），其中A(t)表表t日的資源需求總累計量（日的資源需求總累計量（t日這一天的各開工日這一天的各開工工序所需總資源量工序所需總資源量)，橫道圖中的時間起點與終點均用，橫道圖中的時間起點與終點均用ES與與EF）2022-3-864

40、d(58)f(22)g(42)h(39)6070809010011012013014060708090100110120130140i(26)201830152520406080關鍵工序關鍵工序非關鍵工序非關鍵工序非關鍵工序非關鍵工序資源需求資源需求工序長度工序長度ttdfg ih 工序工序65808164426526橫道圖（橫道圖（a）資源負荷圖（資源負荷圖（b）58G02022-3-86564d(58)f(22)g(42)h(39)6070809010011012013014060708090100110120130140i(26)201830152520406080ttdfg ih 工序

41、工序6558426526橫道圖（橫道圖（a）資源負荷圖（資源負荷圖（b）G02022-3-866l解：3.對資源負荷圖(b)系統分析可知：G0=65(公司供給量)，=(ta,tb)，在1=(70,80)時段工程實際需求80人65人，在2=(70,80)時段工程實際需求81人65人，根據“削峰填谷”原則應將峰1與2中的非關鍵工序后移以填谷，注意到在二個峰期中1中d為關鍵工序，f為非關鍵工序。2中g為關鍵工序，h為非關鍵工序。 故將非關鍵工序f與h后移以填谷，從而可獲得橫道圖(c)及資源負荷圖(d),此中f與h的后移時段多少應視資源負荷的均衡程度為好。2022-3-867工序高峰期后移計算（見程序

42、框圖）工序高峰期后移計算（見程序框圖）工序工序 高峰期高峰期（ta,tb）A(t)G0tsLSTh(*)=LS-ts資源資源V(i,j)ES(*)后移后移f(70,80)8065801173722ES(f)=80h(100,110) 81651101201039ES(f)=1102022-3-868l解1.由資源負荷圖由資源負荷圖(d)及橫道圖及橫道圖(c)獲得經調整后各工序獲得經調整后各工序f,h的最早開工時間的最早開工時間ES(i,j)，最早結束時間，最早結束時間EF(i,j)對未調對未調整的工序之整的工序之ES(i,j)與與EF(i,j)仍用原網絡仍用原網絡G 圖之數據，圖之數據，可得如

43、下新網絡圖可得如下新網絡圖 。對。對 重新計算各網絡時間重新計算各網絡時間參數。最終仍可得工期參數。最終仍可得工期 2.當當G 后，由于后，由于 與與G有相同工期，且各時段之有相同工期，且各時段之資源負荷均小于供應量資源負荷均小于供應量G0且相對均衡，故且相對均衡，故END。GGG（天）170GGTTGe 60,100 40g(42人人)80,110 30i(26人人)110,135 25c60,70 10a0,60 60f(22人人)80,98 18j135,170 35 135,170d(58人人)60,80 201857643b 60,105 45h(39人人)110,125 15060

44、80801101101351702圖G2022-3-869l基本概念與符號（前述模型為后移工序的基本概念與符號（前述模型為后移工序的ES，以下模型為縮短工序長度，以下模型為縮短工序長度t(i,j)）u直接費用直接費用為加快工程進度需對關鍵工序新增為加快工程進度需對關鍵工序新增人力，設備和工作班次，從而需新增一筆投入人力，設備和工作班次，從而需新增一筆投入費用（作為獎金或設備購置費），此筆費用稱費用（作為獎金或設備購置費），此筆費用稱之為直接費用。之為直接費用。u間接費用間接費用管理人員的工資，辦公費用（出差管理人員的工資，辦公費用（出差費、用車費、復印費等）統稱為間接費用。通費、用車費、復印費

45、等）統稱為間接費用。通常當工序作業時間愈短，直接費用愈多，間接常當工序作業時間愈短，直接費用愈多，間接費用愈少。費用愈少。2022-3-870的最早開始時間結點的實際作業時間工序費用間縮短所需增加投入的為達到上述工序作業時）（所需費用最快完成工序所需費用正常完成工序入的直接費用提前單位工期需增加投縮短工序的直接費用變動率，為工序的實際提前時間工序作業時間的最大允許值縮短工序的最快完成時間完成工序路長的正常需要時間，此即完成工序ixjiyTCCCCjiCjiCTTCCKjijiKjiyjiTTjiTjitjiTiijijijijijijijijijijijijijijijijijijij),()

46、,(),(),(),(),(),(),(),(),(2022-3-871l目標：在給定工期T的約束下，求計劃網絡G各工序完成時間，以使因縮短工期而增加的直接費用達最小。GjiyjiTTxjiyTnixjixxTxxTTyyjiyKyTxxtsLPykfijijijijijiijnijijijijijijijijijGjiijij),(0),(0),(, 2 , 10),(),(.min111),(1，提前完工的最大提前量工序的實際作業時間工序，的時間間隔節點所需增加的直接費用時間提前完工工序此中2022-3-872正常（最慢）實際最快（最大）工序完成時間TijTij yij工序提前量0yij2

47、022-3-873l說明：1.優化模型僅考慮直接費用，未考慮間接費用，后述優化模型，則同時考慮直接費用與間接費用的綜合效果。2.上述LP模型之決策變量為yij，亦即僅考慮工序(i,j)的提前，而未考慮工序(i,j)是否關鍵，因此對上述優化模型求解后有可能改變關鍵路線，從而使實際總工期并未縮短，此時應重新建立優化模型求解。模型中的xj為中間變量（yi決定）3.由LP求得yij有 （工期提前量），但不一定有 （詳見下例14(2)）TyGjiij),(GjiijTy),(2022-3-874l例14：對例6的計劃網絡補充如下有關信息，以研究工期的提前性以及相應工序的提前量。1.若該工程按G 需170

48、天完成，現需要提前到150天完成，試求相應各工序的提前量。2.若該工程需提前到140天完工，試求相應各工序的提前量及應增加的費用投入。2022-3-875工序工序正常情況下（天）正常情況下（天）采取措施后（天）采取措施后（天） （元（元/天）天）（天）（天）提前量提前量yij提前量提前量的上限的上限正常完工正常完工時間時間Tij(t(i,j)正常下直正常下直接費用接費用Cij最快完最快完工時間工時間相應直接費相應直接費用用a(1,2)60100006010000-y120b(2,7)454500306300120y2715c(2,3)10280054300300y235d(2,4)207000

49、1011000400y2410e(2,5)40100003512500500y255f(3,7)183600105440230y378g(4,6)3090002012500350y4610h(5,7)153750105750400y575i(6,7)256250159150290y6710j(7,8)35120003512000-y7802022-3-876l解1：由優化模型思路有LP如下：GjiyTxxxnixyyTTyyyyyyyyyxfyxxjyxxeyxxiyxxdyxxyTxxhyxxcyxxxxbyxxgyxxayxxtsykfyyyyyyyyfijniijijijijijijGj

50、iijij),(01502 , 10058101555010100)(18)(35)(40)(25)(20)(15)(10)()(45)(30)(60.290400350230500400300120min118782337672725571224461373778782525676724245757232345272746461212),(167574637252423271虛工序）（2022-3-877f70,88 18j135,170 35i110,135 25g80,110 30d60,80 2012857643a0,60 60b0,60 45c60,70 10e 60,100 40h

51、100,115 150607080100110135170圖圖G（原網絡）（原網絡）2467860d20g30i25j35801101351701001151502015圖圖G1（經（經LP1優化后網絡）優化后網絡）2022-3-8780150101150100010008007000600006400),(5784673762552442337827267121*1yxyxyxyxyxyxyyxyyxyxff解優最利用軟件包求解 原計劃（未調整）網絡見右上圖 G，經上述優化后之網絡見右上G1結論結論：即縮短工序g與i各10天，其余工序長度不變，為此需付出的最少直接費用為6400元，這樣即可將

52、工期由原170天提前20天，即T=150天可完工。 GG（見上右圖G1）2022-3-879l(2) 將上述優化模型的最后一個約束x8140，其它均不變，則構成LP2，運用軟件包計算可得f1=14900元)(5140)(10105090)(595)(10700870060)(10005784673762552442337827267121hyxgyxyxeyxdyxyxyyxiyyx2022-3-880 f 18j35i25g30d2012857643a60 b 45c10e40h150607080100110135170圖圖G（原計劃網絡）（原計劃網絡） f 18j35i15g20d1012

53、857643a60 b 45c10e35h1006087709590105140圖圖G2（LP2優化后網絡）優化后網絡）2022-3-881l由上述求解結果知只要工序e，h提前5天d，g，i工序提前10天，其它工序完工時間不變，則可使整個工程在T=140天完成，此時需至少增加投入經費1.49萬元。此時有 ，對于上述LP2之結果 畫出網絡圖G2，對該G計算網絡時間參數，得知工程工期恰為140天，且四條路線均為關鍵路線。3040),(Tyjiij2022-3-882l解：（分析法）u由題設要求縮短工期20天（由170天提前到150天）完成工程。 根據統籌法原理：向關鍵工序要時間，故需從關鍵工序a，

54、d，g，i，j要時間，比較這五個關鍵工序的直接費用變動率（見下表）可知：工序i直接費用變動率最低，其次是工序 g，注意到直接費用變動率表中有約束如下：iy6710，gy4610，y120 (a)， y780 (j)（i，j工序無提前余地）。取上限有y67=10，y46=10，經由G1圖計算知恰有TG1=150天，此時需增加支出最少的直接費用為f1=35010+29010=6400元，此結果與解1（1）相同。2022-3-883CP1關鍵工序KijCP2關鍵工序Kija-0a-0d40010e5005g35010h4005i29010j-0j-0ijijTTijijTT2022-3-884l解：u若工程期限要求在140天完成（提前工期30天），根據向關鍵路線CP1：adgij要時間的原理，可根據上述(1)同理，可設想將關鍵