運(yùn)籌學(xué)

OperationsResearch2023/7/291

第7章網(wǎng)絡(luò)計劃第1節(jié)網(wǎng)絡(luò)計劃概述第2節(jié)網(wǎng)絡(luò)圖的繪制第3節(jié)關(guān)鍵路線法第4節(jié)計劃評審技術(shù)第5節(jié)網(wǎng)絡(luò)計劃優(yōu)化第6節(jié)緩沖時間設(shè)置2第1節(jié)

網(wǎng)絡(luò)計劃概述網(wǎng)絡(luò)計劃法(networkprogram,NP)也稱網(wǎng)絡(luò)計劃技術(shù),是利用網(wǎng)絡(luò)圖及其時間參數(shù)計算進(jìn)行生產(chǎn)組織與管理的一種方法。

網(wǎng)絡(luò)計劃技術(shù)的特性

反映和表達(dá)項目計劃安排的一種方法，是被項目施工技術(shù)所決定的，它只能適應(yīng)項目施工方法的要求。是把工程進(jìn)度安排通過網(wǎng)絡(luò)的形式直觀地反映出來。

網(wǎng)絡(luò)計劃的發(fā)展歷程

關(guān)鍵路線法(CriticalPathMethod，CPM

)關(guān)鍵路徑是指設(shè)計中從輸入到輸出經(jīng)過的延時最長的邏輯路徑。優(yōu)化關(guān)鍵路徑是一種提高設(shè)計工作速度的有效方法。計劃評審技術(shù)(ProgramEvaluationandReviewTechnique，PERT

)利用網(wǎng)絡(luò)分析制定計劃以及對計劃予以評價的技術(shù)。它能協(xié)調(diào)整個計劃的各道工序，合理安排人力、物力、時間、資金，加速計劃的完成。PERT被廣泛地使用，是現(xiàn)代項目管理的重要手段和方法。

2023/7/2945圖示評審技術(shù)(GraphicEvaluationandReviewTechnique，GERT

)在PERT的基礎(chǔ)上，增加決策節(jié)點，不僅將活動的各參數(shù)如時間和費(fèi)用設(shè)為隨機(jī)性分布，而且其各個活動及相互之間的影響關(guān)系也具有隨機(jī)性。該方法通過解析方法及蒙特卡羅模擬方法，最終求出項目成本和工期的概率分布曲線。圖形評審技術(shù)是項目時間管理的術(shù)語。風(fēng)險評審技術(shù)(VentureEvaluationReviewTechnique，VERT

)是一種以管理系統(tǒng)為對象，以隨機(jī)網(wǎng)絡(luò)仿真為手段的風(fēng)險定量分析技術(shù)。2023/7/295我國，是從20世紀(jì)60年代開始運(yùn)用網(wǎng)絡(luò)計劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國實際，在吸收國外網(wǎng)絡(luò)計劃技術(shù)理論的基礎(chǔ)上，將CPM、PERT、GERT、VERT等方法統(tǒng)一定名為統(tǒng)籌法。統(tǒng)籌方法包括繪制計劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。2023/7/296運(yùn)籌學(xué)--緒論--緒論--緒論--緒論第2節(jié)

網(wǎng)絡(luò)圖的繪制工序(作業(yè))：一項需要人財物或時間等資源的相對獨(dú)立的活動過程在網(wǎng)絡(luò)圖中用箭線“→”

表示，前面直接相連工序稱緊前工序，直接相連的后繼工序為緊后工序。

結(jié)點(事項)：相鄰工序的分界點一般用圓圈來表示，每個結(jié)點編上順序號，結(jié)點既不消耗人力、物力，也不占用時間。7網(wǎng)絡(luò)圖由工序、結(jié)點及時間參數(shù)所構(gòu)成的有向圖即為網(wǎng)絡(luò)圖。

