運(yùn)籌學(xué)網(wǎng)絡(luò)計(jì)劃

用網(wǎng)絡(luò)分析的方法編制的計(jì)劃稱為網(wǎng)絡(luò)計(jì)劃。它是五十年代末發(fā)展起來的一種編制大型工程進(jìn)度計(jì)劃的有效方法。1956年，美國杜邦公司在制定企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃時(shí)，制定了第一套網(wǎng)絡(luò)計(jì)劃。這種計(jì)劃借助于網(wǎng)絡(luò)表示各項(xiàng)工作與所需要的時(shí)間，以及計(jì)劃執(zhí)行過程中的關(guān)鍵路線。這種方法稱為關(guān)鍵路線法（縮寫為CPM）。1958年美國海軍武器部，在制定研制“北極星”導(dǎo)彈計(jì)劃時(shí)，同樣也應(yīng)用了網(wǎng)絡(luò)分析方法與網(wǎng)絡(luò)計(jì)劃。但它注重于對(duì)各項(xiàng)工作安排的評(píng)價(jià)和審查。這種計(jì)劃稱為計(jì)劃評(píng)審方法（縮寫為PERT）。鑒于這兩種方法的差別，CPM主要應(yīng)用于以往在類似工程中已取得一定經(jīng)驗(yàn)的承包工程；PERT更多地應(yīng)用于研究與開發(fā)項(xiàng)目。在這兩種方法得到應(yīng)用推廣之后，又陸續(xù)地出現(xiàn)了類似的最低成本和估算計(jì)劃法，產(chǎn)品分析控制法，人員分配法，物資分配和多種項(xiàng)目計(jì)劃制定法等等。雖然方法很多，各自側(cè)重的目標(biāo)有所不同。但它們都應(yīng)用的是CPM和PERT的基本原理和基本方法。六十年代我國開始應(yīng)用CPM與PERT，并根據(jù)其基本原理與計(jì)劃的表達(dá)形式，稱它們?yōu)榫W(wǎng)絡(luò)技術(shù)和網(wǎng)絡(luò)方法，又按照網(wǎng)絡(luò)計(jì)劃的主要特點(diǎn)――統(tǒng)籌安排，把這些方法稱為統(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ì)劃。還可以應(yīng)用在人力、物力、財(cái)務(wù)等資源的安排，合理組織報(bào)表、文件流程等方面。編制網(wǎng)絡(luò)計(jì)劃包括繪制網(wǎng)絡(luò)圖，計(jì)算時(shí)間參數(shù)，確定關(guān)鍵路線及網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。下面分別討論這些內(nèi)容。網(wǎng)絡(luò)計(jì)劃的性質(zhì)及特點(diǎn)優(yōu)點(diǎn)：①能全面而明確地反映出各項(xiàng)工作之間的相互依賴、相互制約的關(guān)系②反映出整個(gè)工程和任務(wù)的全貌，指出對(duì)全局性有影響的關(guān)鍵線路和關(guān)鍵工作③顯示了機(jī)動(dòng)時(shí)間，以便更好地使用人力、設(shè)備④可利用計(jì)算機(jī)，編制程序上機(jī)⑤便于優(yōu)化和調(diào)整缺點(diǎn)：流水作業(yè)的情況很難在計(jì)劃上反映出來

第一節(jié)網(wǎng)絡(luò)圖

