管科大二上學(xué)期課件-運籌學(xué)or-chap

第九章網(wǎng)絡(luò)計劃

網(wǎng)絡(luò)計劃技術(shù)概論網(wǎng)絡(luò)圖網(wǎng)絡(luò)時間與關(guān)鍵路徑網(wǎng)絡(luò)優(yōu)化用網(wǎng)絡(luò)分析的方法編制的計劃稱為網(wǎng)絡(luò)計劃第九章網(wǎng)絡(luò)計劃1.網(wǎng)絡(luò)計劃技術(shù)概論1.1網(wǎng)絡(luò)計劃的起源和發(fā)展1917年，亨利·甘特發(fā)明了著名的甘特圖GanttChart（也稱橫道圖），使項目經(jīng)理按日歷制作任務(wù)圖表，用于日常工作安排1956年，美國杜邦公司將關(guān)鍵路徑法（CPM）應(yīng)用于設(shè)備維修，使維修停工時間由125小時銳減為7小時

1958年，美國海軍特種計劃局在北極星導(dǎo)彈設(shè)計中，應(yīng)用計劃評審技術(shù)（PERT），將項目任務(wù)之間的關(guān)系模型化，使設(shè)計完成時間縮短了2年

1962年美國國防部規(guī)定：以后承包有關(guān)工程的單位都應(yīng)采用網(wǎng)絡(luò)計劃技術(shù)來安排計劃1.1網(wǎng)絡(luò)計劃的起源和發(fā)展60年代初，我國著名數(shù)學(xué)家華羅庚教授將此技術(shù)介紹到中國，并把它稱為“統(tǒng)籌法”國內(nèi)外應(yīng)用網(wǎng)絡(luò)計劃的實踐表明，它具有一系列優(yōu)點

特別適用于生產(chǎn)技術(shù)復(fù)雜，工作項目繁多、且聯(lián)系緊密的一些跨部門的工作計劃新產(chǎn)品研制開發(fā)、大型工程項目、生產(chǎn)技術(shù)準(zhǔn)備、設(shè)備大修等計劃、資源安排、工作流程以下主要介紹CPM。編制網(wǎng)絡(luò)計劃包括繪制網(wǎng)絡(luò)圖，計算時間參數(shù)，確定關(guān)鍵路線及網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)1.2網(wǎng)絡(luò)計劃與橫道計劃的比較簡單、清晰、形象、易懂、使用方便；施工過程施工進度（天）2468101214161820支模10人綁鋼筋15人澆混凝土10人優(yōu)點：可以直接在圖中進行各項資源需要量統(tǒng)計。102510勞動力動態(tài)消耗圖1.2網(wǎng)絡(luò)計劃與橫道計劃的比較不能直接反映各施工過程之間相互聯(lián)系、相互制約的邏輯關(guān)系不能明確指出那些工作是關(guān)鍵工作，那些工作不是關(guān)鍵工作不能計算各工作的時間參數(shù)，看不到計劃的潛力不能應(yīng)用計算機進行調(diào)整和優(yōu)化缺點：1.2網(wǎng)絡(luò)計劃與橫道計劃的比較1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426施工過程施工進度（天）2468101214161820支模10人綁鋼筋15人澆混凝土10人1.2網(wǎng)絡(luò)計劃與橫道計劃的比較1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426能全面而明確地反映各施工過程之間相互聯(lián)系、相互制約的邏輯關(guān)系；通過時間參數(shù)的計算，能夠找出關(guān)鍵施工過程和關(guān)鍵線路，便于管理者抓住主要矛盾；通過時間參數(shù)的計算，可以對網(wǎng)絡(luò)計劃進行調(diào)整和優(yōu)化；優(yōu)點：第九章網(wǎng)絡(luò)計劃2.網(wǎng)絡(luò)圖2.1網(wǎng)絡(luò)圖的構(gòu)成網(wǎng)絡(luò)圖是由作業(yè)、事項（節(jié)點）和路線三大部分組成作業(yè)（工作、工序、活動），箭線表示，一般箭線之上表示工作名稱，之下表示工作時間作業(yè)一般分為兩種：消耗一定的時間與資源的工作――實工作，用實箭線表示既不消耗時間也不消耗資源的工作――虛工作，虛設(shè)的工作，只表示前后工作之間的邏輯關(guān)系，用虛箭線表示“雙代號表示法”2.1網(wǎng)絡(luò)圖的構(gòu)成

事項，節(jié)點表示，表示前面工作結(jié)束和后面工作開始的時間點，表示工作結(jié)束和開始的瞬間，既不消耗時間也不消耗資源1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426起始節(jié)點終點節(jié)點中間節(jié)點2.1網(wǎng)絡(luò)圖的構(gòu)成1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426節(jié)點的編號:從左到右，由小到大；箭尾編號小于箭頭編號,即i＜j