箭線表示工序,結(jié)點為工序間相互關(guān)系的網(wǎng)絡(luò)圖，稱箭線式網(wǎng)絡(luò)結(jié)點表示工序,箭線為工序間相互關(guān)系的網(wǎng)絡(luò)圖，稱結(jié)點式網(wǎng)絡(luò)2023/7/298運(yùn)籌學(xué)--緒論--緒論--緒論--緒論1.箭線式網(wǎng)絡(luò)圖

21A25B343C55D5Et－作業(yè)時間iN－作業(yè)名稱j2.結(jié)點式網(wǎng)絡(luò)圖

t－作業(yè)時間N－作業(yè)名稱iNti－作業(yè)序號122543355560工序表示的規(guī)定一條箭線和它的相關(guān)結(jié)點只能代表一道工序，不能代表多道工序，

兩個結(jié)點之間只能有一條箭線相連。不允許出現(xiàn)缺口與回路網(wǎng)絡(luò)圖中只能有一個始點和一個終點，使得自網(wǎng)絡(luò)圖的始點經(jīng)由任何路徑都可以到達(dá)終點。

虛工序虛工序是為了表達(dá)相鄰工序之間的邏輯關(guān)系而虛設(shè)的工序。不消耗時間、費(fèi)用和資源，一般用虛箭線表示。ij10方向的規(guī)定網(wǎng)絡(luò)圖是有方向的，工序應(yīng)按工藝流程順序或工作邏輯關(guān)系從左向右排列。編號的規(guī)定編號應(yīng)從始結(jié)點開始，按照時序依次從小到大對結(jié)點編號，直到終結(jié)點。

編號時不允許箭頭編號小于箭尾編號。

節(jié)點標(biāo)號：j>iij2023/7/2911某工程的工序一覽表

工序abcdefg緊前工序----a,bac,dae,f工序時間4235556例7-112

例7.1某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請畫出其網(wǎng)絡(luò)計劃圖。工序代號所需時間（天）緊前工序abcdefgh60151338810165－aacb，ｄdde，ｆ，6015bec13d388h510f6g14第3節(jié)

關(guān)鍵路線法關(guān)鍵路線法是在網(wǎng)絡(luò)圖的基礎(chǔ)上，通過計算時間參數(shù)，確定關(guān)鍵路線，從而對工程項目進(jìn)行更有效的協(xié)調(diào)與計劃。關(guān)鍵路線法適用于常規(guī)性生產(chǎn)項目的計劃安排，各項工作重復(fù)性發(fā)生，有確定的操作規(guī)程和時間定額，有較完備的統(tǒng)計資料。關(guān)鍵路線法相當(dāng)于經(jīng)常說到的“確定型模型”。15一、結(jié)點的時間參數(shù)

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

。結(jié)點的最遲時間

tL(j)指以該結(jié)點為結(jié)束的各道工序最遲必須完工的時刻，否則將會影響后續(xù)工序按時開工，以至推遲整個工程的完工時間。從終點開始，從右向左，逆箭線方向逐個計算。1617二、工序的時間參數(shù)

最早開工時間tES(i,j)一個作業(yè)必須在其各緊前作業(yè)都完工后才能開工，作業(yè)最早可能開工時間等于其箭尾事項的最早時間。

tES(i,j)=

tE(i)最早完工時間

tEF(i,j)從最早可能開工時間開工，完成本作業(yè)的時間

。

tEF(i,j)=tES(i,j)+t(i,j)工序a的最早開始時間工序a的最早完成時間ija[0，60]6018最遲完工時間

tLF(i,j)在不影響工程如期完工的前提下，作業(yè)最遲必須完工的時刻

。