例1：某一設(shè)備維修網(wǎng)絡(luò)圖4225DCBA12453A：設(shè)備拆卸；B：電器部分修理；C：機(jī)械部分修理；D：設(shè)備安裝調(diào)試。網(wǎng)絡(luò)圖的組成：節(jié)點(diǎn)＋箭線（包括虛線）＋工作代號(hào)＋消耗時(shí)間工作或工序（作業(yè)、活動(dòng)）定義：指一項(xiàng)有具體內(nèi)容的、需要人力、物力、財(cái)力、占用一定空間和時(shí)間才能完成的活動(dòng)過程。虛活動(dòng)（作業(yè)）：只表示作業(yè)之間相互依存、相互制約、相互銜接的關(guān)系，但不需人力、物力、空間和時(shí)間的虛設(shè)的活動(dòng)。示例：B12146352產(chǎn)品設(shè)計(jì)A自制零部件B1外購零部件B2裝配C樣品鑒定D455035155事項(xiàng)（事件、節(jié)點(diǎn)）定義：工程（計(jì)劃）的始點(diǎn)、終點(diǎn)（完成點(diǎn)）或其各項(xiàng)作業(yè)的連接點(diǎn)（交接瞬間）。表示方法：ii（節(jié)點(diǎn)編號(hào)）：①表示事項(xiàng)時(shí)間大致順序自左向右自上向下排列②一般以正整數(shù)表示③一個(gè)節(jié)點(diǎn)只有一個(gè)編號(hào)④各節(jié)點(diǎn)不允許重復(fù)使用一個(gè)編號(hào)路線

定義：從網(wǎng)絡(luò)圖始點(diǎn)開始，順著箭頭方向前進(jìn)，連續(xù)不斷地到達(dá)終點(diǎn)的一條通道稱為網(wǎng)絡(luò)圖的一條路線。各條路線所需的周期為對(duì)應(yīng)的作業(yè)時(shí)間之和。

關(guān)鍵路線和關(guān)鍵工序：

概念：網(wǎng)絡(luò)圖中所需工時(shí)最長的路線稱為關(guān)鍵路線。關(guān)鍵路線上的工序稱為關(guān)鍵工序

表示方法：關(guān)鍵路線及工序常用雙線表示注意：（1）關(guān)鍵路線的完成時(shí)間決定整個(gè)工程的完工時(shí)間；

（2）關(guān)鍵路線可能不只一條。關(guān)鍵路線越多，組織工作 越好，安排越緊湊；（3）關(guān)鍵路線與非關(guān)鍵路線可以轉(zhuǎn)化。一網(wǎng)絡(luò)圖必須只有一個(gè)網(wǎng)絡(luò)始點(diǎn)和一個(gè)終點(diǎn)。二網(wǎng)絡(luò)圖是有方向的，不允許出現(xiàn)回路。三直接連接兩個(gè)相鄰結(jié)點(diǎn)之間的工作只能有一個(gè)。四邏輯關(guān)系正確，箭線兩端必須必須有節(jié)點(diǎn)。五正確運(yùn)用虛工作。一、網(wǎng)絡(luò)圖的繪制原則網(wǎng)絡(luò)圖必須只有一個(gè)網(wǎng)絡(luò)始點(diǎn)和一個(gè)終點(diǎn)

23543’145321錯(cuò)對(duì)二網(wǎng)絡(luò)圖是有方向的，不允許出現(xiàn)回路

12345BACDE錯(cuò)三直接連接兩個(gè)相鄰結(jié)點(diǎn)之間的工作只能有一個(gè)3543453’’3’DCBADCBA錯(cuò)對(duì)箭線首尾必有結(jié)點(diǎn)，不能從箭線中間引出另一條箭線

14131211131211配砂造型造型配砂2配砂1對(duì)錯(cuò)五虛作業(yè)的運(yùn)用不消耗資源，表示邏輯關(guān)系。必要時(shí)加虛節(jié)點(diǎn)。虛工作應(yīng)用12AB321AB工作緊前ABCD----AA,BDCBA42135456虛工作應(yīng)用12AB321AB工作緊前ABCD----AA,BDCBA42135456DCBA2143虛工作應(yīng)用（平行與交叉）13212A12435A3A2A1444BBA:修路基B:鋪軌道A=A1+A2+A3B=B1+B2+B313578642A1B2B1A3A2B31212作業(yè)名稱和內(nèi)容作業(yè)代號(hào)后續(xù)作業(yè)代號(hào)作業(yè)長度（月）設(shè)計(jì)AB、C1基本建設(shè)BD8訂購設(shè)備CD3安裝設(shè)備DE6試車E結(jié)束1124563ABDEC18613作業(yè)名稱和內(nèi)容作業(yè)代號(hào)后續(xù)作業(yè)代號(hào)作業(yè)長度（月）設(shè)計(jì)AB、C1基本建設(shè)BD8訂購設(shè)備CD3安裝設(shè)備DE6試車E結(jié)束1ABCDABCDB和C沒有前后關(guān)系，用虛工作表示A和D的前后關(guān)系。ABACD另一例：關(guān)系如下，如何合在一起？ABCDACEABCDEABCDE另一例：如何處理？？？OK網(wǎng)絡(luò)圖的繪制步驟一定義各項(xiàng)作業(yè)（工作）恰當(dāng)?shù)卮_定各項(xiàng)工作范圍，以使網(wǎng)絡(luò)圖復(fù)雜程度適中二

