運(yùn)籌學(xué)基礎(chǔ) 課件 第6章

第6章網(wǎng)絡(luò)計(jì)劃6.1網(wǎng)絡(luò)計(jì)劃的發(fā)展歷程6.2網(wǎng)絡(luò)建模6.3關(guān)鍵路線(xiàn)法CPM6.4計(jì)劃評(píng)審技術(shù)PERT6.5時(shí)間－費(fèi)用優(yōu)化

最早提出的統(tǒng)籌方法是甘特圖法,該方法是科學(xué)管理的奠基人泰勒的學(xué)生,美國(guó)?？颂m兵工廠(chǎng)顧問(wèn)甘特于20世紀(jì)40年代開(kāi)發(fā)的一種計(jì)劃與管理技術(shù)。甘特圖以時(shí)間為橫坐標(biāo),

以工序?yàn)榭v坐標(biāo),以線(xiàn)條長(zhǎng)短表示一項(xiàng)工作或作業(yè)的開(kāi)始和完成時(shí)刻以及工作的進(jìn)展情況。由于甘特圖以條形圖進(jìn)行系統(tǒng)計(jì)劃和管理,故又稱(chēng)為橫道圖、條形圖等(見(jiàn)圖6-1)。

圖6-1甘特圖

甘特圖的優(yōu)點(diǎn)是簡(jiǎn)單明了、容易繪制、使用方便。甘特圖的缺陷是:

(1)不能反映各項(xiàng)工作之間錯(cuò)綜復(fù)雜的聯(lián)系和制約的分工協(xié)作關(guān)系;

(2)不能區(qū)別系統(tǒng)中哪些工作是主要的、關(guān)鍵的生產(chǎn)聯(lián)系和工序,反映不出全局的關(guān)鍵所在,不利于最合理地管理整個(gè)系統(tǒng)。

6.1網(wǎng)絡(luò)計(jì)劃的發(fā)展歷程

PERT方法的優(yōu)化流程為:依據(jù)工作流程繪制網(wǎng)絡(luò)圖,計(jì)算網(wǎng)絡(luò)圖參數(shù),然后進(jìn)行網(wǎng)絡(luò)圖的優(yōu)化。網(wǎng)絡(luò)圖的優(yōu)化以尋找關(guān)鍵路線(xiàn)為要點(diǎn),在關(guān)鍵路線(xiàn)上尋找最有利的工序來(lái)縮短關(guān)鍵活動(dòng)的時(shí)間,在可能的條件下將工序進(jìn)一步細(xì)分,采用平行作業(yè)或交叉作業(yè)的方法使工期縮短。

縮短關(guān)鍵路線(xiàn)的方法有三種:

一是從非關(guān)鍵路線(xiàn)上抽調(diào)資源(人力、物力、財(cái)力等)集中于關(guān)鍵路線(xiàn),以縮短關(guān)鍵路線(xiàn)的時(shí)間;

二是通過(guò)增加資源的方法來(lái)縮短關(guān)鍵路線(xiàn)上完成任務(wù)的期限;

三是采用新技術(shù)、新工藝等措施,縮短某些工序的時(shí)間,從而達(dá)到縮短關(guān)鍵路線(xiàn)時(shí)間的目的。

PM和PERT在原理上十分相似,都是采用網(wǎng)絡(luò)模型,只是在工序時(shí)間的確定上有所差別。由于PERT是軍方首創(chuàng),對(duì)時(shí)間進(jìn)度最為關(guān)心,而CPM是民間首創(chuàng),對(duì)成本非常重視。一開(kāi)始兩種方法的側(cè)重點(diǎn)略有差異,但在后來(lái)的使用與發(fā)展中逐漸靠攏并融為一體。

6.2網(wǎng)絡(luò)建模

項(xiàng)目由一系列活動(dòng)組成,活動(dòng)的完成需要時(shí)間,不同的活動(dòng)之間有相互的依存關(guān)系。在利用網(wǎng)絡(luò)描述項(xiàng)目的時(shí)候,可以使用點(diǎn)來(lái)代表活動(dòng),使用有向邊代表活動(dòng)之間的先后依存關(guān)系,如圖6-2所示。

圖6-2網(wǎng)絡(luò)中活動(dòng)的先后關(guān)系

網(wǎng)絡(luò)建模的步驟如下:

(1)分解出相對(duì)獨(dú)立的活動(dòng)。分解出相對(duì)獨(dú)立的活動(dòng)就是將一項(xiàng)任務(wù)分解成若干項(xiàng)活動(dòng),分析并確定各項(xiàng)活動(dòng)在工藝和組織方面的相互聯(lián)系及相互制約關(guān)系。