；編碼可以不連續(xù)，但不可以重復(fù)。2.1網(wǎng)絡(luò)圖的構(gòu)成

路線，網(wǎng)絡(luò)圖中，從起始節(jié)點開始，沿箭線方向連續(xù)通過一系列節(jié)點和箭線，最后到達(dá)終點節(jié)點的若干條通道，稱為路線124AC5B2D4E5G3F56351①→②→④→⑥（8天）①→②→③→④→⑥（10天）①→②→③→⑤→⑥（9天）①→③→④→⑥（14天）①→③→⑤→⑥（13天）第四條線路耗時最長（14天），對整個工程的完工起著決定性的作用，稱為關(guān)鍵線路；其余線路均稱為非關(guān)鍵線路。處于關(guān)鍵線路上的各項工作稱為關(guān)鍵工作。關(guān)鍵工作完成的快慢將直接影響整個計劃工期的實現(xiàn)。關(guān)鍵線路上的箭線常采用粗線、雙線或其它顏色的箭線突出表示。

位于非關(guān)鍵線路上的工作除關(guān)鍵工作外，都稱為非關(guān)鍵工作，它們都有機動時間(即時差)；非關(guān)鍵工作也不是一成不變的，它可以轉(zhuǎn)化成關(guān)鍵工作；利用非關(guān)鍵工作的機動時間可以科學(xué)地、合理地調(diào)配資源和對網(wǎng)絡(luò)計劃進行優(yōu)化。

2.1網(wǎng)絡(luò)圖的構(gòu)成2.2畫網(wǎng)絡(luò)圖的規(guī)則網(wǎng)絡(luò)圖只能一個開始節(jié)點，一個終止節(jié)點網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號大于箭尾事項編號不能出現(xiàn)循環(huán)路線（即不允許有回路）2365412.2畫網(wǎng)絡(luò)圖的規(guī)則兩事項間只能有一項作業(yè)改為箭線的首尾都必須有節(jié)點131211配砂造型14131211造型配砂2配砂1網(wǎng)絡(luò)圖要布局規(guī)整、條理清晰、重點突出。繪制網(wǎng)絡(luò)圖時，應(yīng)盡量采用水平箭線和垂直箭線而形成網(wǎng)格結(jié)構(gòu)，盡量減少斜箭線，使網(wǎng)絡(luò)圖規(guī)整、清晰。其次，應(yīng)盡量把關(guān)鍵工作和關(guān)鍵線路布置在中心位置，盡可能把密切相連的工作安排在一起，以突出重點，便于使用。2.2畫網(wǎng)絡(luò)圖的規(guī)則1234EBDACF（a）有交叉和斜向箭線的網(wǎng)絡(luò)圖1234EFDCAB（b）調(diào)整后的網(wǎng)絡(luò)圖ABABCABCABCACB序號工作之間的邏輯關(guān)系網(wǎng)絡(luò)圖中的表示方法說明1A工作完成后進行B工作A工作制約著B工作的開始，B工作依賴著A工作2A、B、C三項工作同時開始

A、B、C三項工作稱為平行工作3A、B、C三項工作同時結(jié)束A、B、C三項工作稱為平行工作4有A、B、C三項工作。只有A完成后，B、C才能開始A工作制約著B、C工作的開始，B、C為平行工作5有A、B、C三項工作。C工作只有在A、B完成后才能開始C工作依賴著A、B工作，A、B為平行工作BACDACBDiDA1B1A2A3B2B3ADBCE6有A、B、C、D四項工作。只有當(dāng)A、B完成后，C、D才能開始通過中間節(jié)點i正確地表達(dá)了A、B、C、D工作之間的關(guān)系7有A、B、C、D四項工作。A完成后C才能開始，A、B完成后D才能開始D與A之間引人了邏輯連接（虛工作），從而正確地表達(dá)了它們之間的制約關(guān)系8有A、B、C、D、E五項工作。A、B完成后C才能開始，B、D完成后E才能開始虛工作i-j反映出C工作受到B工作的制約；虛工作i-k反映出E工作受到B工作的制約9有A、B、C、D、E五項工作。A、B、C完成后D才能開始，B、C完成后E才能開始虛工作反映出D工作受到B、C工作的制約10A、B兩項工作分三個施工段，平行施工每個工種工程建立專業(yè)工作隊，在每個施工段上進行流水作業(yè)，虛工作表達(dá)了工種間的工作面關(guān)系A(chǔ)CBE

i

j