編制工作表（示例）

（1）列出各項(xiàng)作業(yè)清單

（2）確定或估計(jì)各項(xiàng)作業(yè)時(shí)間

（3）表明各項(xiàng)作業(yè)之間的邏輯關(guān)系三畫網(wǎng)絡(luò)圖（1）確定各項(xiàng)作業(yè)層次：無緊前作業(yè)的層次為1；其它各作業(yè)層次數(shù)=緊前作業(yè)層次中最大者+1（2）畫草圖（3）畫正圖（4）進(jìn)行節(jié)點(diǎn)編號(hào)(1)任務(wù)分解二、實(shí)例工作工作內(nèi)容緊前工作工時(shí)（周）ABCDEFGHIJKL市場(chǎng)調(diào)查資金籌備需求分析產(chǎn)品設(shè)計(jì)產(chǎn)品研制制定成本計(jì)劃制定生產(chǎn)計(jì)劃籌備設(shè)備籌備原材料安裝設(shè)備調(diào)集人員準(zhǔn)備開工投產(chǎn)／／AADC,EFB,GB,GHGI,J,K4103682328521(2)繪制網(wǎng)絡(luò)圖

（盡量用水平和豎直線）12345678910AFECDGKIHJLB4103682328251ABCDEFGHIJKL緊前／／AADC,EFB,GB,GHGI,J,K(3)節(jié)點(diǎn)編號(hào)箭尾編號(hào)小于箭頭編號(hào)。進(jìn)入節(jié)點(diǎn)的所有箭頭的箭尾都必須編號(hào)，該節(jié)點(diǎn)才能編號(hào)三、網(wǎng)絡(luò)計(jì)劃的分類（一）按性質(zhì)分類

1.確定型網(wǎng)絡(luò)計(jì)劃

2.概率型網(wǎng)絡(luò)計(jì)劃（二）按表示方法分類

1.單代號(hào)

2.雙代號(hào)（三）按目標(biāo)分類

1.單目標(biāo)網(wǎng)絡(luò)計(jì)劃

2.多目標(biāo)網(wǎng)絡(luò)計(jì)劃（四）按有無時(shí)間坐標(biāo)分類

1.時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃

2.非時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃（五）按層次分類

1.總網(wǎng)絡(luò)計(jì)劃

2.局部網(wǎng)絡(luò)計(jì)劃（六）按工作銜接特點(diǎn)分類

1.普通網(wǎng)絡(luò)計(jì)劃

2.搭接網(wǎng)絡(luò)計(jì)劃

3.流水網(wǎng)絡(luò)計(jì)劃第二節(jié)時(shí)間參數(shù)計(jì)算例9-3四條路線1-2-3-5-8：131-2-4-6-7-8：171-2-6-7-8：121-2-3-4-6-7-8：21關(guān)鍵線路決定工期，各項(xiàng)工作有輕重緩急之分。158236474523421342一、作業(yè)時(shí)間t(i,j)的確定完成某一工序所需要的時(shí)間（1）確定型資源確定，時(shí)間可確定計(jì)算（2）概率型（三點(diǎn)時(shí)間估計(jì)）樂觀時(shí)間：在順利情況下，完成工序所需要的最少時(shí)間，常用符號(hào)a表示；最可能時(shí)間：在正常情況下，完成工序所需要的時(shí)間，常用符號(hào)m表示；悲觀時(shí)間：在不順利情況下，完成工序所需要的最多時(shí)間，常用符合b表示。二、事項(xiàng)時(shí)間參數(shù)(1)事項(xiàng)最早時(shí)間(后面工作的最早可能開工時(shí)間)tE(i)：與事項(xiàng)j相鄰的各緊前事項(xiàng)的最早時(shí)間。tE(n)=總最早完工期。從前向后計(jì)算，取大值（2）事項(xiàng)最遲時(shí)間(后面工作的最遲必須開工時(shí)間)

