應(yīng)用運籌學(xué)-8- 網(wǎng)絡(luò)計劃- 2015

第五章網(wǎng)絡(luò)計劃 網(wǎng)絡(luò)圖 時間參數(shù)的計算 網(wǎng)絡(luò)計劃的優(yōu)化關(guān)鍵路線法，CPM(criticalpathmethod)計劃評審法，PERT(programevaluation&reviewtechnique)統(tǒng)籌法的基本原理從需要管理的任務(wù)的總進度著眼，以任務(wù)中各工作所需的工時為時間因素，按工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實現(xiàn)管理過程的模型化。進行時間參數(shù)計算，找出計劃中的關(guān)鍵工作和關(guān)鍵路線，對任務(wù)的各項工作所需的人、財、物通過改善網(wǎng)絡(luò)計劃作出合理安排，得到最優(yōu)方案并付諸實施。對各種評價指標進行定量分析，在計劃實施過程中，進行有效的監(jiān)督與控制，以保證任務(wù)優(yōu)質(zhì)優(yōu)量地完成。簡介項目：一系列特定的能自行控制的工作，有明確的起始與結(jié)束時間。項目管理：計劃、組織和控制資源（人員、設(shè)備和物料），使其滿足項目的技術(shù)、成本和時間等要求。項目控制報告機制：項目進展的信息收集處理系統(tǒng)。甘特圖、成本分解圖、時間進度表…組織機制：項目的組織形式。組織結(jié)構(gòu)（職能、矩陣）、項目經(jīng)理、…項目管理背景網(wǎng)絡(luò)計劃制定的條件組成項目的各項活動都可以作為實體加以識別（有清晰的開始和結(jié)束時間，相互獨立）項目活動序列的關(guān)系可以被確定和網(wǎng)絡(luò)化存在資源調(diào)整的可能性網(wǎng)絡(luò)計劃的編制工程任務(wù)分析（工序劃分、關(guān)系及時間估計）繪制網(wǎng)絡(luò)圖形（實、虛箭線、節(jié)點、線路）計算時間參數(shù)（最早、最晚開始與結(jié)束時間）確定關(guān)鍵路線（總時差為零的工序為最長路線）網(wǎng)絡(luò)優(yōu)化調(diào)整（工期、時間－費用、資源分析）項目網(wǎng)絡(luò)計劃網(wǎng)絡(luò)圖的構(gòu)成實箭線：表示一道具體的工序。箭頭方向表示工序進行方向，箭尾位置表示工序開始，箭頭位置表示工序結(jié)束。虛箭線：表示一道虛工序，虛工序僅僅表示工序與工序之間的關(guān)聯(lián)關(guān)系，不需要消耗時間和資源。工序名稱或代碼工序時間工序名稱或代碼網(wǎng)絡(luò)圖繪制1網(wǎng)絡(luò)圖的構(gòu)成節(jié)點：又稱事項、事件等。表示一個工序的開始或結(jié)束。用圓圈表示，在圈內(nèi)注上該節(jié)點的序號。整個網(wǎng)絡(luò)圖的開始事項稱起始節(jié)點，最后工序結(jié)束事項為結(jié)束節(jié)點。只有當某一節(jié)點的所有緊前工序都完成后，它的緊后工序才能開始.（A是B的緊前工序，B是A的緊后工序）路線：從起始節(jié)點沿箭頭方向連續(xù)不斷地到達終點的通路。路線有多條，路線的長度為各工序的時間和，最長的為關(guān)鍵路線。23AB網(wǎng)絡(luò)圖繪制繪制網(wǎng)絡(luò)圖的準備工作確定目標：以時間要求還是資源費用要求為主工程分解：列出全部分解后的工序及代號清單工序關(guān)系：確定每一道工序的緊前工序是哪些工序時間：確定每一道工序的完成所需的時間一時估計法：僅估計一個完成工序的最大時間D三時估計法：樂觀時間a、悲觀時間b、最可能時間m網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制規(guī)則方向、時序與節(jié)點編號