tLF(i,j）=tL(j)

最遲開工時間

tLS(i,j)在不影響工程如期完工的前提下，作業(yè)最遲必須開工的時刻。等于它的箭頭事項的最遲時間減去本作業(yè)的作業(yè)時間

tLS(i,j)=tL(j)-t(i,j)工序a的最晚開始時間工序a的最晚完成時間ij[0，60]a2023/7/29192023/7/2920三、時差與關(guān)鍵路線

總時差R(i,j)：不影響其緊后工序最遲開工的前提下，本工序最早可能完工時間可以推遲的時間。R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)單時差r(i,j)：不影響其緊后工序最早開工的前提下，本工序最早可能完工時間可以推遲的時間。r(i,j)=tES(j,k)-tEF(i,j)總時差為零的工序稱為關(guān)鍵工序；關(guān)鍵工序組成關(guān)鍵路線。212023/7/2922四、時間參數(shù)計算

作業(yè)t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)r(i,j)關(guān)鍵作業(yè)abcdefg23第4節(jié)

計劃評審技術(shù)實際工作中，許多工程項目的工序時間是不確定的或者是由于隨機(jī)因素的影響或者是屬于開拓性的工作，沒有經(jīng)驗數(shù)據(jù)或統(tǒng)計資料很難確定工序時間，這時便不宜采用關(guān)鍵路線法采用計劃評審技術(shù)，對工序時間進(jìn)行粗略的估計，而后繪制網(wǎng)絡(luò)圖，找出關(guān)鍵路線，并可對工程工期進(jìn)行概率估計24一、作業(yè)時間估計

工序時間（β分布）的三種可能估計：最樂觀時間：在最理想的情況下完成工序所需時間a；最悲觀時間：在最不利的情況下完成工序所需時間b；最可能時間：在正常情況下完成工序所需時間m。加權(quán)平均就是工序時間t25期望工期等于關(guān)鍵路線上各道工序的時間之和

。設(shè)規(guī)定的工程完工時間為Tk，則完工時間的概率為二、計算期望工期

2023/7/2926例7-2某項目的作業(yè)及相關(guān)時間如表。求項目的最短期望工期；若合同規(guī)定工期為17，求如期完成的概率；若要求有90%的把握如期完成，求可接受的合同工期。作業(yè)緊前作業(yè)樂觀時間悲觀時間可能時間期望方差abcdefg----a,bac,dae,f312233453410119124234.544.552023/7/29272023/7/2928第5節(jié)

網(wǎng)絡(luò)計劃優(yōu)化一、縮短工程工期①改進(jìn)工藝和技術(shù)裝備，壓縮關(guān)鍵工序的作業(yè)時間②合理組織平行作業(yè)、交叉作業(yè)平行作業(yè)指兩道以上相互獨(dú)立的工序同時進(jìn)行交叉作業(yè)指將緊前工序完成的部分任務(wù)分期分批地轉(zhuǎn)入下道工序③利用時差，合理調(diào)配資源等途徑實現(xiàn)總時差不影響最短工期，但影響后續(xù)工序的自由時間。單時差不影響后續(xù)工序。29把串聯(lián)工作改為平行工作或平行交叉工作2023/7/2930二、工期-費(fèi)用優(yōu)化工期與成本之間關(guān)系工期的縮短與費(fèi)用是密切相關(guān)的工程費(fèi)用最低的完工時間(最低成本日程)時間費(fèi)用極限完工時間正常完工時間直接費(fèi)用間接費(fèi)用最優(yōu)完工時間工程總費(fèi)用31直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。2023/7/2932運(yùn)籌學(xué)--線性規(guī)劃尋求最低成本日程的思路：從網(wǎng)絡(luò)計劃的關(guān)鍵工序著手，對增加直接費(fèi)用做少的某些關(guān)鍵工序采取措施，縮短其作業(yè)時間。時間直接費(fèi)用極限完工時間正常完工時間33完成工序j的正常所需時間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時間為T`j,直接費(fèi)用為c`j?？s短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動率（成本斜率）。有34某工程作業(yè)流程及其費(fèi)用統(tǒng)計資料