tL(j)：與事項(xiàng)i相鄰的各緊后事項(xiàng)的最遲時(shí)間。確定工期，從右向左計(jì)算取小值。

三、工作的時(shí)間參數(shù)1.最早可能開工時(shí)間與最早可能完工時(shí)間。

tES(i,j)（i事項(xiàng)最早時(shí)間），tEF(i,j)1.所有從總開工事項(xiàng)出發(fā)的工作(1,j),其最早可能開工時(shí)間=0；2.任一工作(i,j)其最早可能開工時(shí)間,要與它的所有的緊前工作（k,i）的最早開工時(shí)間決定；3.工作(i,j)其最早完工時(shí)間等于其最早開工時(shí)間與工時(shí)之和。2.最遲必須開工時(shí)間與最遲必須完工時(shí)間。

tLS(i,j)，tLF(i,j)(j事項(xiàng)最遲時(shí)間)1.總完工事項(xiàng)的工作(i,n),其最遲完工時(shí)間=預(yù)定總工期或者等于這個(gè)工作的最早可能完工時(shí)間；2.任一工作(i,j)其最遲必須開工時(shí)間,要與它的所有的緊后工作（j,k）的最遲開工時(shí)間決定；3.工作(i,j)其最遲完工時(shí)間等于其最遲開工時(shí)間與工時(shí)之和。四、時(shí)差：工作的機(jī)動(dòng)時(shí)間或富裕時(shí)間（1）工作總時(shí)差不影響總工期的最多機(jī)動(dòng)時(shí)間。某工作可以延遲其開工時(shí)間的最大幅度。（2）工作單時(shí)差不影響緊后工作的最早開工時(shí)間。工作及時(shí)差關(guān)系工作AES工作A的緊后工作ESEFLFLFEFLSLS總時(shí)差單時(shí)差(自由浮動(dòng))例118972310654468322382510041018202323253132323126232320181040044101820232323232531010041513182029232324263110tEStLSRr001100000013611001100006130100五、時(shí)間參數(shù)的圖上計(jì)算法六、表上計(jì)算法見下表

原則：工作的排列應(yīng)嚴(yán)格按照箭尾事項(xiàng)編號(hào)由小到大的順序排列，箭尾事項(xiàng)相同的工作，按其箭頭事項(xiàng)有小到大排列。工作工作工時(shí)t(i,j)最早開工tES(i,j)最早完工tEF(i,j)最遲開工tLS(i,j)最遲完工tLF(i,j)總時(shí)差R(i,j)單時(shí)差r(i,j)關(guān)鍵工作箭尾i箭頭j12345678910①①②②③④⑤⑥⑥⑦⑦⑧⑨②⑦③④④⑤⑥⑦⑨⑧⑨⑨⑩4106382302285104010410471018182020232323232523252331253031323231312631232624312923232320201818101815104231340013011000061010013011000060010********第三節(jié)網(wǎng)絡(luò)計(jì)劃的優(yōu)化應(yīng)從工期、成本、資源消耗等方面綜合評(píng)價(jià)。一、把串聯(lián)工作改為平行工作或平行交叉工作。124444二、利用時(shí)差盡量利用單時(shí)差，其次總時(shí)差。非關(guān)鍵路上的工作有時(shí)差，可以考慮放慢非關(guān)鍵工作的進(jìn)度，減少其資源，轉(zhuǎn)去支援關(guān)鍵工作。三、資源配置優(yōu)化12354642234395763134時(shí)間人數(shù)1234567891001114235642234395763134時(shí)標(biāo)網(wǎng)絡(luò)圖0人數(shù)5102015181920951總時(shí)差按照最早開工時(shí)間安排，人力需求不均勻1234567891001114235642234395763134時(shí)標(biāo)網(wǎng)絡(luò)圖0人數(shù)51020159192018511、盡量保證關(guān)鍵工作的日資源需求量。2、利用非關(guān)鍵工作的時(shí)差錯(cuò)開各工作的使用資源時(shí)間。3、在技術(shù)允許下，可適當(dāng)延長時(shí)差大的工作的工時(shí)，或切斷某些非關(guān)鍵工作，減少日總需求量。1234567891001114235642234395763134時(shí)標(biāo)網(wǎng)絡(luò)圖0人數(shù)510201591020181411234567891001114235642234395763134時(shí)標(biāo)網(wǎng)絡(luò)圖0人數(shù)51020159107910四、工期費(fèi)用優(yōu)化直接費(fèi)用：指人工、材料、能源等與各項(xiàng)活動(dòng)直接有關(guān)的費(fèi)用；活動(dòng)作業(yè)時(shí)間越短，直接費(fèi)用就越大。間接費(fèi)用：指管理費(fèi)用，銷售費(fèi)用等費(fèi)用；它與各項(xiàng)活動(dòng)時(shí)間無直接關(guān)系，而與工程周期長短直接相關(guān)。工程費(fèi)用與工期關(guān)系圖0直接費(fèi)用間接費(fèi)用總費(fèi)用費(fèi)用時(shí)間直接費(fèi)用的計(jì)算假定直接費(fèi)用與工期為線性關(guān)系，如圖：MdMijmijDij費(fèi)用時(shí)間BA

