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

運籌帷幄之中決勝千里之外運籌學(xué)課件網(wǎng)絡(luò)方案技術(shù)NetworkProgramTechnique1整理課件第十章網(wǎng)絡(luò)方案技術(shù)網(wǎng)絡(luò)方案技術(shù)1957年，美國杜邦公司運用網(wǎng)絡(luò)方案技術(shù)來統(tǒng)籌各項工作，并找出編制與執(zhí)行方案的關(guān)鍵路線，稱為關(guān)鍵路線法(CriticalPathMethod)，簡稱CPM。1958年，美國海軍武器局在制定研制“北極星〞導(dǎo)彈方案時，開發(fā)出了方案評審技術(shù)(ProgramEvaluationandReviewTechnique)，簡稱PERT。1962年產(chǎn)生了能夠表達隨機因素作用的圖示評審技術(shù)(GraphicEvaluationandReviewTechnique)，簡稱GERT。20世紀70年代，美國G.L.穆勒等人，在GERT根底上提出了風(fēng)險評審技術(shù)(VentureEvaluationReviewTechnique)，簡稱VERT。這些技術(shù)方法均以網(wǎng)絡(luò)描述工序及工序之間的關(guān)系。2整理課件第一節(jié)網(wǎng)絡(luò)圖及其繪制規(guī)那么工序一項需要人力、物力或時間等資源的相對獨立的活動過程，又稱作業(yè)；在網(wǎng)絡(luò)圖中用箭線“→〞表示；與某道工序前面直接相連的工序稱為緊前工序；其后直接相連的后繼工序為緊后工序。結(jié)點(事項)結(jié)點(事項)是相鄰工序的分界點；一般用圓圈來表示，每個結(jié)點編上順序號：箭尾結(jié)點表示工序的開始，箭頭結(jié)點表示工序的完成。結(jié)點(事項)既不消耗人力、物力，也不占用時間。網(wǎng)絡(luò)圖由工序、事項及時間參數(shù)〔工序時間〕所構(gòu)成的賦權(quán)有向圖即為網(wǎng)絡(luò)圖。用箭線表示工序，結(jié)點表示工序間相互關(guān)系的網(wǎng)絡(luò)圖，稱箭線式網(wǎng)絡(luò)圖。一、網(wǎng)絡(luò)圖的概念

3整理課件第一節(jié)網(wǎng)絡(luò)圖及其繪制規(guī)那么工序表示的規(guī)定一條箭線和它的相關(guān)事項只能代表一道工序，不能代表多道工序，兩個結(jié)點之間只能有一條箭線相連。不允許出現(xiàn)缺口與回路網(wǎng)絡(luò)圖中只能有一個始點和一個終點，使得自網(wǎng)絡(luò)圖的始點經(jīng)由任何路徑都可以到達終點。虛工序虛工序是為了表達相鄰工序之間的邏輯關(guān)系而虛設(shè)的工序。不消耗時間、費用和資源，一般用虛箭線表示。方向的規(guī)定

網(wǎng)絡(luò)圖是有方向的，工序應(yīng)按工藝流程順序或工作的邏輯關(guān)系從左向右排列。編號的規(guī)定編號應(yīng)從始結(jié)點開始，按照時序依次從小到大對結(jié)點編號，直到終結(jié)點。編號時不允許箭頭編號小于箭尾編號。二、繪制網(wǎng)絡(luò)圖的規(guī)那么4整理課件第一節(jié)網(wǎng)絡(luò)圖及其繪制規(guī)那么某工程的工序一覽表如下，試繪制網(wǎng)絡(luò)圖。工序緊前工序a--b--c--da,bea,cfa,b,c123abc4def565整理課件第二節(jié)關(guān)鍵路線法關(guān)鍵路線法是在網(wǎng)絡(luò)圖的根底上，通過計算時間參數(shù)，確定關(guān)鍵路線，從而對工程工程進行更有效的協(xié)調(diào)與方案。關(guān)鍵路線法適用于常規(guī)性生產(chǎn)工程的方案安排，各項工作重復(fù)性發(fā)生，有確定的操作規(guī)程和時間定額，有較完備的統(tǒng)計資料。關(guān)鍵路線：網(wǎng)絡(luò)中所有路線最長的路線。6整理課件第二節(jié)關(guān)鍵路線法結(jié)點的最早時間tE(j)

結(jié)點j的最早時間tE(j)指以該事項為始點的各道工序的最早開始時間，等于從始點開始到本結(jié)點的最長路線上各道工序時間之和。從始點事項開始，自左向右，順著箭線方向逐個計算。一、結(jié)點(事項)的時間參數(shù)計算

