運(yùn)籌學(xué)-錢(qián)頌迪-第9章

第9章網(wǎng)絡(luò)計(jì)劃本章主要內(nèi)容網(wǎng)絡(luò)圖時(shí)間參數(shù)的計(jì)算網(wǎng)絡(luò)計(jì)劃的優(yōu)化簡(jiǎn)述通常情況下，項(xiàng)目的策劃、安排及控制等活動(dòng)包含許多獨(dú)立的工作或由大量不同部門(mén)或個(gè)人負(fù)責(zé)。由于項(xiàng)目大且復(fù)雜，管理人員一般難以記住與項(xiàng)目相關(guān)的策劃、安排以及進(jìn)展等所有信息；此時(shí)，網(wǎng)絡(luò)計(jì)劃技術(shù)就能顯示出極為重要的作用。網(wǎng)絡(luò)計(jì)劃（NetworkProgramming，NP）——用網(wǎng)絡(luò)圖編制的計(jì)劃稱(chēng)為網(wǎng)絡(luò)計(jì)劃；產(chǎn)生于20世紀(jì)50年代末。網(wǎng)絡(luò)計(jì)劃技術(shù)由計(jì)劃評(píng)審技術(shù)（ProgramEvaluationandReviewTechnique，PERT）和關(guān)鍵路線(xiàn)法（Critical-PathMethod，CPM）組成。PERT主要用于解決活動(dòng)時(shí)間不確定的項(xiàng)目，而CPM主要是為活動(dòng)時(shí)間已知或確定的項(xiàng)目而設(shè)計(jì)的。但由于PERT的基礎(chǔ)是CPM，它們有時(shí)共同解決問(wèn)題。因此，通常一起討論P(yáng)ERT和CPM，統(tǒng)稱(chēng)為網(wǎng)絡(luò)計(jì)劃或網(wǎng)絡(luò)計(jì)劃技術(shù)（PERT/CPM）網(wǎng)絡(luò)計(jì)劃技術(shù)主要用于解決項(xiàng)目的策劃、安排及控制。如：新產(chǎn)品研制與開(kāi)發(fā)、大型工程項(xiàng)目的建設(shè)、復(fù)雜機(jī)器的維修、新系統(tǒng)的設(shè)計(jì)與安裝等；網(wǎng)絡(luò)計(jì)劃被發(fā)達(dá)國(guó)家認(rèn)為是當(dāng)前最為行之有效的管理方法之一；實(shí)踐證明：網(wǎng)絡(luò)計(jì)劃技術(shù)的應(yīng)用可使項(xiàng)目時(shí)間縮短20%左右，使成本降低10%左右；9.1網(wǎng)絡(luò)計(jì)劃圖9.1.1基本術(shù)語(yǔ)帶箭頭的線(xiàn)（箭線(xiàn)）和節(jié)點(diǎn)是網(wǎng)絡(luò)計(jì)劃圖的基本組成元素。線(xiàn)表示工作（工序、活動(dòng)、作業(yè)）；節(jié)點(diǎn)表示事項(xiàng)，為工作的開(kāi)始或結(jié)束。線(xiàn)有時(shí)間概念。它是消耗時(shí)間或者其他資源的單元。例如125a工作a（1，2），事項(xiàng)1，2；時(shí)間5另外，虛線(xiàn)可表示虛工作，它的工時(shí)為0，其作用僅表示工作的前后關(guān)系雙代號(hào)網(wǎng)絡(luò)計(jì)劃圖：如上圖。箭尾的節(jié)點(diǎn)表示工作的開(kāi)始點(diǎn)；箭頭的節(jié)點(diǎn)表示工作的完成點(diǎn)。9.1.2雙代號(hào)網(wǎng)絡(luò)計(jì)劃圖兩個(gè)內(nèi)容網(wǎng)絡(luò)計(jì)劃圖的繪制；時(shí)間參數(shù)的計(jì)算例9-1根據(jù)表格畫(huà)出網(wǎng)絡(luò)圖序號(hào)工作名稱(chēng)工作代號(hào)工作時(shí)間緊后序號(hào)工作名稱(chēng)工作代號(hào)工作時(shí)間緊后1設(shè)計(jì)A60BCDE6機(jī)加工1F18L2外購(gòu)B45L7工裝制造2G30K3備鍛件C10F8機(jī)加工2H15L4工裝制造1D20GH9機(jī)加工3K25L5鑄件E40H10裝配調(diào)試L35畫(huà)網(wǎng)絡(luò)圖的規(guī)則和術(shù)語(yǔ)1、網(wǎng)絡(luò)圖的方向、時(shí)序、節(jié)點(diǎn)編號(hào)方向：自左向右，時(shí)序：反映工作的先后順序節(jié)點(diǎn)統(tǒng)一編號(hào)，由小到大，最大的表示計(jì)劃結(jié)束，最小的表示開(kāi)始，對(duì)任一工序（i,j），要求j>i只能有一個(gè)總起點(diǎn)，一個(gè)總終點(diǎn)。起點(diǎn)表示開(kāi)始，終點(diǎn)表示結(jié)束從起點(diǎn)到終點(diǎn)的走向集合稱(chēng)為路線(xiàn)下面的圖就不符合要求1623458792、緊前工作和緊后工作緊前工作：緊排在本工作之前的工作，它開(kāi)始或完成后才能開(kāi)始本工作。緊后工作：緊排在本工作之后的工作，本工作開(kāi)始或完成后它才能開(kāi)始工作。3、相鄰的兩個(gè)節(jié)點(diǎn)之間只能有一個(gè)工作。不能出現(xiàn)該圖4、虛工作只有邏輯關(guān)系，不消耗時(shí)間或其他資源121321654325、不能有回路，也不能有缺口（斷路）虛工作的例子（鋪設(shè)地下管道）123746515432123121367451011891412312134576811109146、盡量避免箭頭線(xiàn)的交叉160C回到剛才的例子里來(lái)。根據(jù)以上規(guī)則，畫(huà)出網(wǎng)絡(luò)計(jì)劃圖2354678452510304018201535LKHGFEDBA9.2網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算網(wǎng)絡(luò)的時(shí)間參數(shù)包括：工作持續(xù)時(shí)間、工作過(guò)程時(shí)間、時(shí)差工作過(guò)程時(shí)間包括：工作最早開(kāi)始時(shí)間ES工作最早完成時(shí)間EF工作最遲開(kāi)始時(shí)間LS工作最遲完成時(shí)間LF9.2.1工作持續(xù)時(shí)間D1、確定型2、概率型（華羅庚型）設(shè)a——最快可能完成的時(shí)間（最樂(lè)觀時(shí)間）設(shè)b——最慢可能完成的時(shí)間（最悲觀時(shí)間）設(shè)m——最可能完成的正常時(shí)間則工作時(shí)間D(i,j)=(a+4m+b)/6其均方差σ2＝[(b-a)/6]2證明略9.2.2工作的時(shí)間參數(shù)的計(jì)算關(guān)系式1、工作的最早開(kāi)始時(shí)間ES(i,j)、工作的最早完成時(shí)間EF(i,j)2、工作的最遲開(kāi)始時(shí)間LS(i,j)、工作的最遲完成時(shí)間LF(i,j)3、時(shí)差又稱(chēng)作工作的機(jī)動(dòng)時(shí)間或者富裕時(shí)間。常用的時(shí)差有兩種（1）工作的總時(shí)差TF(i,j)在不影響總工期的條件下，其工作(i,j)可以延遲其開(kāi)工時(shí)間的最大幅度。（2）工作的自由時(shí)差FF(i,j)在不影響后繼工作最早開(kāi)工時(shí)間的條件下，此工作(i,j)最早結(jié)束時(shí)間中可以推遲的時(shí)間160C回到剛才的例子里來(lái)2354678452510304018201535LKHGFEDBAESLSTFEFLFFF00060600609030105135306047700606008080060802010012007011747881354780800110110010012020115135201101100135135013513501701700170107117關(guān)鍵路線(xiàn)及其確定已知，從起點(diǎn)S到終點(diǎn)T之間的任何一個(gè)活動(dòng)序列都稱(chēng)為一個(gè)路線(xiàn)，各活動(dòng)的時(shí)間之和為該路線(xiàn)的時(shí)間，時(shí)間最長(zhǎng)的路線(xiàn)稱(chēng)為關(guān)鍵路線(xiàn)；當(dāng)一項(xiàng)活動(dòng)的總時(shí)差為0時(shí)，意味著如果不增加整個(gè)項(xiàng)目完成時(shí)間，該活動(dòng)時(shí)間就不能延遲，因此：當(dāng)某活動(dòng)的總時(shí)差為0，則該活動(dòng)為關(guān)鍵活動(dòng)；由關(guān)鍵活動(dòng)組成的從始點(diǎn)到終點(diǎn)的路線(xiàn)就是關(guān)鍵路線(xiàn)；圖中①—②—④—⑥—⑦—⑧即為關(guān)鍵路線(xiàn)；任何一項(xiàng)關(guān)鍵活動(dòng)被延遲，整個(gè)項(xiàng)目就會(huì)被延遲，因此，項(xiàng)目經(jīng)理必須密切關(guān)注關(guān)鍵活動(dòng)的進(jìn)展對(duì)于一個(gè)項(xiàng)目的管理工作，關(guān)鍵路線(xiàn)可以幫助我們回答如下問(wèn)題：（1）完成項(xiàng)目總共需要的時(shí)間；該例：170天（2）每一活動(dòng)的開(kāi)始時(shí)間及結(jié)束時(shí)間安排；該例給出了各活動(dòng)的ES，EF，LS，LF（3）哪些活動(dòng)極為重要，需要及時(shí)完成；（4）在保證整個(gè)項(xiàng)目完成時(shí)間不被延遲的情況下，非重要活動(dòng)最多能拖延多長(zhǎng)時(shí)間關(guān)鍵路線(xiàn)的作用時(shí)間參數(shù)的表上作業(yè)法仍以此例為例步驟：為方便使用，對(duì)表格做統(tǒng)一的規(guī)定列出10列，內(nèi)容為工作的事項(xiàng)頭和事項(xiàng)尾、工作時(shí)間t(i,j)、最早開(kāi)工時(shí)間tES、最早完工時(shí)間tEF、最遲開(kāi)工時(shí)間tLS、最遲完工時(shí)間tLF、總時(shí)差R(i,j)、單時(shí)差r(i,j)、關(guān)鍵工作行數(shù)按工作項(xiàng)排列，一般按事項(xiàng)頭的順序依次排列最后給出結(jié)論ij本章作業(yè)：257頁(yè)，9.1題第二問(wèn)改為：圖上法只計(jì)算最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間，以及總時(shí)差；同時(shí)用表上法進(jìn)行全部計(jì)算。參考圖1643287910115HGMLBACIEFKD有很多軟件可以對(duì)較小的項(xiàng)目進(jìn)行計(jì)算與求解，如ManagementScientist；winQSB