dijmij為極限費(fèi)用；Mij為正常費(fèi)用；dij為極限工期；Dij為正常工期；d為壓縮后的作業(yè)時(shí)間；M為壓縮后的直接費(fèi)用幾個(gè)概念Mij指當(dāng)工期延長到—定程度，直接費(fèi)用不能再隨之下降時(shí)的費(fèi)用；Dij指對(duì)應(yīng)正常費(fèi)用（Mij

）的工期；mij指當(dāng)工期縮短到一定程度，再增加直接費(fèi)用，工期也不能再縮短時(shí)的費(fèi)用；

dij指對(duì)應(yīng)極限費(fèi)用（mij

）的工期。直接費(fèi)用變動(dòng)率指活動(dòng)作業(yè)時(shí)間每縮短或延長一個(gè)單位時(shí)間所需增加或減少的費(fèi)用。結(jié)論：直接費(fèi)用變動(dòng)率越大，則縮短工期而增加的直接費(fèi)用越多。時(shí)間——費(fèi)用優(yōu)化時(shí)，首先應(yīng)縮短關(guān)鍵線路上cij值最小的活動(dòng)作業(yè)時(shí)間。間接費(fèi)用的計(jì)算設(shè)單位時(shí)間間接費(fèi)用額為Cj

則工期Tx對(duì)應(yīng)的間接費(fèi)用CJ為：CJ=CjTx

（三）時(shí)間—費(fèi)用優(yōu)化的原則①關(guān)鍵線路上的活動(dòng)優(yōu)先；②直接費(fèi)用變化率小的活動(dòng)優(yōu)先；③逐次壓縮活動(dòng)的作業(yè)時(shí)間以不超過趕工時(shí)間為限；具體步驟：用正常作業(yè)時(shí)間計(jì)算網(wǎng)絡(luò)時(shí)間參數(shù)、活動(dòng)直接費(fèi)用變化率及工程周期。計(jì)算正常時(shí)間條件下的工程總費(fèi)用。逐步壓縮關(guān)鍵線路的延續(xù)時(shí)間，找出最低費(fèi)用及最佳工期。注意：每次優(yōu)化以后，會(huì)引起關(guān)鍵線路的變化，因而要重新繪制網(wǎng)絡(luò)圖，尋找出關(guān)鍵線路。

例3

工作

正常工時(shí)

特急工時(shí)成本斜率cij(元／d)時(shí)間(d)費(fèi)用(元)時(shí)間(d)費(fèi)用(元)①－②②－③②－④③－④③－⑤④－⑥⑤－⑥2430222624