(2)分析活動(dòng)的順序關(guān)系、依賴(lài)關(guān)系。確定各項(xiàng)活動(dòng)的先后順序,分析各項(xiàng)活動(dòng)的依賴(lài)關(guān)系,確定各項(xiàng)活動(dòng)的所有緊前、緊后活動(dòng)和與它平行的活動(dòng)。

(3)列出活動(dòng)的名稱(chēng)、所需資源。確定各項(xiàng)活動(dòng)的名稱(chēng)、工期、所需資源(人力、物力、時(shí)間)等參數(shù)。

(4)每個(gè)活動(dòng)使用一個(gè)網(wǎng)絡(luò)中的一個(gè)點(diǎn)來(lái)表示,緊前活動(dòng)和當(dāng)前活動(dòng)之間使用一條有向邊連接。

(5)為了便于分析,確保沒(méi)有緊前活動(dòng)的活動(dòng)只有一個(gè),沒(méi)有直接后續(xù)活動(dòng)的活動(dòng)也只有一個(gè)。在所建立的網(wǎng)絡(luò)中,如果有多個(gè)沒(méi)有緊前活動(dòng)的活動(dòng),則增加一個(gè)虛擬的起始活動(dòng),并將其連接到所有的沒(méi)有緊前活動(dòng)的活動(dòng);如果有多個(gè)沒(méi)有直接后續(xù)活動(dòng)的活動(dòng),則增加一個(gè)虛擬的結(jié)束活動(dòng),將所有的沒(méi)有直接后續(xù)活動(dòng)的活動(dòng)連接到虛擬的結(jié)束活動(dòng)。

例6-1經(jīng)過(guò)分解和分析,某項(xiàng)目可以由11個(gè)活動(dòng)組成,這些活動(dòng)之間的關(guān)系和所需時(shí)間如表6-1所示。

利用項(xiàng)目活動(dòng)分解表,可以繪制項(xiàng)目網(wǎng)絡(luò)計(jì)劃的網(wǎng)絡(luò)示意圖如圖6-3所示。圖6-3項(xiàng)目網(wǎng)絡(luò)計(jì)劃的網(wǎng)絡(luò)示意圖

利用網(wǎng)絡(luò)計(jì)劃技術(shù)能夠回答的問(wèn)題包括:

(1)如果每個(gè)活動(dòng)都按時(shí)完成,項(xiàng)目需要多久完工?

(2)如果項(xiàng)目要盡快完工,每個(gè)活動(dòng)的工作時(shí)間窗口是什么?

(3)為了使項(xiàng)目盡快完成,哪些活動(dòng)是瓶頸,哪些活動(dòng)可以拖延,能拖延多久?

(4)如果有不確定性存在,項(xiàng)目按時(shí)完成的概率怎么計(jì)算?

(5)如果有一些額外的預(yù)算,花到什么地方可以使項(xiàng)目盡可能按時(shí)完成?

(6)如果要縮短項(xiàng)目工期,怎樣使增加的費(fèi)用最小?

6.3關(guān)鍵路線(xiàn)法CPM

6.3.1關(guān)鍵路線(xiàn)的計(jì)算關(guān)鍵路線(xiàn)法是最先提出的網(wǎng)絡(luò)計(jì)劃技術(shù)。所謂關(guān)鍵路線(xiàn),就是在項(xiàng)目的網(wǎng)絡(luò)中,從起始活動(dòng)到結(jié)束活動(dòng)所花費(fèi)時(shí)間最長(zhǎng)的路線(xiàn),短于關(guān)鍵路線(xiàn)的路線(xiàn)稱(chēng)為非關(guān)鍵路線(xiàn)。路線(xiàn)的長(zhǎng)度使用路線(xiàn)上所有活動(dòng)花費(fèi)時(shí)間總和計(jì)算。

為了利用最短路算法,可以將網(wǎng)絡(luò)進(jìn)行以下變換:將任意有向邊的長(zhǎng)度設(shè)為其起點(diǎn)活動(dòng)對(duì)應(yīng)的時(shí)間。

例如,對(duì)于圖6-3,就可以變換為如圖6-4所示的普通網(wǎng)絡(luò),在這個(gè)網(wǎng)絡(luò)中,可以利用最短路算法求解從A到K的最長(zhǎng)路。

圖6-4轉(zhuǎn)換為有向邊帶權(quán)值的普通網(wǎng)絡(luò)

6.3.2幾個(gè)時(shí)間參數(shù)的計(jì)算

對(duì)于網(wǎng)絡(luò)中的任意一個(gè)活動(dòng),還可以計(jì)算以下幾個(gè)參數(shù):