網(wǎng)絡(luò)圖是有向圖，按流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡(luò)圖中的各個節(jié)點都有一個時間（某一個或若干個工序開始或結(jié)束時間），一般按節(jié)點的時間順序編號（從左到右，從上到下），箭尾節(jié)點編號應(yīng)小于箭頭節(jié)點編號。始節(jié)點編號為1。網(wǎng)絡(luò)圖中不能出現(xiàn)缺口和回路二個節(jié)點之間只能有一個直接的工序

兩條箭線不能有同樣的始末節(jié)點，若二個事項之間有幾個平行進行的工序，不許直接連接，而需要引入虛工序。

網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制規(guī)則平行作業(yè)

有幾個工序平行作業(yè)結(jié)束后轉(zhuǎn)入下一個工序的情況下，考慮到計算網(wǎng)絡(luò)時間的方便，選擇在平行作業(yè)的幾個工序中所需時間最長的一個工序，直接與其緊后工序銜接，而其它工序則通過虛工序與其緊后工序銜接。交叉作業(yè)

對需要較長時間才能完成的一些工序，在工藝流程與生產(chǎn)組織條件允許的情況下，可以不必等待工序全部結(jié)束后再轉(zhuǎn)入其緊后工序，而是分期分批的轉(zhuǎn)入。分批轉(zhuǎn)入時需增加虛工序。網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制規(guī)則始點和終點

為表示工程的開始和結(jié)束，在網(wǎng)絡(luò)圖中只能有一個始點和一個終點。當工程開始時有幾個平行工序或結(jié)束時有幾個平行工序，而又不能用一個始節(jié)點或一個終節(jié)點表示時，需用虛工序把它們與始節(jié)點或終節(jié)點連接。網(wǎng)絡(luò)圖布局

盡可能將關(guān)鍵線路布置在中心位置，盡量將聯(lián)系緊密的工作布置在相近的位置；盡量用水平線或具有一段水平線的折線。網(wǎng)絡(luò)圖繪制6554虛工序應(yīng)用12AB321ABDCB4A213網(wǎng)絡(luò)圖繪制虛工序應(yīng)用12AB321ABDCBA5213546DCBA2143網(wǎng)絡(luò)圖繪制13212A12435A3A2A1444BBA:修路基B:鋪軌道A=A1+A2+A3B=B1+B2+B31212178642A1B2B1A3A2B35364312A1B2B1A3A2B35網(wǎng)絡(luò)圖繪制例5.1某化工廠管道安裝的工程進度表:網(wǎng)絡(luò)圖繪制例5.1某化工廠管道安裝的網(wǎng)絡(luò)圖先畫出沒有緊前工序的工作A,在A后畫出緊前工序為A的各工作,即B,C,E,F。ABCEF網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制在表中查出B,C為D的緊前工序，F(xiàn)為G的緊前工序，則在F工序后畫出G，在B,C工序后面畫出D。GDABCEF網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制畫出H,I,J的工序如下：ABCEFGDHIJH緊前：D、E、GI緊前：D、EJ緊前：H、IH除J外已沒有緊后工序網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制畫出K,L工序，K,L的緊前工序均為J。ABCEFGDHIJLK網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制在K,L后畫出M,N,P：ABCEFGDHIJLKNMPM緊前：K、LN緊前：KP緊前：M、N網(wǎng)絡(luò)圖繪制練習(xí)：畫出以下網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖繪制練習(xí)答案：15387642AHELKGDFCB60451810204015302535網(wǎng)絡(luò)圖繪制符號約定

iE(i)L(i)S(i)jE(j)L(j)S(j)KD(i,j)LFijEFijLSijESijE(1)=0L(j)E(j)L(n)=E(n)SijRij時間參數(shù)計算節(jié)點（事項）時間

