系統(tǒng)工程與運(yùn)籌學(xué)5.ppt

第七章 網(wǎng)絡(luò)計(jì)劃技術(shù),,Company Logo,第一節(jié) 系統(tǒng)管理的網(wǎng)絡(luò)計(jì)劃技術(shù) 一、網(wǎng)絡(luò)計(jì)劃技術(shù) 定義： 是利用網(wǎng)絡(luò)圖對計(jì)劃任務(wù)的進(jìn)度、費(fèi)用及其組成部分之間的相互關(guān)系進(jìn)行計(jì)劃和控制的使系統(tǒng)協(xié)調(diào)運(yùn)轉(zhuǎn)的科學(xué)方法。其主要特點(diǎn)是統(tǒng)籌安排，因此我國把各種不同的網(wǎng)絡(luò)計(jì)劃技術(shù)與方法統(tǒng)稱為統(tǒng)籌法。,,Company Logo,1、甘特圖法,它以時(shí)間為橫坐標(biāo)，以工序?yàn)榭v坐標(biāo)，以線條的長短表示一項(xiàng)工作或作業(yè)的開始和完成時(shí)刻以及工作的進(jìn)展情況。由于它以條形圖進(jìn)行系統(tǒng)計(jì)劃與管理，故又稱橫道圖、條形圖,,Company Logo,優(yōu)點(diǎn)：簡單明了、容易繪制、使用方便。 缺點(diǎn)： 不能反映各項(xiàng)工作之間錯(cuò)綜復(fù)雜的聯(lián)系和制約關(guān)系； 不能反映哪些工作是主要的、關(guān)鍵性的生產(chǎn)聯(lián)系和工序，反映不出全局的關(guān)鍵所在； 修改時(shí)牽一發(fā)而動全身。,,Company Logo,2、關(guān)鍵線路法 （Critical Path Method，CPM） 以網(wǎng)絡(luò)圖的形式表示各工序之間在時(shí)間和空間上的相互關(guān)系以及各工序的工期，通過時(shí)間參數(shù)的計(jì)算，確定關(guān)鍵線路和總工期，從而制訂出系統(tǒng)計(jì)劃并指示出系統(tǒng)管理的關(guān)鍵所在。 特點(diǎn)：工序確定、工期確定 關(guān)鍵線路：管理的重點(diǎn),,Company Logo,3、計(jì)劃評審技術(shù) （Program Evaluation and Review Teacnique，PERT） 計(jì)劃評審技術(shù)（也稱計(jì)劃協(xié)調(diào)技術(shù)） 特點(diǎn)：工序確定，工期不確定,,Company Logo,區(qū)別：,PERT與CPM法既有聯(lián)系又有區(qū)別。 聯(lián)系：二者的網(wǎng)絡(luò)圖形和計(jì)算方法基本相似；,,Company Logo,4、決策關(guān)鍵線路法 （Decision Critical Path Method，DCPM） 該將CPM網(wǎng)絡(luò)和決策理論結(jié)合起來，開發(fā)出決策關(guān)鍵線路法。 特點(diǎn)：在同一張網(wǎng)絡(luò)圖上表示完成同一任務(wù)的各種不同方案，通過繪制特定的網(wǎng)絡(luò)圖和采用特定的計(jì)算方法，可得出完成該項(xiàng)任務(wù)的最小費(fèi)用工期及關(guān)鍵路線等。,,Company Logo,5、圖解評審技術(shù) （Graphical evaluation and Review Technique，GERT） 是一種廣義網(wǎng)絡(luò)計(jì)劃技術(shù)。該技術(shù)可克服CPM與PERT中工序均為確定型的缺點(diǎn)，解決實(shí)踐中存在隨機(jī)工序問題。 特點(diǎn)：工序不確定，工期不確定,,Company Logo,二、 網(wǎng)絡(luò)計(jì)劃技術(shù)應(yīng)用的程序,,Company Logo,網(wǎng)絡(luò)圖又叫統(tǒng)籌圖，它是由箭線和節(jié)點(diǎn)組成的、用來表示工作流程的有向、有序網(wǎng)狀圖形，是計(jì)劃任務(wù)及其組成部分相互關(guān)系的綜合反映，是進(jìn)行計(jì)劃、管理和計(jì)算的基礎(chǔ)。,第二節(jié) 網(wǎng)絡(luò)圖的繪制,,Company Logo,1、網(wǎng)絡(luò)圖的組成 網(wǎng)絡(luò)圖是針對一項(xiàng)任務(wù)編制的，由節(jié)點(diǎn)、工作和線路組成。 任務(wù)：一項(xiàng)有開始和結(jié)束標(biāo)志、由若干相互關(guān)聯(lián)且有不同指標(biāo)要求的工作所組成的有目的的事物。 工作或工序：將任務(wù)按需要的粗細(xì)程度劃分而成的、消耗時(shí)間或同時(shí)也消耗資源的、在工藝和組織管理上相互獨(dú)立的活動（子任務(wù)），它包括人的各式各樣的相互協(xié)調(diào)的勞動，是網(wǎng)絡(luò)計(jì)劃的基本組成單元。,,Company Logo,節(jié)點(diǎn)：網(wǎng)絡(luò)圖中箭線端部圓圈或其他形狀的封閉圖形。 雙代號網(wǎng)絡(luò)圖中是工作開始或結(jié)束的標(biāo)志，表示工作之間的邏輯關(guān)系； 單代號網(wǎng)絡(luò)圖中表示工作。 線路：從網(wǎng)絡(luò)圖的起點(diǎn)開始沿箭線方向連續(xù)通過一系列箭線和節(jié)點(diǎn)，最后到達(dá)終點(diǎn)所經(jīng)過的路線。線路所消耗的時(shí)間稱路長，最長的路長為關(guān)鍵線路，它決定任務(wù)的工期。,,Company Logo,流程特性：工作與工作之間工作的關(guān)系有多種，其中最常用的是緊前工作和緊后工作。 緊前工作：指一項(xiàng)工作開始之前必須完成的工作； 緊后工作：指一項(xiàng)工作完成之后緊接著能進(jìn)行的工作。,,Company Logo,2、 網(wǎng)絡(luò)圖的繪制 （1）網(wǎng)絡(luò)圖的繪制程序。繪制網(wǎng)絡(luò)圖是在對任務(wù)進(jìn)行分析和分解的基礎(chǔ)上，按規(guī)定的畫法畫出網(wǎng)絡(luò)圖的過程。該過程分為以下兩步： 任務(wù)的分解和分析。 分解 確定先后順序 確定工期,,Company Logo,流程特性，指工作與工作之間工作的關(guān)系有多種，也稱為前導(dǎo)關(guān)系或者依賴關(guān)系：(finish-start) 完成-開始FS： 完成-完成FF： 開始-開始SS： 開始-完成SF： 最常用的是緊前工作和緊后工作。,,Company Logo,工作邏輯關(guān)系表,,Company Logo,例：某廠管理信息系統(tǒng)開發(fā)活動清單,,Company Logo, 畫網(wǎng)絡(luò)圖 在網(wǎng)絡(luò)計(jì)劃法中，網(wǎng)絡(luò)圖有單代號和雙代號兩種表示法。 單代號表示法可表示工作間的各種邏輯關(guān)系，應(yīng)用較廣； 雙代號僅能表示工作間的緊前、緊后關(guān)系，應(yīng)用有一定的局限性。 目前我國中小型項(xiàng)目大多采用雙代號表示法,,Company Logo,（2）單代號網(wǎng)絡(luò)圖 用節(jié)點(diǎn)及編號表示一項(xiàng)工作，用箭線表示各工作之間的聯(lián)系，一般采用或表示,,Company Logo,單代號網(wǎng)絡(luò)圖繪制的基本規(guī)則： 網(wǎng)絡(luò)圖必須正確表述已定的邏輯關(guān)系。 嚴(yán)禁出現(xiàn)循環(huán)回路。 嚴(yán)禁出現(xiàn)雙箭頭或無箭頭的連線。 嚴(yán)禁出現(xiàn)沒有箭尾節(jié)點(diǎn)和沒有箭頭節(jié)點(diǎn)的箭線。 箭線不宜交叉，當(dāng)交叉不可避免時(shí)可采用過橋法和指向法繪制。 只應(yīng)有一個(gè)起點(diǎn)節(jié)點(diǎn)和一個(gè)終點(diǎn)節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)圖中有多項(xiàng)起點(diǎn)節(jié)點(diǎn)或多項(xiàng)終點(diǎn)節(jié)點(diǎn)時(shí)應(yīng)在網(wǎng)絡(luò)圖的兩端分別設(shè)置一項(xiàng)虛工作，作為該網(wǎng)絡(luò)圖的起點(diǎn)節(jié)點(diǎn)（St）和終點(diǎn)節(jié)點(diǎn)（Fin）。,,Company Logo,（3）雙代號網(wǎng)絡(luò)圖繪制方法與規(guī)則 雙代號網(wǎng)絡(luò)圖用表示節(jié)點(diǎn)，以箭線表示工作。,,Company Logo,在雙代號網(wǎng)絡(luò)圖中，為了正確地表示各工作之間的邏輯關(guān)系，有時(shí)需引入虛工作。,,Company Logo,雙代號網(wǎng)絡(luò)圖繪制的基本規(guī)則為： 網(wǎng)絡(luò)圖必須正確表達(dá)已定的邏輯關(guān)系。 所有箭線方向必須由左到右，時(shí)間必須由現(xiàn)在到將來，嚴(yán)禁出現(xiàn)循環(huán)回路。 節(jié)點(diǎn)之間嚴(yán)禁出現(xiàn)雙向箭頭或無箭頭的連線。 嚴(yán)禁出現(xiàn)沒有箭頭事項(xiàng)或沒有箭尾事項(xiàng)的箭線。 箭線盡量避免交叉。 進(jìn)入某事項(xiàng)的工作可有多條，但由同一事項(xiàng)進(jìn)入該事項(xiàng)的工作只能有一條。 一個(gè)工作只應(yīng)有一個(gè)起點(diǎn)節(jié)點(diǎn)和一個(gè)終點(diǎn)節(jié)點(diǎn)。,,Company Logo,3、邏輯關(guān)系的基本表示方法,,Company Logo,,Company Logo,,Company Logo,練習(xí)：畫雙代號網(wǎng)絡(luò)圖,,Company Logo,一、 分析法 1、關(guān)鍵路線、路長和時(shí)差 路長：每條路所含工作的工期之和稱為路長。,第三節(jié) 網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算方法,,Company Logo,第三節(jié) 網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算方法,關(guān)鍵線路：決定任務(wù)總工期的路稱為關(guān)鍵線路。 線路時(shí)差：關(guān)鍵線路的路長和其余線路的路長之差。 F（Ln）=Lcp-Ln 其中：F（Ln）是線路時(shí)差； Lcp是關(guān)鍵路線路長； Ln是第n條線路的路長。,,Company Logo,,Company Logo,2、 網(wǎng)絡(luò)時(shí)間參數(shù)的計(jì)算 最早開始時(shí)間 最早結(jié)束時(shí)間 最晚開始時(shí)間 最晚結(jié)束時(shí)間 總時(shí)差 自由時(shí)差 約定： (i)事項(xiàng)；（i,j）：工作； E：最早；L：最晚； S：開始；F：結(jié)束； T時(shí)間； T（i,j）工作工期,,Company Logo,（1）事項(xiàng)（i）的最早開工時(shí)刻tES(i)。 只有進(jìn)入i事項(xiàng)的全部工作完成之后，由i事項(xiàng)開始的工作才能進(jìn)行，叫i事項(xiàng)的最早開始時(shí)刻。 TES(i)=maxTES(k)+T(k,i) 式中： TES(i)為第i事項(xiàng)最早開始時(shí)刻； TES(k)為第k事項(xiàng)最早開始時(shí)刻。 k=0時(shí)，TES(k)=0 （2）工作的最早開始時(shí)刻TES(i,j)和最早完工時(shí)刻TEF(i,j) TES(i,j)= TES(i) 或 TES(i,j)=max TES(k,i)+T(k,i) TEF(i,j)=TES(i,j)+T(i,j),,Company Logo,（3）事項(xiàng)(j)的最晚完工時(shí)刻TLF(j)。 為保證由該事項(xiàng)出發(fā)的工作在某一預(yù)定的最早時(shí)刻完成時(shí)，必須事項(xiàng)進(jìn)行的時(shí)刻叫事項(xiàng)的最晚完工時(shí)刻。 TLF(j)=minTLF(k)-T(j,k) （4）工作的最晚完工時(shí)刻TLF(i,j)和最晚開工時(shí)刻TLS(i,j)。 在不影響整個(gè)工程任務(wù)按期完成的條件下，一項(xiàng)工作必須完成的最遲時(shí)刻 TLF(i,j)=TLF(j)=minTLF(k)-T(j,k)=minTLF(j,k)-T(j,k) TLS(i,j)= TLF(i,j)-T(i,j),,Company Logo,（5）工作總時(shí)差和關(guān)鍵線路。 一項(xiàng)工作的最晚結(jié)束時(shí)刻與最早結(jié)束時(shí)刻之差或最晚開始時(shí)刻與最早開始時(shí)刻之差為工作的總時(shí)差。 R(i,j)=TLS(i,j)-TES(i,j)=TLF(i,j)-TEF(i,j) R(i,j)0 總時(shí)差最小（0,意味著沒有機(jī)動時(shí)間）的工作為關(guān)鍵工作。 由始至終全部由關(guān)鍵工作組成的線路稱關(guān)鍵線路。 （6）工作的自由時(shí)差。 可僅供本工作使用的寬裕時(shí)間自由時(shí)差又稱單時(shí)差，它是不能存儲的。是緊后工作最早開始時(shí)刻與本工作最早結(jié)束時(shí)刻之差。 r(i,j)=TES(j,k)-TEF(i,j) r(i,j) 0 R(i,j)r(i,j),,Company Logo,（7）線路時(shí)差 線路時(shí)差為零的線路為關(guān)鍵線路。 Rk(i,j)=0 (k=1，2，m)是該線路為關(guān)鍵線路的充要條件。,,Company Logo,（8）確定關(guān)鍵線路的步驟 求事項(xiàng)的最早開始時(shí)刻TES（i)。 求工作的最早結(jié)束時(shí)刻TEF(i,j)。 令終點(diǎn)事項(xiàng)的最早開始時(shí)刻為總工期。 求事項(xiàng)的最晚完工時(shí)刻TLF(i)。 求工作的最晚開始時(shí)刻TLS(i,j)。 確定總時(shí)差R(i,j)，自由時(shí)差r(i,j)。 R(i,j)=0或R(i,j)最小的工作所連成的線路為關(guān)鍵線路。,,Company Logo,二、 圖算法 圖算法的實(shí)質(zhì)是把分析法每步的計(jì)算結(jié)果用不同的符號標(biāo)在圖上，,以表示事項(xiàng)最早開工時(shí)刻，以表示事項(xiàng)的最晚完工時(shí)刻 （ ）內(nèi)是單時(shí)差， 內(nèi)是總時(shí)差,,Company Logo,三、 表算法,,Company Logo,第四節(jié) CPM網(wǎng)絡(luò)的優(yōu)化 一、 時(shí)間的優(yōu)化 時(shí)間優(yōu)化主要解決如何縮短總工期的問題。 任何網(wǎng)絡(luò)圖，經(jīng)計(jì)算都可得到完成任務(wù)的總工期T總（計(jì)算工期），該總工期與規(guī)定的工期T規(guī)（計(jì)劃工期）之間有如下三種關(guān)系： (1) T總T規(guī)。,,Company Logo,1、 消除負(fù)時(shí)差法,10,45,42,,Company Logo,,Company Logo,關(guān)鍵線路：包括負(fù)數(shù)在內(nèi)的最小寬裕時(shí)間工序所組成的線路。 次關(guān)鍵線路：具有最負(fù)總時(shí)差和次負(fù)總時(shí)差工作所組成的線路。,,Company Logo,消除負(fù)時(shí)差法的具體方法是： (1) 按要求工期計(jì)算出各工序的總時(shí)差，并以負(fù)時(shí)差確定關(guān)鍵線路和次關(guān)鍵線路。 (2) 如僅關(guān)鍵線路的時(shí)差為負(fù)時(shí)，按調(diào)整費(fèi)用最少的原則選擇一個(gè)或幾個(gè)工序進(jìn)行調(diào)整，直至使負(fù)時(shí)差為零。 (3) 如存在次關(guān)鍵線路，則說明為達(dá)到預(yù)定工期，在某些關(guān)鍵線路上調(diào)整可能使關(guān)鍵線路轉(zhuǎn)移。 關(guān)鍵線路和次關(guān)鍵線路存在公共工序 關(guān)鍵線路和次關(guān)鍵線路存在公共工序 (4) 繼續(xù)以新有效松弛量為調(diào)整量調(diào)整兩條關(guān)鍵線路中費(fèi)用較少的工序，直至使總時(shí)差全部為零為止。,,Company Logo,工期,調(diào)整費(fèi)用,16,3,7,9,15,7,7,4,8,5,15,4,2,7,9,2,10,5,13,7,45,42,12,4,13,7,40,總調(diào)整費(fèi)用=(15-13) *7+(15-12)*4=26,www.themegaller