作業(yè)緊前作業(yè)作業(yè)時間（天）作業(yè)直接費(fèi)用（萬元）費(fèi)率正常完工極限完工正常完工極限完工a-438124b-2116171ca,b322021.21.2da5210131ec,d5315192fa5310121ge,f649174合計88間接費(fèi)用2萬元/天例7-335方案I：各道作業(yè)正常完工工程費(fèi)用=正常完工直接費(fèi)用+間接費(fèi)用=88+2×20=128萬元。

[0,4][0,4][0,2][4,7][4,9][9,14][14,20][4,9][14,20][9,14][9,14][4,9][6,9][4,6]2023/7/2936方案2：關(guān)鍵路線a→d→e→g上趕進(jìn)度

考慮關(guān)鍵工序可壓時間、費(fèi)用變動率非關(guān)鍵路線總時差為4、2、5，故趕2天。工程費(fèi)用=正常完工直接費(fèi)用+趕進(jìn)度增加的直接費(fèi)用+間接費(fèi)用

=88+2×1+2×18=126萬元。[0,4][0,4][0,2][4,7][4,9][9,14][14,20][4,9][14,20][9,14][9,14][4,9][6,9][4,6]37方案3：關(guān)鍵路線a→d→e→g，a→c→e→g上趕進(jìn)度

考慮關(guān)鍵工序可壓時間、費(fèi)用變動率非關(guān)鍵路線總時差為2、3，故趕2天。工程費(fèi)用=正常完工直接費(fèi)用+趕進(jìn)度增加的直接費(fèi)用+間接費(fèi)用

=88+2×1+2×2+2×16=126萬元。[0,4][0,4][0,2][4,7][4,7][7,12][12,18][4,9][12,18][7,12][7,12][4,7][4,7][2,4]38方案4：關(guān)鍵路線a→d→e→g，a→c→e→g上趕進(jìn)度各趕1天工程費(fèi)用=正常完工直接費(fèi)用+趕進(jìn)度增加的直接費(fèi)用+間接費(fèi)用

=88+2×1+2×1.5+1×(1+1.2)+2×15=126.2萬元。[0,4][0,4][0,2][4,7][4,7][7,10][10,16][4,9][10,16][5,10][7,10][4,7][4,7][2,4]39線性規(guī)劃法S.t.xj-xiTij-yij,對一切?。╥,j)yijTij-T`ij,對一切?。╥,j)xn-x1T,

xi0，yij0。提前完工時間為yijTij,T`ij分別表示正常完工時間與最快完工的時間實際完工時間為：Tij-yij

40三、工期-資源優(yōu)化資源平衡準(zhǔn)則：考量每道作業(yè)所需資源的用量與供應(yīng)能力，安排進(jìn)度。通過平衡資源，取得工期與資源的最優(yōu)配置優(yōu)先保證關(guān)鍵路線上關(guān)鍵作業(yè)對資源的需求量。對非關(guān)鍵作業(yè)要資源，利用時差調(diào)整非關(guān)鍵作業(yè)的開工/完工時間，拉平資源需要量的高峰。當(dāng)資源絕對受限制時，在保證不推遲或盡量少推遲工期的前提下，全面統(tǒng)籌安排，最大限度地利用資源。41每天只有13臺設(shè)備可用，工期20天，試合理安排進(jìn)度工序abcdefg緊前工序----a,bac,dae,f作業(yè)時間4235556每天所需設(shè)備數(shù)137856712例7-4[0,4][0,4][0,2][4,7][4,9][9,14][14,20][4,9][14,20][9,14][9,14][4,9][6,9][4,6](1)制定初始方案以最早開工時間，安排初始進(jìn)度如表

43(2)調(diào)整開工時間44第六節(jié)

緩沖時間設(shè)置“學(xué)生綜合癥”是人的一種普遍行為“還早呢，急什么？”

■考試，“臨陣磨槍”寫作，不到時候不動筆

■任務(wù)，不急不辦對管