節(jié)點本身不占用時間，它只表示某項工作應(yīng)在某一時刻開始或結(jié)束，因此，節(jié)點參數(shù)主要只有兩個：最早實現(xiàn)時間（最早時間）和最遲實現(xiàn)時間（最遲時間）。最早時間：以該節(jié)點結(jié)束的工作最早可能結(jié)束的時間，或以該節(jié)點開始的工作最早可能開始的時間。E(1)=0,E(n)為工程時間，從左往右計算。最遲時間：允許所有后續(xù)工序都能及時開始的最晚時間。L(n)=E(n),L(1)=0，從右往左計算。時間參數(shù)計算節(jié)點（事項）時間計算節(jié)點最早時間E(j)的計算E(1)=0E(j)=max[E(i)+D(i,j)],i=2,3,4,……98767E(7)=5E(8)=6E(9)=MAX[E(7)+6,E(8)+7)]=13時間參數(shù)計算節(jié)點（事項）時間計算節(jié)點最遲時間L(i)的計算L(n)=E(n)L(i)=MIN[L(j)-D(i,j)],j=n-1,n-2,……911102012L(10)=70L(11)=89L(9)=MIM[L(10)-20,L(11)-12)]=50時間參數(shù)計算543561267243EDCBAF1點的開始時刻為0；2點的最早時間為2；3點的最早時間為5；4點的最早時間為6；5點的最早時間為12；6點的最早時間為19；6點的最遲時間為19；5點的最遲時間為12；3點的最遲時間為7；4點的最遲時間為6；2點的最遲時間為2；1點的最遲時間為0。

00

22

1212

5

7

191966例5.2節(jié)點時間計算工序時間參數(shù)計算

一個工序可以從箭尾節(jié)點的最早時間開始作業(yè)，也可以適當推遲開始，但須在箭頭節(jié)點的最遲時間內(nèi)完工才不至于延誤后續(xù)工序，因此工序時間就包括最早開始時間和最遲開始時間，加上或減去該工序的作業(yè)時間，相應(yīng)地還有最早結(jié)束時間和最遲結(jié)束時間。最早開始時間:ESij=E(i)最早結(jié)束時間：EFij=ESij+D(i,j)最遲結(jié)束時間：LFij=L(j)最遲開始時間：LSij=LFij-D(i,j)時間參數(shù)計算時差及計算節(jié)點時差：最遲與最早時間差

S(i)=L(i)－E(i)工序總時差：不影響工期(最早結(jié)束時間）的該工序可松動的時間（可以推遲開始的時間）.Sij=LSij－ESij=LFij－EFij

=L(j)－E(i)－D(i,j)（總浮動）工序單時差：不影響緊后工序最早可能開始條件下，工序最早可能完工時間可以推遲的時間.Rij=E(j)－EFij（自由浮動）時間參數(shù)計算工序及時差關(guān)系工序AES工序A的緊后工序ESEFLFLFEFLSLS總時差SA單時差RA(自由浮動)D時間參數(shù)計算關(guān)鍵線路關(guān)鍵線路的長度決定了工程周期，關(guān)鍵線路可以有多條，計劃安排得越緊湊，關(guān)鍵線路越多。關(guān)鍵線路的確定破“圈”法：在“圈”中去掉最短的一個工序。圖上作業(yè)法：標注節(jié)點時間，通常情況下，節(jié)點時差為0的節(jié)點組成關(guān)鍵線路。表上作業(yè)法：計算工序時間，總時差為0的工序組成關(guān)鍵線路。線性規(guī)劃法：最大允許時間法和影子價格法關(guān)鍵線路的確定破圈法：15387642AHELKGDFCB60451810204015302535關(guān)鍵線路A-D-G-K-L(1-2-4-6-7-8),長度為170例5.4關(guān)鍵線路的確定圖上標注法15387642AHELKGDFCB60451810204015302535060708010011013517017013511012080117600關(guān)鍵線路的確定表上作業(yè)法關(guān)鍵線路的確定參照最短路徑的方法，假設(shè)網(wǎng)絡(luò)圖中的總流量為1，將每個工序的作業(yè)時間作為單位流量費用，求這一個流量通過網(wǎng)絡(luò)的最大費用，所經(jīng)過的弧即為關(guān)鍵工序，按順序連在一起即為關(guān)鍵路徑，求得的最大費用（最長距離）即為項目的最早完工時間。根據(jù)各個節(jié)點的凈流量條件，目標為總經(jīng)過的時間最長。線性規(guī)劃法求關(guān)鍵線路(1)15387642AHELKGDFCB60451810204015302535例5.4線性規(guī)劃法確定關(guān)鍵線路例5.4：設(shè)fij表示通過節(jié)點(i,j)的流量，根據(jù)題意求關(guān)鍵線路的線性規(guī)劃模型(1)畫出網(wǎng)絡(luò)圖例5.4決策變量：各節(jié)點的發(fā)生時間（項目起始時刻為0，節(jié)點的最早時間）；目標函數(shù)：最后一個節(jié)點的發(fā)生（完成）時間最早；約束條件：各個活動的實際持續(xù)時間應(yīng)不小于完成活動所需時間；某活動實際持續(xù)時間＝某活動結(jié)束時間－開始時間線性規(guī)劃法求關(guān)鍵線路(2)例5.4：設(shè)xi表示通過節(jié)點i的最早時間，根據(jù)題意求關(guān)鍵線路的線性規(guī)劃模型(2)建立活動--節(jié)點矩陣，對任一節(jié)點，箭頭進入為+1，箭頭流出為-1。利用該矩陣元素與相應(yīng)變量之間的乘積和計算各工序的時間。關(guān)鍵線路判斷：作業(yè)時間影子價格為1的工序（為什么？）或?qū)嶋H持續(xù)時間與完成活動所需時間相等的工序為關(guān)鍵線路上的工序。線性規(guī)劃法求關(guān)鍵線路(2)線性規(guī)劃方法求關(guān)鍵線路舉例網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化縮短工程計劃工期問題