k2.3網(wǎng)絡(luò)圖的繪制實例任務(wù)分解(WorkBreakdownStructure,WBS)繪制網(wǎng)絡(luò)圖節(jié)點編號作業(yè)分析表試探性繪制法：試探試探性繪制法：修改流程圖過渡繪制法：流程圖流程圖過渡繪制法：加事項流程圖過渡繪制法：去方框流程圖過渡繪制法：修改2.4練習(xí)某新產(chǎn)品研制項目的各項序動、所需時間及相互關(guān)系如下表。工序工序代號所需時間緊后工序產(chǎn)品及工藝設(shè)計a60b,c,d,e外購配套件b45l下料、鍛件c10f工裝制造1d20g,h木模、鑄件e40h機械加工1f18l工裝制造2g30i機械加工2h15l機械加工3i25l機械加工4l25j裝配調(diào)試j3512345678a60d20g30i25l25b45f18e40h15c109j352.4練習(xí)第九章網(wǎng)絡(luò)計劃3.網(wǎng)絡(luò)時間與關(guān)鍵路徑3.1時間參數(shù)計算網(wǎng)絡(luò)圖繪制，只是用網(wǎng)絡(luò)的形式表達(dá)出了工作之間的邏輯關(guān)系。還必須通過計算求出工期，得到一定的時間參數(shù)計算網(wǎng)絡(luò)圖中有關(guān)的時間參數(shù)，主要目的是找出關(guān)鍵路線，為網(wǎng)絡(luò)計劃的優(yōu)化、調(diào)整和執(zhí)行提供明確的時間概念時間參數(shù)：工序所需時間、事項最早、最遲的時間、工序的最早、最遲時間及時差完成工序所需時間確定，只給出一個時間值CPM在影響工序因素較多，作業(yè)時間難以準(zhǔn)確估計時，采用三點時間PERTa—最快可能完成時間m—最可能完成時間b—最慢可能完成時間3.2工序時間的確定確定型概率型3.3事項的時間參數(shù)-最早事項（節(jié)點）的最早時間——tE(j)表示以j為始點的各工序最早可能開始的時間，也表示以j為終點的各工序均完成的最早可能時間起始節(jié)點的最早開始時間為0，即tE(1)=0

tE(j)=max{tE(i)+t(i,j)}i,j

分別代表箭尾和箭頭事件從起始節(jié)點開始,正向計算i3.3事項的時間參數(shù)-最遲事項（節(jié)點）最遲時間——tL(i)表示在不影響任務(wù)總工期的條件下，以i為始點的各工序最遲必須開始時間，或以i為終點的各工作的最遲必須完成時間一般將任務(wù)的最早完工時間作為任務(wù)的總工期

tL(n)=tE(n)

n為終點事項

tL(i)=min{tL(j)–t(i,j)}i,j

分別代表箭尾和箭頭事件從終點節(jié)點開始,反向計算，即從編號大到小順序j3.3事項的時間參數(shù)-例題計算各事項的最早時間和最遲時間。3.3事項的時間參數(shù)-例題時間參數(shù)的圖上計算法3.4工序的時間參數(shù)-最早工序的最早可能開工時間——tES(i,j)任何一個工序都必須在其所有緊前工序全部完成后才能開始工序的最早可能完工時間——tEF(i,j)表示工作按最早開工時間開始所能達(dá)到的完工時間tES(1,j)=0tES(i,j)=max{tES(k,i)+t(k,i)}tEF(i,j)=tES(i,j)+t(i,j)tES(i,j)=tE(i)EarlyFinishEarlyStarttEF(i,j)=tE(i)+

t(i,j)k3.4工序的時間參數(shù)-最遲工序的最遲必須開工時間——tLS(i,j)表示工序(i,j)在不影響整個任務(wù)如期完成的前提下，必須開始的最晚時間工序的最遲必須完工時間——tLF(i,j)表示工作(i,j)按最遲時間開工，所達(dá)到的完工時間tLF(i,n)=tL(n)=tE(n)tLS(i,j)=min{tLS(j,k)-t(i,j)}tLF(i,j)=tLS(i,j)+t(i,j)tLF(i,j)=tL(j)LateFinishLateStarttLS(i,j)=tL(i)

-

t(i,j)k作業(yè)時間和事項時間的關(guān)系ijETESEFETLTLTLFLStij+tij=－

tij=工序的時差或工序的機動時間工序總時差R(i,j)，在不影響總工期的情況下，最早開始（或結(jié)束）時間可以推遲的時間R(i,j)=tLF(i,j)-tEF(i,j)=tLS(i,j)-tES(i,j)總時差為0的作業(yè)是關(guān)鍵作業(yè)，開始和結(jié)束的時間沒有一點機動的余地由關(guān)鍵作業(yè)構(gòu)成的路線是關(guān)鍵路線，它是時間最長的路線3.5時差-總時差3.5時差-單時差工序單時差——r(i,j)