(1)最早開(kāi)始時(shí)間(ES)和最早完成時(shí)間(EF)。

任何活動(dòng)的最早開(kāi)始時(shí)間都決定于其所有緊前活動(dòng)的最早完成時(shí)間,任何活動(dòng)的最早完成時(shí)間都等于其最早開(kāi)始時(shí)間加上本身所需要的時(shí)間,因此有

例如,在圖6-3中,首先將沒(méi)有緊前活動(dòng)的活動(dòng)A的最早開(kāi)始時(shí)間設(shè)為0,則其最早完成時(shí)間EF=3,然后,對(duì)于B和C來(lái)講,最早開(kāi)始時(shí)間都等于A的最早完成時(shí)間,然后依次進(jìn)行計(jì)算,計(jì)算的順序參見(jiàn)圖6-5中Step的序號(hào)。

圖6-5最早開(kāi)始時(shí)間和最早完成時(shí)間的計(jì)算

(2)最晚完成時(shí)間(LF)和最晚開(kāi)始時(shí)間(LS)。

最晚完成時(shí)間和最晚開(kāi)始時(shí)間,就是在保證整個(gè)項(xiàng)目最后一個(gè)活動(dòng)的最早完成時(shí)間等于最晚完成時(shí)間的情況下,從后往前計(jì)算各個(gè)活動(dòng)的最晚完成時(shí)間和最晚開(kāi)始時(shí)間。在所

有活動(dòng)的最早開(kāi)始時(shí)間和最早完成時(shí)間已經(jīng)確定的情況下,可以計(jì)算所有活動(dòng)的最晚完成時(shí)間和最晚開(kāi)始時(shí)間,計(jì)算公式為

例如,在圖6-5中,首先將沒(méi)有直接后續(xù)活動(dòng)的活動(dòng)K的最晚完成時(shí)間(LF)設(shè)為活動(dòng)K的最早完成時(shí)間(EF),這樣就可以保證整個(gè)項(xiàng)目的工期不被拖后。活動(dòng)K的最晚開(kāi)始時(shí)間(LS)等于最晚完成時(shí)間減去活動(dòng)K本身所需要的時(shí)間。然后可以計(jì)算以K為直接后續(xù)活動(dòng)的J的最晚完成時(shí)間(LF),等于活動(dòng)K的最晚開(kāi)始時(shí)間,然后依次進(jìn)行計(jì)算,計(jì)算步驟如圖6-6中Step的序號(hào)所示。

圖6-6-項(xiàng)目活動(dòng)的最晚完成時(shí)間和最晚開(kāi)始時(shí)間

(3)可松弛時(shí)間。

可松弛時(shí)間就是某個(gè)活動(dòng)在不影響整個(gè)項(xiàng)目工期的情況下,可以進(jìn)行活動(dòng)的時(shí)間窗口,其計(jì)算公式如下:

例如,對(duì)于圖6-6,可以計(jì)算每個(gè)活動(dòng)的可松弛時(shí)間如圖6-7所示,其中,可松弛時(shí)間為零的關(guān)鍵活動(dòng)使用深色表示。

圖6-7活動(dòng)的可松弛時(shí)間及關(guān)鍵活動(dòng)

6.4計(jì)劃評(píng)審技術(shù)PERT

樂(lè)觀(guān)時(shí)間to表示活動(dòng)完成的樂(lè)觀(guān)估計(jì)時(shí)間,即在順利情況下完成某個(gè)活動(dòng)所需的時(shí)間。最可能時(shí)間tm

表示活動(dòng)完成的最可能估計(jì)時(shí)間,即在正常情況下完成某個(gè)活動(dòng)所需的時(shí)間。悲觀(guān)時(shí)間tp表示活動(dòng)完成的悲觀(guān)估計(jì)時(shí)間,即在不利情況下完成某個(gè)活動(dòng)所需的時(shí)間。

例6-2經(jīng)過(guò)分解和分析,某項(xiàng)目可以由11個(gè)活動(dòng)組成,這些活動(dòng)之間的關(guān)系和所需時(shí)間如表6-2所示。

活動(dòng)所需時(shí)間的期望為

對(duì)于所需時(shí)間的期望μ,這里實(shí)際上是采用了加權(quán)求和的方法,即假設(shè)活動(dòng)最可能完成時(shí)間的權(quán)值為4/6,樂(lè)觀(guān)時(shí)間和悲觀(guān)時(shí)間的權(quán)值為1/6,而4/6≈0.6666,接近于黃金分割率。