保證質(zhì)量和不增加人力物力的前提下盡量縮短工期。注意關(guān)鍵線路的變化。壓縮關(guān)鍵工序的工序時間

在關(guān)鍵工序上采取改進技術(shù)、工藝和設(shè)備等措施，優(yōu)先保證關(guān)鍵工序所需，矛盾時非關(guān)鍵線路應(yīng)盡可能讓路。在非關(guān)鍵工序上盡量挖掘潛力

利用非關(guān)鍵線路上的時差進行合理調(diào)度，抽調(diào)資源支援關(guān)鍵線路。采用平行或交叉作業(yè)例5.5縮短計劃工期某工程有關(guān)的工序關(guān)系及時間如下：例5.5縮短計劃工期畫出網(wǎng)絡(luò)圖：153109742ALDMJFCHB264354524386GE1例5.5縮短計劃工期計算時間參數(shù)，確定關(guān)鍵線路：153109742ALDMJFCHB264354524386GE10182576119915181510101198520關(guān)鍵線路A-B-E-H-M(1-2-3-6-9-10),長度為18例5.5縮短計劃工期現(xiàn)要求將整個計劃工期縮短3天。首先從關(guān)鍵線路上想辦法，能否縮短3天？也要考慮其它非關(guān)鍵線路上工時縮短的情況。具體做法如下：將圖中的最后一個節(jié)點的最遲時間設(shè)定為15倒退計算法求出各工作的時差找出所有時差為負值的工序?qū)ζ渲械年P(guān)鍵工序進行協(xié)調(diào)，縮短工作時間，使總時間為15天重新計算時間，如仍有負時差工序，再考慮縮短該工序的時間，直到?jīng)]有負時差為止。例5.5縮短計劃工期將第10節(jié)點的最遲時間設(shè)定為15，計算各工序時差153109742ALDMJFCHB264354524386GE101525761199151812778652－1－3-3-2-1-30-2-30-2-3-31515例5.5縮短計劃工期從圖中可以看出：在原關(guān)鍵線路上各工序的總時差均為－3，因此需要在原來的關(guān)鍵線路上縮短3天。除了原先關(guān)鍵線路上是負時差外，在其它非關(guān)鍵線路上也出現(xiàn)負時差，在這些線路上也要進行日期的縮短。共有以下幾條需要縮短：第一條：1－2－3－6－9－10縮短3天第二條：2－4－7－8－9縮短2天第三條：7－9縮短1天必須滿足以上條件才有可能縮短3天例5.5縮短計劃工期先考慮關(guān)鍵線路縮短3天，經(jīng)協(xié)調(diào)使B、M、E各減1天；B和M工序各縮短為2天；E工序縮短為5天重新計算時間例5.5縮短計劃工期關(guān)鍵路線工序時間縮短后，重新計算時間：153109742ALDMJFCHB26425452438