等；對(duì)于大型復(fù)雜的項(xiàng)目，有P3，Project2000等；例如：ManagementScientist對(duì)項(xiàng)目的求解

關(guān)鍵路線(xiàn)的計(jì)算機(jī)求解9.4.1利用時(shí)差進(jìn)行資源優(yōu)化以下圖所示的網(wǎng)絡(luò)圖為例，其關(guān)鍵路線(xiàn)為②→④→⑥→⑦，總工期為75天。圖中△里的數(shù)據(jù)為每天所需要的人力數(shù)。只有65人9.4網(wǎng)絡(luò)計(jì)劃的優(yōu)化

（9.3“時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃圖”由同學(xué)們自學(xué)）254674258392620天30天15天25天32218天10天58人64人80人42人26人顯然人力資源分配不均勻。若自有81人，會(huì)浪費(fèi)；若臨時(shí)聘，可能有風(fēng)險(xiǎn)，且成本高254674258392665人20天30天15天25天32218天10天81人此時(shí)可利用時(shí)差調(diào)整。注意以下原則確保關(guān)鍵路線(xiàn)的人力安排非關(guān)鍵路線(xiàn)上的人力可以采用時(shí)差調(diào)整可見(jiàn)，調(diào)整后的效果非常好58人64人42人26人254674258392665人20天30天15天25天32218天20天9.4.2最低成本日程（時(shí)間——費(fèi)用優(yōu)化）項(xiàng)目經(jīng)理總是希望項(xiàng)目盡可能早的完成。因此，他們通過(guò)增加資源（設(shè)備、加班、雇傭臨時(shí)工、采用高技術(shù)、改進(jìn)工藝等）來(lái)縮短完成時(shí)間?？s短一個(gè)活動(dòng)的時(shí)間會(huì)增加該活動(dòng)的費(fèi)用，縮短整個(gè)項(xiàng)目完成時(shí)間會(huì)在增加總費(fèi)用的同時(shí)，也會(huì)帶來(lái)效益；因此，需要在活動(dòng)時(shí)間的減少與費(fèi)用的增加之間的平衡上做出決定。（一）基本概念：1、直接費(fèi)用：會(huì)計(jì)費(fèi)用2、間接費(fèi)用：如管理費(fèi)用3、成本斜率Cij對(duì)于某一活動(dòng)i有：正常活動(dòng)時(shí)間——Dij

