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

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