表示不影響緊后工序最早開始時間的條件下，工序最早結(jié)束時間可以推遲的時間

r(i,j)=tES(j,k)–tEF(i,j)

tES(j,k)為工序(i,j)的緊后工序的最早開始時間單時差為0，總時差不一定為0總時差為0，單時差一定為03.5時差-總時差與單時差的關(guān)系計算各作業(yè)的最早時間、最遲時間和時差。3.6例題13.6例題1時間參數(shù)的表上計算法143568927B62IHDGECA22KLJ741034343.6例題2

143568927025261519120202256102915190228151221226212500221212151521919111187612615811746151115711B62IHDGECA22KLJ741034343.6例題23.7概率型網(wǎng)絡(luò)圖的時間參數(shù)總完工期（期望工期）——關(guān)鍵路線上各工序的平均工時之和總完工期的方差——關(guān)鍵路線上各工序的方差之和3.7概率型網(wǎng)絡(luò)圖的時間參數(shù)

為達(dá)到嚴(yán)格控制工期，確保任務(wù)在計劃期內(nèi)完成的目的，我們可以計算在某一給定期限Ts前完工的概率。

一般可指定多個完工期Ts，直到求得有足夠可靠性保證的計劃工期Ts*，將其作為總工期。標(biāo)準(zhǔn)正態(tài)分布3.7概率型網(wǎng)絡(luò)圖的時間參數(shù)—舉例

例：已知某一計劃中各件工作的a,m,b值（單位：月）。要求：（1）每件工作的平均工時

t和均方差σ；（2）畫出網(wǎng)絡(luò)圖，確定關(guān)鍵路線；（3）在25個月前完工的概率。工作ambt①→②78980.333①→③5786.8330.5②→⑥691291③→④44440③→⑤78108.1670.5③→⑥10131913.51.5④→⑤3464.1670.5⑤→⑥4575.1670.5⑤→⑦791190.667⑥→⑦3484.50.8333.7概率型網(wǎng)絡(luò)圖的時間參數(shù)—舉例按

t值計算出各工作的最早開工時間tES和最遲開工時間

tLS，以及總時差

R。工作tEStLSR①→②03.3333.333①→③000②→⑥811.3333.333③→④6.8336.9990.166③→⑤6.8336.9990.166③→⑥6.8336.8330④→⑤10.83310.9990.166⑤→⑥1515.1660.166⑤→⑦1515.8330.833⑥→⑦20.33320.3330√√√關(guān)鍵路線：①→③→⑥→⑦

總完工期：24.8333.7概率型網(wǎng)絡(luò)圖的時間參數(shù)—舉例在25個月前完工的概率為：注1：計算某一事項i在指定日期Ts(i)前完成的概率具有較小概率的事項應(yīng)特別注意，凡是以它為完工時間的工作均應(yīng)加快進度。注2：還應(yīng)注意那些從始點到終點完工日期與總工期相近的次關(guān)鍵路線，計算它們按總工期完工的概率，實施計劃時對其中完工概率較小的一些路線從嚴(yán)控制進度。第九章網(wǎng)絡(luò)計劃4.網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)計劃優(yōu)化工期優(yōu)化費用優(yōu)化資源優(yōu)化4.1工期限定，資源需要平衡該作業(yè)每天所需勞動力該作業(yè)時間4.1工期限定，資源需要平衡關(guān)鍵路線作業(yè)總時差作業(yè)時間各工作都按最早開始時間開始工期不變，就是關(guān)鍵工作時間不能調(diào)整，即不調(diào)整關(guān)鍵路線上的作業(yè)資源不平衡將導(dǎo)致資源不足利用時差，調(diào)整非關(guān)鍵路線上工作的開始時間，使資源實現(xiàn)平衡4.1工期限定，資源需要平衡4.1工期限定，資源需要平衡4.1工期限定，資源需要平衡4.2資源有限，要求工期最短某工程按作業(yè)最早開工期安排的日程網(wǎng)絡(luò)圖如下：若每天最多只有10人工作，試問如何安排才能使總工期最短？4.2資源有限，要求工期最短調(diào)整方案一4.2資源有限，要求工期最短調(diào)整方案二4.3費用優(yōu)化工程項目的成本費用是和時間進度有關(guān)的。投入的資源愈多，作業(yè)時間也愈短反之，成本費用可能低些，但作業(yè)時間會加長綜合考慮費用優(yōu)化主要有以下兩個方面：工程周期給定，如何安排各項作業(yè)，使整個工程的直接費用降低如果有一筆準(zhǔn)備用來加快工程進度的追加費用，如何安排才能使工程總周期縮短最多?；蛘哒f，如果要求工程縮短一定時間，如何安排才能使追加的費用最小4.3費用優(yōu)化工期