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

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

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

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

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

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

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

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

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

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

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

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

i

j

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

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

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

tL(n)=tE(n)

n為終點(diǎn)事項(xiàng)

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

分別代表箭尾和箭頭事件從終點(diǎn)節(jié)點(diǎn)開始,反向計(jì)算，即從編號大到小順序j3.3事項(xiàng)的時(shí)間參數(shù)-例題計(jì)算各事項(xiàng)的最早時(shí)間和最遲時(shí)間。3.3事項(xiàng)的時(shí)間參數(shù)-例題時(shí)間參數(shù)的圖上計(jì)算法3.4工序的時(shí)間參數(shù)-最早工序的最早可能開工時(shí)間——tES(i,j)任何一個工序都必須在其所有緊前工序全部完成后才能開始工序的最早可能完工時(shí)間——tEF(i,j)表示工作按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間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í)間參數(shù)-最遲工序的最遲必須開工時(shí)間——tLS(i,j)表示工序(i,j)在不影響整個任務(wù)如期完成的前提下，必須開始的最晚時(shí)間工序的最遲必須完工時(shí)間——tLF(i,j)表示工作(i,j)按最遲時(shí)間開工，所達(dá)到的完工時(shí)間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è)時(shí)間和事項(xiàng)時(shí)間的關(guān)系ijETESEFETLTLTLFLStij+tij=－

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

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

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

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

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

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

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

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

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í)間參數(shù)—舉例按

t值計(jì)算出各工作的最早開工時(shí)間tES和最遲開工時(shí)間

tLS，以及總時(shí)差

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