結(jié)點的最遲時間tL(j)指以該事項為結(jié)束的各道工序最遲必須完工的時刻，否那么將會影響后續(xù)工序按時開工，以至推遲整個工程的完工時間。從終點開始，從右向左，逆箭線方向逐個計算。7整理課件第二節(jié)關(guān)鍵路線法計算結(jié)點時間參數(shù)，確定關(guān)鍵路線。1234564a3b6c5d8e10f046461616666608整理課件第二節(jié)關(guān)鍵路線法工序最早可能開工時間tES(i,j)一個工序必須在其各緊前工序都完工后才能開工，工序最早可能開工時間等于其箭尾事項的最早時間。tES(i,j)=tE(i)工序最早可能完工時間tEF(i,j)從最早可能開工時間開工，完本錢工序的時間。tEF(i,j)=tES(i,j)+t(i,j)工序最遲必須開工時間tLS(i,j)在不影響工程如期完工的前提下，工序最遲必須開工的時刻。等于它的箭頭事項的最遲時間減去本工序的作業(yè)時間tLS(i,j)=tL(j)-t(i,j)工序最遲必須完工時間tLF(i,j)從最遲必須開工時間開工，完本錢工序的時間。tLF(i,j)=tLS(i,j)+t(i,j)=tL(j)二、工序的時間參數(shù)計算

9整理課件第二節(jié)關(guān)鍵路線法時差又稱機動時間或?qū)捲r間在不影響如期完成任務(wù)的條件下，各道工序可以機動使用的一段時間。工序總時差R(i,j)

在不影響整個工程最早完工日期的前提下，本工序最早可能完工時間可以推遲的時間，稱為工序的總時差。R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)=tL(j)-tE(i)-t(i,j)三、時差與關(guān)鍵路線

10整理課件第二節(jié)關(guān)鍵路線法工序單時差r(i,j)在不影響其緊后工序最早可能開工的前提下，本工序最早可能完工時間可以推遲的時間。r(i,j)=tE(j)-tE(i)-t(i,j)關(guān)鍵路線確實定總時差為零的工序稱為關(guān)鍵工序，關(guān)鍵工序組成的路線就是關(guān)鍵路線。tES(A)tEF(A)tLS(A)tLF(A)tES(B)tEF(B)tLS(B)tLF(B)R(i,j)r(i,j)11整理課件第二節(jié)關(guān)鍵路線法計算時間參數(shù)1234564a3b6c5d8e10f04646161666660工序t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)r(i,j)關(guān)鍵工序a4b3c6d5e8f10000466436914166661616162301186230720010720cf12整理課件第三節(jié)方案評審技術(shù)實際工作中，許多工程工程的工序時間是不確定的，或者是由于隨機因素的影響，或者是屬于開拓性的工作，沒有經(jīng)驗數(shù)據(jù)或統(tǒng)計資料，很難確定工序時間，這時便不宜采用關(guān)鍵路線法。采用方案評審技術(shù)，對工序時間進行粗略的估計，而后繪制網(wǎng)絡(luò)圖，找出關(guān)鍵路線，并可對工程完工期進行概率估計。13整理課件第三節(jié)方案評審技術(shù)工序時間的三種可能估計：

最樂觀時間：在最理想的情況下完成工序所需時間a；最悲觀時間：在最不利的情況下完成工序所需時間b；最可能時間：在正常情況下完成工序所需時間m。加權(quán)平均就是工序時間t一、工序時間估計

二、工期估計