正常費(fèi)用——Mij應(yīng)急活動(dòng)時(shí)間——dij

應(yīng)急費(fèi)用——mij成本斜率（又稱(chēng)作：?jiǎn)挝粦?yīng)急時(shí)間費(fèi)用）：

Cij=（mij–Mij

）/（Dij–dij

）活動(dòng)時(shí)間

dij

Mij

mij

Dij（二）網(wǎng)絡(luò)優(yōu)化的實(shí)例具體數(shù)據(jù)見(jiàn)下表。工期每縮短一天，間接費(fèi)用可節(jié)省400元，求最低成本日程。正常工期170天，直接費(fèi)用68900元，間接費(fèi)用170×400=68000元，總費(fèi)用136900元160C2354678452510304018201535LKHGFEDBA最低成本日程活動(dòng)一覽表工作正常工時(shí)與費(fèi)用特急工時(shí)與費(fèi)用最大時(shí)間緊縮TMAX(天)成本斜率(元/天)時(shí)間（天）費(fèi)用（元）時(shí)間（天）費(fèi)用（元）A①→②B②→⑦C②→③

D②→④E②→⑤F③→⑦G④→⑥H⑤→⑦K⑥→⑦L⑦→⑧604510204018301525351000045002800700010000360090003750625012000603051035102010153510000630043001100012500544012500575091501200001551058105100——120300400500230350400290——解：在關(guān)鍵路線(xiàn)中選出成本斜率最低的工作進(jìn)行盡可能大的縮短。本例中⑥→⑦的成本斜率最小，為290，將其縮短為15天，即縮短了10天。此時(shí)關(guān)鍵路線(xiàn)沒(méi)有變，這樣④→⑥還可以繼續(xù)減少10天，總工期縮短了20天160C2354678451510204018201535LKHGFEDBA兩個(gè)關(guān)鍵路線(xiàn)A→D→G→K→L;A→E→H→L增加的直接成本：10天×(290+350)元/天=6400元減少的間接成本：20天×400元/天=8000元總成本降低，可以繼續(xù)調(diào)整要同時(shí)針對(duì)兩個(gè)關(guān)鍵路線(xiàn)調(diào)整由圖可知，關(guān)鍵路線(xiàn)A→D