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

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

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

以工序為縱坐標,以線條長短表示一項工作或作業(yè)的開始和完成時刻以及工作的進展情況。由于甘特圖以條形圖進行系統(tǒng)計劃和管理,故又稱為橫道圖、條形圖等(見圖6-1)。

圖6-1甘特圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)如果每個活動都按時完成,項目需要多久完工?

(2)如果項目要盡快完工,每個活動的工作時間窗口是什么?

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

(4)如果有不確定性存在,項目按時完成的概率怎么計算?

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

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

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

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

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

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

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

6.3.2幾個時間參數(shù)的計算

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

(1)最早開始時間(ES)和最早完成時間(EF)。

任何活動的最早開始時間都決定于其所有緊前活動的最早完成時間,任何活動的最早完成時間都等于其最早開始時間加上本身所需要的時間,因此有

例如,在圖6-3中,首先將沒有緊前活動的活動A的最早開始時間設(shè)為0,則其最早完成時間EF=3,然后,對于B和C來講,最早開始時間都等于A的最早完成時間,然后依次進行計算,計算的順序參見圖6-5中Step的序號。

圖6-5最早開始時間和最早完成時間的計算

(2)最晚完成時間(LF)和最晚開始時間(LS)。

最晚完成時間和最晚開始時間,就是在保證整個項目最后一個活動的最早完成時間等于最晚完成時間的情況下,從后往前計算各個活動的最晚完成時間和最晚開始時間。在所

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

例如,在圖6-5中,首先將沒有直接后續(xù)活動的活動K的最晚完成時間(LF)設(shè)為活動K的最早完成時間(EF),這樣就可以保證整個項目的工期不被拖后?；顒覭的最晚開始時間(LS)等于最晚完成時間減去活動K本身所需要的時間。然后可以計算以K為直接后續(xù)活動的J的最晚完成時間(LF),等于活動K的最晚開始時間,然后依次進行計算,計算步驟如圖6-6中Step的序號所示。

圖6-6-項目活動的最晚完成時間和最晚開始時間

(3)可松弛時間。

可松弛時間就是某個活動在不影響整個項目工期的情況下,可以進行活動的時間窗口,其計算公式如下:

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

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

6.4計劃評審技術(shù)PERT

樂觀時間to表示活動完成的樂觀估計時間,即在順利情況下完成某個活動所需的時間。最可能時間tm

表示活動完成的最可能估計時間,即在正常情況下完成某個活動所需的時間。悲觀時間tp表示活動完成的悲觀估計時間,即在不利情況下完成某個活動所需的時間。

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

活動所需時間的期望為

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

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

需要注意的是,這里的活動所需時間的期望和方差,均是估計值。

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

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

其中,μi為活動i所需時間的期望。

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

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

其中,σi2為活動i所需時間的方差。

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

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

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

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

6.5時間－費用優(yōu)化

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

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

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

綜合來說