在PERT中,假設(shè)所需時(shí)間的概率分布為一種貝塔分布,而對(duì)于貝塔分布來(lái)講,大部分值落在區(qū)間[μ-3σ,μ+3σ]內(nèi)。因此,假設(shè)tp-to=6σ,可以估計(jì)活動(dòng)所需時(shí)間的方差為

需要注意的是,這里的活動(dòng)所需時(shí)間的期望和方差,均是估計(jì)值。

例如,可以在表6-2的基礎(chǔ)上,計(jì)算任一活動(dòng)所需時(shí)間的期望及其方差,如表6-3所示。

如果以活動(dòng)所需時(shí)間的期望μ作為活動(dòng)所需時(shí)間,將隨機(jī)問(wèn)題轉(zhuǎn)化為確定型問(wèn)題,即可采用CPM的方法求解網(wǎng)絡(luò)的關(guān)鍵路線(xiàn),這條關(guān)鍵路線(xiàn)稱(chēng)為PERT的期望關(guān)鍵路線(xiàn)。也就是說(shuō),期望關(guān)鍵路線(xiàn)就是以活動(dòng)所需時(shí)間的期望作為活動(dòng)確定的時(shí)間,在網(wǎng)絡(luò)上得到的關(guān)鍵路線(xiàn)。因此,期望關(guān)鍵路線(xiàn)p的期望長(zhǎng)度為

其中,μi為活動(dòng)i所需時(shí)間的期望。

然而,由于項(xiàng)目活動(dòng)的隨機(jī)性,期望關(guān)鍵路線(xiàn)上的所有活動(dòng)未必都按照期望的時(shí)間完成,也就是說(shuō),期望關(guān)鍵路線(xiàn)p的長(zhǎng)度dp應(yīng)該是一個(gè)隨機(jī)值,且有

如果所有活動(dòng)所需時(shí)間是相互獨(dú)立(需要注意的是,這個(gè)假設(shè)有的時(shí)候并不成立,有的時(shí)候,影響一個(gè)活動(dòng)的因素,也會(huì)影響另外一個(gè)活動(dòng)),且具有相同的分布,則dp的方差為

其中,σi2為活動(dòng)i所需時(shí)間的方差。

例如,利用表6-3可以得到網(wǎng)絡(luò)的期望關(guān)鍵路徑如圖6-8所示,網(wǎng)絡(luò)中的活動(dòng)的所需時(shí)間均使用期望時(shí)間表示,則期望關(guān)鍵路徑p為A—C—D—E—G—I—J—K,期望長(zhǎng)度為μp=53.67,期望方差為σ2p=7.72。

圖6-8網(wǎng)絡(luò)的期望關(guān)鍵路徑

同理,網(wǎng)絡(luò)上的其他路線(xiàn)也可以按照同樣的假設(shè)和公式計(jì)算期望長(zhǎng)度及其方差,所有路線(xiàn)長(zhǎng)度的期望值和方差如表6-4所示。

例如,對(duì)于表6-4中的不同路徑,計(jì)算在40周內(nèi)完成的概率如表6-5所示。

6.5時(shí)間－費(fèi)用優(yōu)化

時(shí)間費(fèi)用優(yōu)化的目的主要是解決如何縮短總工期至規(guī)定值并最小化費(fèi)用的問(wèn)題。如果總工期小于規(guī)定的工期,則說(shuō)明項(xiàng)目的時(shí)間要求并不緊迫,關(guān)鍵路線(xiàn)還可延長(zhǎng),可降低資源投入的強(qiáng)度。如果總工期等于規(guī)定的工期,則說(shuō)明此計(jì)劃較合適,無(wú)須調(diào)整。如果總工期大于規(guī)定的工期,則說(shuō)明計(jì)劃的總工期不能滿(mǎn)足實(shí)際需求,需對(duì)項(xiàng)目計(jì)劃進(jìn)行修改和調(diào)整。

例如,對(duì)于圖6-9所示的網(wǎng)絡(luò),關(guān)鍵路線(xiàn)的總長(zhǎng)度為45,如果將關(guān)鍵活動(dòng)E所需的時(shí)間從15縮短為1,則重新計(jì)算網(wǎng)絡(luò)的時(shí)間參數(shù),可得關(guān)鍵路線(xiàn)的總長(zhǎng)度為35,調(diào)整后的關(guān)鍵路線(xiàn)總共縮短了10,與關(guān)鍵活動(dòng)E縮短的時(shí)間14并不相等,因?yàn)殛P(guān)鍵路線(xiàn)發(fā)生了轉(zhuǎn)移。

圖6-9關(guān)鍵活動(dòng)時(shí)間的縮短與總工期的縮短并不一定等額

綜合來(lái)說(shuō)