工程期望工期等于關(guān)鍵路線上各道工序的時間之和。設(shè)規(guī)定的工程完工時間為Tk，那么完工時間的概率為14整理課件第三節(jié)方案評審技術(shù)三、應(yīng)用舉例假設(shè)合同規(guī)定工期為20，如期完工的概率？要求90%的把握如期完工，可接受的合同工期？工序緊前工序作業(yè)時間估計樂觀時間悲觀時間可能時間a--354b--243ca,b132da3114ec,d2109fa71310ge,f2106作業(yè)時間均值方差41/931/921/9516/9816/9101616/915整理課件第三節(jié)方案評審技術(shù)繪制網(wǎng)絡(luò)圖1234a3b2c45d8e10f566g0449172323179740參數(shù)計算工程期望工期TE=23，關(guān)鍵工序的方差2=49/9，那么(x)=-1.29，查表知P(x)=9.9%P(x)=90%，查表知(x)=1.3，那么可接受的合同工期為TE+(x)=2616整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化縮短工程時間①改進工藝和技術(shù)裝備，壓縮關(guān)鍵工序的作業(yè)時間；②合理組織平行作業(yè)、交叉作業(yè)；平行作業(yè)指兩道以上相互獨立的工序同時進行。交叉作業(yè)指將緊前工序完成的局部任務(wù)分期分批地轉(zhuǎn)入下道工序。③利用時差，合理調(diào)配資源等途徑實現(xiàn)。17整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化時間—費用優(yōu)化在時間進度優(yōu)化中，重點在于如何縮短工期，工期的縮短與費用是密切相關(guān)的，網(wǎng)絡(luò)方案的優(yōu)化中，應(yīng)考慮不同的完工時間所對應(yīng)的工程費用，找到工程費用最低的完工時間(最低本錢日程)。時間費用極限完工時間正常完工時間直接費用間接費用最優(yōu)完工時間工程總費用18整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化尋求最低本錢日程的思路：從網(wǎng)絡(luò)方案的關(guān)鍵工序著手，對增加直接費用做少的某些關(guān)鍵工序采取措施，縮短其作業(yè)時間。時間直接費用極限完工時間正常完工時間19整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化例工序緊前工序作業(yè)時間(天)工序的直接費用(元)費率正常完工極限完工正常完工極限完工A--33800800--B--5316001900150CA7320002800200DB6320002300100EB52500860120FE3310001000--GD439001100200合計8800間接費用200元/天20整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化方案I：正常完工1233a5b6d47c4g5e563f035111015151211580工程費用C(I)=正產(chǎn)完工直接費用+間接費用=8800+200×15=11800元21整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化方案II：在關(guān)鍵路線上趕進度趕進度的工序：關(guān)鍵工序d趕單位時間進度增加的直接費用最少，選擇工序d趕緊度；趕進度的時間：工序d最多只能趕3天，非關(guān)鍵路線時差為2和5，故工序d只能趕2天。1233a5b4d47c4g5e563f0359101313109560工程費用C(II)=正產(chǎn)完工直接費用+趕進度增加的直接費用+間接費用=8800+2×100+200×13=11600元22整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化方案III：在關(guān)鍵路線上趕進度趕進度的工序：關(guān)鍵工序b趕單位時間進度增加的直接費用最少，選擇工序b趕緊度；趕進度的時間：工序b最多只能趕2天，非關(guān)鍵路線時差為3，故工序b只能趕2天。1233a3b4d47c4g5e563f03378111187340工程費用C(III)=正產(chǎn)完工直接費用+趕進度增加的直接費用+間接費用=8800+2×100+2×150+200×11=11500元23整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化方案IV：在關(guān)鍵路線上趕進度趕進度的工序：選擇工序d,e同時各

趕緊度；趕進度的時間：工序d最多只能趕1天，故工序d,e只能同時各趕1天。1233a3b3d47c4g4e563f03367101076330工程費用C(IV)=正產(chǎn)完工直接費用+趕進度增加的直接費用+間接費用=8800+2×100+2×150+1×(100+120)+200×10=11520元24整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化時間—資源優(yōu)化在一定工期下，通過平衡資源，取得工期與資源的最優(yōu)配置。平衡原那么：優(yōu)先保證關(guān)鍵路線上關(guān)鍵工序?qū)Y源的需求量。向非關(guān)鍵工序要資源，利用時差調(diào)整非關(guān)鍵工序的開工時間，到達與其它工序在占用資源的時間上錯開，拉平資源需要量的頂峰。例，某工程工序一覽表如下，每天只有13人上班，方案10天內(nèi)完成，試合理安排生產(chǎn)。工序abcdefg緊前工序----aab,ce,da作業(yè)時間3123415每天所需人理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化工程所需工作日：3×13+1×5+2×8+3×2+4×6+1×12+5×5=12710天內(nèi)完成，那么平均每天所需人力12.7現(xiàn)有人力13人，適當(dāng)安排各工序的開工和完工，10天可以完成工程。1233a1bc245d8e10f56g03591010953026整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化工序相關(guān)結(jié)點作業(yè)時間最早開工時間總時差工程進度12345678910a①

②300b①

③104c②

③230d②

④333e③

④450f④

⑤190g②

⑤532每天所需人數(shù)合計13131358822266661255555181313151513111161227整理課件第四節(jié)網(wǎng)絡(luò)方案的優(yōu)化調(diào)整非關(guān)鍵工序開工時間