《運(yùn)籌學(xué)》8關(guān)鍵路線法解讀課件

第八章計(jì)劃評審方法和關(guān)鍵路線方法第八章1網(wǎng)絡(luò)計(jì)劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計(jì)劃方法是項(xiàng)目計(jì)劃管理的重要方法。它起源于美國。當(dāng)時(shí)，有兩種網(wǎng)絡(luò)計(jì)劃方法：關(guān)鍵路線法和計(jì)劃評審技術(shù)。1957年，美國杜邦化學(xué)公司用關(guān)鍵路線法(CriticalPathMethod)。當(dāng)年就節(jié)約100萬美元，為該公司用于該項(xiàng)目研究費(fèi)用的5倍以上。1958年，美國海軍當(dāng)局在研制北極星導(dǎo)彈潛艇時(shí)，第一次采用了BuzzAllen提出的計(jì)劃評審技術(shù)(ProgramEvaluationandReviewTechnique),主要承包商200多家，轉(zhuǎn)包商10000家。23個(gè)系統(tǒng)網(wǎng)絡(luò)，每兩周檢查一次，原定6年，提前兩年完成，節(jié)約經(jīng)費(fèi)10—15％。60年代耗時(shí)11年阿波羅登月計(jì)劃3000億$,42萬人,2萬家公司,120所大學(xué),600臺計(jì)算機(jī),700萬零件,終于在1969年7月，阿波羅11號船長阿姆斯特朗登上月球。網(wǎng)絡(luò)計(jì)劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計(jì)劃方法是項(xiàng)目計(jì)劃管理的重要方法260-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做了大量工作。華羅庚的例子：有客來訪，要請他飲茶，于是要做幾件事：洗茶杯、洗杯蓋、燒開水、泡茶到端茶。60-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做3客來沏茶本問題的幾道“工序”有次序,洗杯蓋端茶燒水泡茶洗杯虛時(shí)間:251020.5客來沏茶本問題的幾道“工序”有次序,洗杯蓋4第一節(jié)PERT網(wǎng)絡(luò)圖第一節(jié)PERT網(wǎng)絡(luò)圖5網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(diǎn)(事件)、箭線（作業(yè)）和路線。132一、網(wǎng)絡(luò)圖構(gòu)成網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(diǎn)(事件)、箭線（作業(yè)）和路線。136箭線:

1、代表計(jì)劃中的一項(xiàng)作業(yè)或工序，包括人力、財(cái)力、物力的付出。2、作業(yè)的內(nèi)容可大可小，可多可少。3、箭尾表示作業(yè)開始，箭頭表示作業(yè)結(jié)束4、通常把作業(yè)的代號和作業(yè)所耗時(shí)間標(biāo)在箭線的上下。5、虛箭線：不占用時(shí)間和空間，不消耗任何資源。只是為了明確活動(dòng)的相互之間的邏輯關(guān)系。

3445A

10AijA：作業(yè)活動(dòng)代號3445AAijA：作業(yè)活動(dòng)代號7結(jié)點(diǎn)（表示事件）：

網(wǎng)絡(luò)圖中兩條或兩條以上的箭線的交接點(diǎn)就是結(jié)點(diǎn)，結(jié)點(diǎn)代表的作業(yè)開始和結(jié)束。用圓圈加上數(shù)字表示。

路線：從網(wǎng)絡(luò)圖的始點(diǎn)事件開始到終點(diǎn)事件為止，由一系列首尾相連的箭線和結(jié)點(diǎn)所代表的作業(yè)和事件所組成的通道。網(wǎng)絡(luò)圖一般有多條路線。其中最長的我們稱之為關(guān)鍵路線，關(guān)鍵路線上的工序?yàn)殛P(guān)鍵工序。結(jié)點(diǎn)（表示事件）：8（錯(cuò)誤）135624正確135624PERT圖的開始節(jié)點(diǎn)與結(jié)束節(jié)點(diǎn)均應(yīng)是唯一的。二、繪制PERT圖的原則如果在實(shí)際工作中發(fā)生不吻合時(shí)，應(yīng)將沒有緊前作業(yè)的結(jié)點(diǎn)用虛箭頭線同網(wǎng)絡(luò)始點(diǎn)事項(xiàng)連接起來，將沒有后續(xù)事項(xiàng)的結(jié)點(diǎn)用虛箭頭同終點(diǎn)事項(xiàng)邊接起來。（錯(cuò)誤）135624正確135624PERT圖的開始節(jié)點(diǎn)與結(jié)9錯(cuò)誤正確在相鄰的兩個(gè)節(jié)點(diǎn)之間，最多只能有一條箭線相連。進(jìn)入某一個(gè)結(jié)點(diǎn)的箭線可以有多條，但其它任何結(jié)點(diǎn)直接連接該結(jié)點(diǎn)的箭線只能有一條。兩個(gè)相鄰結(jié)點(diǎn)間只允許有一條箭線直接相連。若有平行活動(dòng)，可引入虛線以保證這一規(guī)則不被破壞。錯(cuò)誤正確在相鄰的兩個(gè)節(jié)點(diǎn)之間，最多只能有一條箭線相連。進(jìn)入某10錯(cuò)誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路錯(cuò)誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路11

節(jié)點(diǎn)編號時(shí)，按照矢線箭頭的指向，升序排號，保證節(jié)點(diǎn)序號先后關(guān)系保持一致。應(yīng)將各作業(yè)的工時(shí)數(shù)據(jù)標(biāo)注在表示該作業(yè)的矢線的下面。

正確使用虛工序（不消耗資源，一般表示平行工作關(guān)系）節(jié)點(diǎn)編號時(shí)，按照矢線箭頭的指向，升序排號，保證節(jié)點(diǎn)序號先后12三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如下：@根據(jù)活動(dòng)清單中規(guī)定的關(guān)系，將活動(dòng)代號欄所有的活動(dòng)逐次地畫在網(wǎng)絡(luò)圖上，從左到右@理順活動(dòng)的緊前、緊后關(guān)系，沒有緊后活動(dòng)的活動(dòng)所對應(yīng)的箭線匯集在終止結(jié)點(diǎn)上@草圖繪制完成后，將序號標(biāo)在結(jié)點(diǎn)上，將活動(dòng)代號和時(shí)間標(biāo)在箭線上@檢查無誤后，將草圖繪制成規(guī)范圖

三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如13作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，H作業(yè)時(shí)間D15151410661308例：某項(xiàng)工程任務(wù)經(jīng)分解后，確定由9項(xiàng)作業(yè)構(gòu)成，各項(xiàng)作業(yè)的代號、緊前作業(yè)及作業(yè)時(shí)間如表所示，畫出網(wǎng)絡(luò)圖作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，141412346578A15B15CE6D10G1H30F6I81412346578A15B15CE6D10G1H30F6I15序號施工項(xiàng)目所需時(shí)間（月）工序代號緊前項(xiàng)目12345678清理地面打地基砌墻安裝電線粉刷畫圖案室內(nèi)工程上屋頂14434645ABCDEF

G

HA

BDD，HCEC例：建筑一幢房屋，施工順序如上表所示，要求計(jì)算工程周期及關(guān)鍵路線序號施工項(xiàng)目所需時(shí)間（月）工序代號緊前項(xiàng)目1清理地面1A例：16E51 2346785ABCDG144H344E51 2346785ABCDG144H3417活動(dòng)代號活動(dòng)描述緊后活動(dòng)活動(dòng)時(shí)間（周）ABCDEFGHIJKL系統(tǒng)分析和總體設(shè)計(jì)輸入和輸出設(shè)計(jì)模塊1詳細(xì)設(shè)計(jì)輸入和輸出程序設(shè)計(jì)模塊1程序設(shè)計(jì)模塊2詳細(xì)設(shè)計(jì)輸入和輸出及模塊1測試模塊2程序設(shè)計(jì)模塊1測試系統(tǒng)總調(diào)試穩(wěn)當(dāng)編寫系統(tǒng)測試B,CDE,FG,IG,IHJI,KJL無無346885363583某機(jī)械廠管理信息系統(tǒng)開發(fā)活動(dòng)清單例活動(dòng)代號活動(dòng)描述緊后活動(dòng)活動(dòng)時(shí)間（周）A系統(tǒng)分析和總體設(shè)計(jì)B1812346109857A3B4

C6D8E8F5H6G3J5L3K8I312346109857AB4CDEFHGJLKI319四、PERT圖的分類（1）按工時(shí)估計(jì)的性質(zhì)：A：確定型網(wǎng)絡(luò)，每個(gè)工作的預(yù)計(jì)工時(shí)只估一個(gè)值，即，這些工作的實(shí)際完成情況一般地可按預(yù)計(jì)工時(shí)達(dá)到，也即實(shí)現(xiàn)的概率等于或近似等于1。B：概率型網(wǎng)絡(luò)，每個(gè)工作按三種情況下給定工時(shí)，最快可能完成工時(shí)，最可能完成工時(shí)，最慢可能完成工時(shí)。四、PERT圖的分類（1）按工時(shí)估計(jì)的性質(zhì)：20五、PERT圖的計(jì)算1.工作時(shí)間tij的確定:確定型:利用已知的工時(shí)定額資料給出。概率型：對于開發(fā)性任務(wù)，或?qū)ぷ魉璧墓r(shí)難以準(zhǔn)確估計(jì)時(shí)，可采用三點(diǎn)時(shí)間法來確定工作的工時(shí)。

五、PERT圖的計(jì)算1.工作時(shí)間tij的確定:21則實(shí)際計(jì)算中，完成一項(xiàng)作業(yè)的期望工時(shí)t(i,j)按如下公式計(jì)算：設(shè)：a是最樂觀的時(shí)間估計(jì)值，m是最可能的估計(jì)值，b是最悲觀的時(shí)間估計(jì)值方差為：則實(shí)際計(jì)算中，完成一項(xiàng)作業(yè)的期望工時(shí)t(i,j)按如下公式計(jì)222.結(jié)點(diǎn)（事項(xiàng)）的時(shí)間參數(shù)確定：（1）節(jié)點(diǎn)的最早時(shí)間：它表明以它為始點(diǎn)的各工作最早可能開始的時(shí)間，也表明以它為終點(diǎn)的各工作的最早可能完成時(shí)間。等于從始點(diǎn)結(jié)點(diǎn)到該結(jié)點(diǎn)的最長路線上所有工作的工時(shí)總和。遞推公式：：整個(gè)工程的總最早完工期2.結(jié)點(diǎn)（事項(xiàng)）的時(shí)間參數(shù)確定：（1）節(jié)點(diǎn)的最早時(shí)間：它表23（2）節(jié)點(diǎn)的最遲時(shí)間：它表明在不影響任務(wù)總工期的條件下，以它為始點(diǎn)的各工作最遲必須開始的時(shí)間，也表明以它為終點(diǎn)的各工作的最遲必須完成時(shí)間。由于，一般都把任務(wù)的最早完工時(shí)間作為任務(wù)的總工期，所以結(jié)點(diǎn)的最遲時(shí)間遞推公式為：（2）節(jié)點(diǎn)的最遲時(shí)間：它表明在不影響任務(wù)總工期的條件下，以它243.工作的時(shí)間參數(shù)確定：1。作業(yè)的最早可能開始時(shí)間（ES）是指作業(yè)最早可能開始的時(shí)間，是它的各項(xiàng)緊前作業(yè)最早結(jié)束的時(shí)間中最大的一個(gè)。2。作業(yè)的最早可能結(jié)束時(shí)間（EF）

是指作業(yè)按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間。3.工作的時(shí)間參數(shù)確定：1。作業(yè)的最早可能開始時(shí)間（ES）253.作業(yè)的最遲必須開工時(shí)間（LS）是指作業(yè)（i,j）在不影響整個(gè)任務(wù)如期完工的前提下，必須開始的最晚時(shí)間。

4.作業(yè)的最遲必須結(jié)束時(shí)間（LF）

是指作業(yè)（i,j）按最遲時(shí)間開工，所能達(dá)到的完工時(shí)間。3.作業(yè)的最遲必須開工時(shí)間（LS）264.時(shí)差：按性質(zhì)可以分為作業(yè)的總時(shí)差R（i,j）和作業(yè)的自由時(shí)差F（i,j）?？倳r(shí)差：在不影響任務(wù)總工期的條件下，某工作（i,j）可以延遲其開工時(shí)間的最大幅度。這是網(wǎng)絡(luò)上多于一項(xiàng)作業(yè)共同擁有的機(jī)動(dòng)時(shí)間，并非為某項(xiàng)作業(yè)單獨(dú)擁有。工作（i,j）的總時(shí)差等于它的最遲完工時(shí)間與最早完工時(shí)間的差，也等于它的最遲開工時(shí)間與最早開工時(shí)間的差。4.時(shí)差：總時(shí)差：在不影響任務(wù)總工期的條件下，某工作（i,27自由時(shí)差：不影響它的各項(xiàng)緊后作業(yè)最早開工時(shí)間條件下，該項(xiàng)作業(yè)可以推遲的開工時(shí)間的最大限度，它是一項(xiàng)作業(yè)獨(dú)自擁有的機(jī)動(dòng)時(shí)間。即自由時(shí)差等于其緊后作業(yè)的最早開工時(shí)間與本工作的最早完工時(shí)間的差。自由時(shí)差：不影響它的各項(xiàng)緊后作業(yè)最早開工時(shí)間條件下，該項(xiàng)作業(yè)28下圖是一個(gè)工程施工圖，請依次求出各時(shí)間參數(shù)。

時(shí)間參數(shù)計(jì)算舉例下圖是一個(gè)工程施工圖，請依次求出各時(shí)間參數(shù)。291。結(jié)點(diǎn)時(shí)間參數(shù)：方括號－最早時(shí)間，三角－最晚時(shí)間1。結(jié)點(diǎn)時(shí)間參數(shù)：方括號－最早時(shí)間，三角－最晚時(shí)間302。作業(yè)時(shí)間參數(shù)：方括號－最早開工時(shí)間，三角－最晚開工時(shí)間02。作業(yè)時(shí)間參數(shù)：方括號－最早開工時(shí)間，三角－最313。總時(shí)差，自由時(shí)差：中括號－總時(shí)差，園括號－自由時(shí)差3。總時(shí)差，自由時(shí)差：中括號－總時(shí)差，園括號－自由時(shí)差32說明：1，由關(guān)鍵路線的意義知，這條線在時(shí)間上沒有回旋余地，即每個(gè)關(guān)鍵工作應(yīng)滿足“最早開工時(shí)間＝最遲必須開工時(shí)間”，而非關(guān)鍵路線則有富裕時(shí)間。所以，總時(shí)差為0的工作鏈就是關(guān)鍵路線。此處為2，比較總時(shí)差和自由時(shí)差的關(guān)系：工作（1，7）有自由時(shí)差13，若把它拖至13周開工，對它后面的工作的最早開工時(shí)間及時(shí)差等都沒有影響，對整個(gè)工期也沒有影響。而只有總時(shí)差沒有自由時(shí)差的工作則不然，若工作（7，8），總時(shí)差為1，自由時(shí)差為0，如果讓它推遲1周開工，雖然總工期不受影響，但其后面的工作最早時(shí)間及時(shí)差都要受影響。所以使用時(shí)差來調(diào)整工作時(shí)，應(yīng)盡量先用自由時(shí)差。說明：1，由關(guān)鍵路線的意義知，這條線在時(shí)間上沒有回旋余地，即33第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計(jì)劃的優(yōu)化路線時(shí)間最長的網(wǎng)絡(luò)路線為關(guān)鍵路線關(guān)鍵路線上的工序稱為關(guān)鍵工序不在關(guān)鍵路線上的工序?yàn)榉顷P(guān)鍵工序第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計(jì)劃的優(yōu)化路線時(shí)間最長的網(wǎng)絡(luò)路線為關(guān)34網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整

通過繪制網(wǎng)絡(luò)圖、計(jì)算時(shí)間參數(shù)、確定關(guān)鍵路線，得到的僅是一個(gè)初步計(jì)劃方案．為了得到從各方面都較好的方案，一般一項(xiàng)工程或任務(wù)的網(wǎng)絡(luò)計(jì)劃，往往要根據(jù)項(xiàng)目的要求綜合考慮時(shí)間、資源和費(fèi)用等目標(biāo)，對初始方案進(jìn)一步改善和調(diào)整，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的方案,求得最佳效果。但目前還沒有一個(gè)能全面反映這些指標(biāo)的模型，所以，一般只是按照某一個(gè)或兩個(gè)指標(biāo)來衡量計(jì)劃的優(yōu)劣。如：網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整通過繪制網(wǎng)絡(luò)圖、計(jì)算時(shí)間參數(shù)、確定354.工期不變的條件下，如何使所用資源最少（資源優(yōu)化）。1.縮短網(wǎng)絡(luò)計(jì)劃工期(時(shí)間優(yōu)化)；2.降低人力使用高峰，使其符合人力供應(yīng)能力，并使各工種人員中的使用連續(xù)均衡，且工期最短（時(shí)間—資源優(yōu)化）；3.縮短工期并使費(fèi)用增加最少（時(shí)間費(fèi)用優(yōu)化）

；4.工期不變的條件下，如何使所用資源最少1.縮短網(wǎng)絡(luò)計(jì)劃36

在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大于關(guān)鍵線路上工序時(shí)間總和時(shí)，關(guān)鍵線路上各工序的總時(shí)差就會出現(xiàn)正值，說明完成該項(xiàng)任務(wù)的時(shí)間較寬余，必要時(shí)可適當(dāng)延長某些工序的時(shí)間，以便減少資源或節(jié)省費(fèi)用。反之，任務(wù)比較急時(shí)，規(guī)定的工期會小于總工期，則需對網(wǎng)絡(luò)進(jìn)行調(diào)整。對超過規(guī)定工期的各條線路上的某些工序，通常在組織上和技術(shù)上可采用的方法有如下幾種：1.時(shí)間優(yōu)化--縮短網(wǎng)絡(luò)計(jì)劃工期在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大37(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時(shí)間。(b)

可能條件下采取平行交叉工序縮短工期。(c)

搞技術(shù)改造，或增加人力、物質(zhì)設(shè)備等多種措施，縮短某些工序的延續(xù)時(shí)間。(d)

利用時(shí)差，從非關(guān)鍵線路上抽調(diào)適當(dāng)?shù)娜肆Α⑽锪杏陉P(guān)鍵路線，以縮短關(guān)鍵路線的持續(xù)時(shí)間。

以上幾種縮短工期方法在使用過程中，會隨時(shí)引起網(wǎng)絡(luò)計(jì)劃的改變，每次改變后都要重新計(jì)算網(wǎng)絡(luò)時(shí)間和確定關(guān)鍵路線，直到求得最短周期為止。(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時(shí)間。38

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計(jì)劃時(shí)間為19周完成，現(xiàn)因特殊情況，上級要求提前3周完工，即總工期壓縮為16周，試對網(wǎng)絡(luò)進(jìn)行調(diào)整。

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計(jì)劃時(shí)間為1939解

（1）計(jì)算工序的時(shí)間參數(shù)，找出關(guān)鍵線路。如圖1，雙箭線的工序組成的線路為關(guān)鍵線路：①→②→③→⑤→⑨→⑩注：方括號內(nèi)：作業(yè)最早開始時(shí)間；三角內(nèi)：最遲開始時(shí)間解（1）計(jì)算工序的時(shí)間參數(shù)，找出關(guān)鍵線路。40

（2）縮短工期的計(jì)算：首先將終點(diǎn)事項(xiàng)⑩的最遲結(jié)束時(shí)間定為16周，從右向左逐個(gè)求出各工序的最遲開始時(shí)間tLS，標(biāo)在圖2相應(yīng)箭線下方的“△”內(nèi)，同時(shí)求出各工序總時(shí)差，用[]括起來放于相應(yīng)工序下方。（2）縮短工期的計(jì)算：首先將終點(diǎn)事項(xiàng)⑩的最遲結(jié)束時(shí)間定為141《運(yùn)籌學(xué)》8關(guān)鍵路線法解讀課件42

圖中方括號內(nèi)的數(shù)字為總工期16周時(shí)，各工序的總時(shí)差，從計(jì)劃的結(jié)果可看出，在原先的關(guān)鍵路線上各工序的總時(shí)差為（-3），這意味著原來的關(guān)鍵路線上應(yīng)縮短3周。而其他非關(guān)鍵線路上也出現(xiàn)負(fù)時(shí)差，即在這些線路上也要進(jìn)行日期的縮短。圖中方括號內(nèi)的數(shù)字為總工期16周時(shí)，各工序的總時(shí)差，43需要縮短日期的線路和工序有：線路

時(shí)差

（1）①→②→③→⑤→⑨→⑩-3（2）②→④→⑦→⑧→⑨-2（3）⑦→⑨ -1需要縮短日期的線路和工序有：線路44

首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短3周，不妨在②→③?③→⑤?⑨→⑩上各縮1周，縮短后，通過網(wǎng)絡(luò)時(shí)間參數(shù)的計(jì)算，其結(jié)果如圖所示。

53壓縮為26壓縮為53壓縮為2首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短45由上圖可知：絕對值最大的負(fù)時(shí)差線路為：①→②→④→⑦→⑧→⑨→⑩，現(xiàn)在其中任一工序上壓縮1周，比如⑧→⑨改為5周。由上圖可知：絕對值最大的負(fù)時(shí)差線路為：①→②→④→⑦→⑧→⑨46

再計(jì)算時(shí)間參數(shù)，可知負(fù)時(shí)差已全部消滅，如圖所示6壓縮為5這時(shí)總時(shí)差為0的線路有三條：①→②→③→⑤→⑨→⑩?①→②→④→⑦→⑨→⑩和①→②→④→⑦→⑧→⑨→⑩。它們均是關(guān)鍵線路，總工期為16周，符合規(guī)定的要求。再計(jì)算時(shí)間參數(shù)，可知負(fù)時(shí)差已全部消滅，如圖所示6壓縮為47網(wǎng)絡(luò)計(jì)劃的時(shí)間—資源優(yōu)化，是指對時(shí)間和其他資源進(jìn)行統(tǒng)籌安排，達(dá)到特定的工程要求．往往要求在有限的資源條件下合理分配資源，既滿足各項(xiàng)活動(dòng)對計(jì)劃的需求，又確保整個(gè)工程項(xiàng)目在盡可能短的時(shí)間內(nèi)完成．包括以下幾個(gè)方面：2.時(shí)間—資源優(yōu)化（主要優(yōu)化資源）1．先安排關(guān)鍵工程所需資源；2．錯(cuò)開非關(guān)鍵工序的開始時(shí)間，使工程各時(shí)段對資源的需求趨于平衡；3．為達(dá)到總體效益最佳，必要時(shí)可適當(dāng)延長總工期．網(wǎng)絡(luò)計(jì)劃的時(shí)間—資源優(yōu)化，是指對時(shí)間和其他資48

例

某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項(xiàng)疫情調(diào)查，整個(gè)工作可分許多階段(工序)，各階段所需的時(shí)間和人員數(shù)量不等，具體見表1，問各階段工作應(yīng)如何合理安排，才可以使人力的使用最合理?例某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項(xiàng)49表1各工序所需的時(shí)間和人員數(shù)量工序工期需人員數(shù)緊前工序a①→②27—b①→③24—c①→④25—d①→⑥410—e②→③28af③→⑤33b,eg④→⑤39ch⑤→⑥42f，gi⑥→⑦312d，h表1各工序所需的時(shí)間和人員數(shù)量工序工期需人員數(shù)緊前工序a①501764325abcdefghi442222333此時(shí)，關(guān)鍵路線為：aefhi,時(shí)間為14天。如果不做任何調(diào)整，按照正常的時(shí)間安排工作，則1－2天做a,b,c,d，需要26人；3－4天做d,e,g，需要27人；第5天做f,g，需要12人；6－7天做f，需要3人；8－11天做h，需要2人；12－14天做i需要12人，結(jié)果見下圖1764325abcdefghi442222333此時(shí)，關(guān)鍵511764325abcdefghi442222333人數(shù)74510839212abcdefghi1764325abcdefghi442222333人數(shù)74552考慮時(shí)差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)椋嚎紤]時(shí)差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)?3繼續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋豪^續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋?4繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：最少安排12人。繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：55工程所需時(shí)間與工程所需費(fèi)用是一對矛盾．一般情況下，縮短一道工序時(shí)間，就要采取一些措施，如加班，增加設(shè)備等，需要增加一定費(fèi)用，同時(shí)也會得到一些收益，如節(jié)約了管理費(fèi)用等．要想縮短整個(gè)工程的工期，必須從兩方面考慮：（1）要分析縮短工期所需代價(jià)；（2）要分析縮短工期帶來得收益．在一定條件下，滿足工程時(shí)間要求以期達(dá)到工程費(fèi)用的最低的網(wǎng)絡(luò)計(jì)劃安排稱為最低成本日程

3.時(shí)間—費(fèi)用優(yōu)化（主要是費(fèi)用優(yōu)化）工程所需時(shí)間與工程所需費(fèi)用是一對矛盾．56(1)費(fèi)用與時(shí)間的關(guān)系工程所需費(fèi)用，基本上分為兩大部分：

直接費(fèi)用——完成工序直接有關(guān)的費(fèi)用，如人力、機(jī)械、原材料等費(fèi)用．工序直接費(fèi)用和所需工時(shí)常假定為直線關(guān)系。

間接費(fèi)用——管理費(fèi)、設(shè)備租金等，是根據(jù)各道工序時(shí)間按比例分?jǐn)偟模ば驎r(shí)間越少，間接費(fèi)用就越少；反之，工序時(shí)間越多，間接費(fèi)用就越多．

工程總費(fèi)用W就是直接費(fèi)用U與間接費(fèi)用V的總和，即：W＝U＋V(1)費(fèi)用與時(shí)間的關(guān)系工程總費(fèi)用W就是直接費(fèi)用U57工程費(fèi)用與完工期之間的關(guān)系可用下圖表示．總費(fèi)用直接費(fèi)用正常時(shí)間間接費(fèi)用完工時(shí)間最優(yōu)時(shí)間最短時(shí)間費(fèi)用從圖中可看出，在正常工期和最短工期(縮短工期的最低限度，也簡稱趕工時(shí)間)之間，存在著一個(gè)最優(yōu)工期，此時(shí)總費(fèi)用最少．這個(gè)時(shí)間稱為最低成本日程．從關(guān)鍵路線入手，找出最少工程費(fèi)日程的方法，就是關(guān)鍵路線法(CPM)．工程費(fèi)用與完工期之間的關(guān)系可用下圖表示．總費(fèi)用直接費(fèi)用正常時(shí)58假設(shè)工序的直接費(fèi)用與工序時(shí)間是線性關(guān)系，設(shè)工序k每趕一天進(jìn)度所需要增加的費(fèi)用為q（k），則式中q（k）為費(fèi)用斜率,c為趕工所需費(fèi)用,n為正常完工所需費(fèi)用,nt為正常完工所需時(shí)間,ct為趕工時(shí)間．(2)時(shí)間—費(fèi)用優(yōu)化的計(jì)算顯然，費(fèi)用斜率越大的工序，每縮短一天，花的費(fèi)用就越多．在考慮縮短工程工期時(shí)，當(dāng)然是要縮短各關(guān)鍵工序中的某一道或某幾道工序的工期，而選擇縮短哪道工序要以總費(fèi)用最省為根據(jù)．假設(shè)工序的直接費(fèi)用與工序時(shí)間是線性關(guān)系，設(shè)工序k每趕一天59時(shí)間—費(fèi)用優(yōu)化的計(jì)算

首先應(yīng)確定工期與直接費(fèi)用的關(guān)系。即先對全部工序按正常時(shí)間計(jì)算參數(shù)，求出網(wǎng)絡(luò)圖的關(guān)鍵路線、工程周期和相應(yīng)的直接費(fèi)用。工程項(xiàng)目的總費(fèi)用=正常完工的直接費(fèi)用+趕工增加的費(fèi)用+間接費(fèi)用其次逐次壓縮費(fèi)用增長率q最小的關(guān)鍵工序延續(xù)時(shí)間，使直接費(fèi)用的增加最小。壓縮網(wǎng)絡(luò)時(shí)，按下面原則進(jìn)行：時(shí)間—費(fèi)用優(yōu)化的計(jì)算首先應(yīng)確定工期與直接費(fèi)用的關(guān)系。60(a)

壓縮關(guān)鍵線路上費(fèi)用增長率最小的工序時(shí)間，以增加最少的費(fèi)用來縮短工期。(b)

在選擇壓縮某項(xiàng)工序的延續(xù)時(shí)間時(shí)，既要滿足工序費(fèi)用一時(shí)間變化關(guān)系的限制，又要考慮網(wǎng)絡(luò)中和該作業(yè)并列的各工序時(shí)差數(shù)的限制，應(yīng)取這兩個(gè)限制的最小值。(c)

當(dāng)網(wǎng)絡(luò)圖不斷壓縮出現(xiàn)數(shù)條關(guān)鍵路線時(shí)，繼續(xù)壓縮工期，需要同時(shí)縮短這數(shù)條路線，僅縮短一條線路不會達(dá)到縮短工期的目的。(a)

壓縮關(guān)鍵線路上費(fèi)用增長率最小的工序時(shí)間，61

下面以例子說明通過縮短關(guān)鍵路線上工序時(shí)間來尋求最少工程費(fèi)日程的方法.

例某項(xiàng)工程根據(jù)有關(guān)資料，計(jì)算出了費(fèi)用斜率如表2，試制定該工程的最少工程費(fèi)計(jì)劃方案．下面以例子說明通過縮短關(guān)鍵路線上工序時(shí)間來尋求最62表2工程的有關(guān)資料及費(fèi)用斜率

工序緊前工序正常完工時(shí)間（天）正常完工直接費(fèi)用（百元）趕工時(shí)間（天）費(fèi)用斜率（百元）a/103074b/51042cb31522da,c42033ea,c52533fd63235ge5821hf,g5944合計(jì)

149

間接費(fèi)用5（百元/天）表2工程的有關(guān)資料及費(fèi)用斜率工序緊前正常完工正常完工直63圖1（a）

解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時(shí)間完工需25天，所需總費(fèi)用為:Ｗ＝14900+500×25＝27400元圖1（a）解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時(shí)64圖1（b）

若使工程工期最短，即將所有工序時(shí)間都壓縮到其可能的最短時(shí)間，看其費(fèi)用情況如何．這時(shí)，統(tǒng)籌圖如圖1（b）所示．

工程完工期為17天，其趕工增加費(fèi)用(c－n)為:3×400＋1×200＋1×200＋1×300＋2×300＋3×500＋3×100+1×400＝4700元.總費(fèi)用Ｗ＝14900+4700+500×17＝28100元.顯然費(fèi)用太大，不是最優(yōu)．

圖1（b）若使工程工期最短，即將所有工序時(shí)間都壓縮到其可能65分析按正常時(shí)間完工的計(jì)劃方案，找出最少工程費(fèi)方案．由圖2（a）可以看出，在按正常時(shí)間完工的統(tǒng)籌圖中，有兩條關(guān)鍵路線：①→③→④→⑥→⑦，①→③→⑤→⑥→⑦。

圖2（a）

分析按正常時(shí)間完工的計(jì)劃方案，找出最少工程費(fèi)方案．由圖66要縮短工期，就要縮短關(guān)鍵工序的時(shí)間.

首先考慮壓縮關(guān)鍵線路上費(fèi)用增長率最小的工序時(shí)間，以增加最少的費(fèi)用來縮短工期。在上述兩條關(guān)鍵路線的情況下，縮短哪道關(guān)鍵工序，分析如下：圖1（a）

要縮短工期，就要縮短關(guān)鍵工序的時(shí)間.

首先考慮壓縮關(guān)67兩條關(guān)鍵路線在結(jié)點(diǎn)3和結(jié)點(diǎn)6之間有并聯(lián)部分，關(guān)鍵工序?yàn)閍、d、e、f、g和h，其中工序a、h為兩條關(guān)鍵路線所共有．要縮短工期，在費(fèi)用最小的情況下，首先考慮縮短共有的關(guān)鍵工序．其次考慮結(jié)點(diǎn)3和結(jié)點(diǎn)6之間的各關(guān)鍵工序d、e、f和g，因?yàn)樗鼈冎g是并聯(lián)的，所以要想縮短工程的工期，必須在d、f中和e、g中，各壓縮一道工序的時(shí)間．這樣，它們就有4種可能的組合。綜合以上組合及費(fèi)用情況可通過下表考慮選擇：兩條關(guān)鍵路線在結(jié)點(diǎn)3和結(jié)點(diǎn)6之間有并聯(lián)部分，關(guān)鍵工序68從上表比較可知，費(fèi)用增長率最小的工序或工序組合為a、h、d和g，這三者中首先考慮縮短兩條關(guān)鍵路線所共有的關(guān)鍵工序a、h．不妨先縮短關(guān)鍵工序h，每縮短1天，需增加費(fèi)用400元，但節(jié)省間接費(fèi)500元，凈省費(fèi)用100元．因此，把工序h壓縮到最低限度4天．同時(shí)，總費(fèi)用減為27300元．

表3幾種可能縮短的工序或工序組合工序趕工一天增加的費(fèi)用趕工一天間接費(fèi)用減少總費(fèi)用凈變化a45-1h45-1d和e3+3=65+1d和g3+1=45-1f和e5+3=85+3f和g5+1=65+1從上表比較可知，費(fèi)用增長率最小的工序或工序組合為a、h69然后再考慮壓縮工序a，與壓縮工序h一樣，每壓縮1天，總費(fèi)用凈省100元．但此處需注意，工序a不能壓縮到其最低時(shí)間限度7天，因?yàn)楫?dāng)工序壓縮2天時(shí)，工序時(shí)間為8天，這時(shí)工序b和工序c就都變成了關(guān)鍵工序．這樣，在結(jié)點(diǎn)1和結(jié)點(diǎn)3之間，也出現(xiàn)了并聯(lián)的關(guān)鍵路線部分．繼續(xù)單獨(dú)壓縮工序a，已不能縮短整個(gè)工程的工期．因此，只能把工序a壓縮為8天．總費(fèi)用減為27100元．

最后，將工序d和工序g各壓縮1天，總費(fèi)用減為27000元.由于工序d的限制，不能進(jìn)一步壓縮了．

然后再考慮壓縮工序a，與壓縮工序h一樣，每壓縮1天，70綜合起來，最少工程費(fèi)計(jì)劃方案，按下列要求去做：將工序a壓縮為8天，將工序d壓縮為3天，將工序g壓縮為4天，將工序h壓縮為4天，其它工序b、c、e和f仍按正常時(shí)間進(jìn)行，這樣得到的最少工程費(fèi)日程為21天，總費(fèi)用為27000元，其統(tǒng)籌圖如圖1（c）所示．

圖1（c）

#綜合起來，最少工程費(fèi)計(jì)劃方案，按下列要求去做：將工71第三節(jié)概率型網(wǎng)絡(luò)、完成作業(yè)的期望時(shí)間、在規(guī)定時(shí)間內(nèi)實(shí)現(xiàn)事件的概率第三節(jié)概率型網(wǎng)絡(luò)、完成作業(yè)的期望時(shí)間、在規(guī)定時(shí)間內(nèi)實(shí)72對于概率型網(wǎng)絡(luò)，在實(shí)際計(jì)算中，完成一項(xiàng)作業(yè)的期望時(shí)間Et(i,j)按如下公式計(jì)算：其中：a是最樂觀的時(shí)間估計(jì)值，m是最可能的估計(jì)值，b是最悲觀的時(shí)間估計(jì)值對于概率型網(wǎng)絡(luò)，在實(shí)際計(jì)算中，完成一項(xiàng)作業(yè)的期望時(shí)間Et(i73我們知道，當(dāng)上述的時(shí)間參數(shù)求出后，概率型網(wǎng)絡(luò)就可用同確定型網(wǎng)絡(luò)一樣的方法可計(jì)算出其它相應(yīng)的所有參數(shù)。但由于他們的工作工時(shí)本身包含隨機(jī)因素，所以，整個(gè)任務(wù)的總完工期也是個(gè)期望工期。它是關(guān)鍵路線上各道工作的平均工時(shí)之和，所以總完工工期的方差就是關(guān)鍵路線上所有工序的方差之和。若工作足夠多，每一件工作的工時(shí)對整個(gè)任務(wù)的完成工時(shí)影響不是很明顯的話，由中心極限定理，總完工期服從上述均值和方差為參數(shù)的正態(tài)分布。我們知道，當(dāng)上述的時(shí)間參數(shù)求出后，概率型網(wǎng)絡(luò)就可用同確定型網(wǎng)74為達(dá)到嚴(yán)格控制工期，確保任務(wù)在計(jì)劃期內(nèi)完成的目的，我們可以計(jì)算在給定的工期前完工的概率。實(shí)際問題中，可以通過計(jì)算多個(gè)不同的完工期內(nèi)能完成的概率，最終找到一個(gè)符合概率要求的完工期，將它作為項(xiàng)目總工期。為達(dá)到嚴(yán)格控制工期，確保任務(wù)在計(jì)劃期內(nèi)完成的目的，我們可以計(jì)75例：一項(xiàng)工程項(xiàng)目由9個(gè)作業(yè)組成，各作業(yè)間的邏輯關(guān)系以及工期信息見表。 (1)繪制相應(yīng)的網(wǎng)絡(luò)。 (2)用表格計(jì)算法找出關(guān)鍵線路，并預(yù)測該項(xiàng)目的總工期。

例：一項(xiàng)工程項(xiàng)目由9個(gè)作業(yè)組成，各作業(yè)間的邏輯關(guān)系以及工期信76《運(yùn)籌學(xué)》8關(guān)鍵路線法解讀課件77解：（1）繪制相應(yīng)的網(wǎng)絡(luò)圖見圖1234567A4B6C3D5H6E6F2G6I5(4+5*4+6)/6(2+4*4+6)/6(5+6*4+7)/6(4+6*4+8)/6計(jì)算出工期的均值，如下表中的工期ET解：（1）繪制相應(yīng)的網(wǎng)絡(luò)圖見圖1234567AB6C78作業(yè)名稱ABCDEFGHI樂觀工期252341354最可能工期463562665悲觀工期674783976工期ET463562665工期方差0.440.110.110.440.440.110.250.110.11關(guān)鍵作業(yè)

作業(yè)ABCDEFGHI樂觀252341354最可463562791234567A4B6C3D5H6E6F2G6I50471312241907418241913計(jì)算時(shí)間，得下圖。找出關(guān)鍵線路，預(yù)測該項(xiàng)目的總工期為24周。也可以用后面的表表示。1234567AB6C3DHEFGI5047180作業(yè)名稱ABCDEFGHI樂觀工期252341354最可能工期463562665悲觀工期674783976工期ET463562665工期方差0.440.110.110.440.440.110.250.110.11關(guān)鍵作業(yè)#

#

#

#

#作業(yè)ABCDEFGHI樂觀252341354最可46356281如果該項(xiàng)目的計(jì)劃工期為26周，則按期完工的可能性有多大？如果該項(xiàng)目的計(jì)劃工期為26周，則按期完工82為計(jì)算方便，我們假定每個(gè)事件的最早實(shí)現(xiàn)時(shí)間服從正態(tài)分布（此假定對最終事件的完成時(shí)間是基本正確的），即事件3的正態(tài)分布的中心為方差為計(jì)算方便，我們假定每個(gè)事件的最早實(shí)現(xiàn)時(shí)間服從正態(tài)分布（此假83假定事件k的最早實(shí)現(xiàn)時(shí)間的期望和方差已知，則事件k的實(shí)現(xiàn)時(shí)間Tk小于規(guī)定期限Tdk的概率為假定事件k的最早實(shí)現(xiàn)時(shí)間的期望和方差已知，則事件k的實(shí)現(xiàn)時(shí)間84《運(yùn)籌學(xué)》8關(guān)鍵路線法解讀課件85

第八章計(jì)劃評審方法和關(guān)鍵路線方法第八章86網(wǎng)絡(luò)計(jì)劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計(jì)劃方法是項(xiàng)目計(jì)劃管理的重要方法。它起源于美國。當(dāng)時(shí)，有兩種網(wǎng)絡(luò)計(jì)劃方法：關(guān)鍵路線法和計(jì)劃評審技術(shù)。1957年，美國杜邦化學(xué)公司用關(guān)鍵路線法(CriticalPathMethod)。當(dāng)年就節(jié)約100萬美元，為該公司用于該項(xiàng)目研究費(fèi)用的5倍以上。1958年，美國海軍當(dāng)局在研制北極星導(dǎo)彈潛艇時(shí)，第一次采用了BuzzAllen提出的計(jì)劃評審技術(shù)(ProgramEvaluationandReviewTechnique),主要承包商200多家，轉(zhuǎn)包商10000家。23個(gè)系統(tǒng)網(wǎng)絡(luò)，每兩周檢查一次，原定6年，提前兩年完成，節(jié)約經(jīng)費(fèi)10—15％。60年代耗時(shí)11年阿波羅登月計(jì)劃3000億$,42萬人,2萬家公司,120所大學(xué),600臺計(jì)算機(jī),700萬零件,終于在1969年7月，阿波羅11號船長阿姆斯特朗登上月球。網(wǎng)絡(luò)計(jì)劃方法的產(chǎn)生起源：網(wǎng)絡(luò)計(jì)劃方法是項(xiàng)目計(jì)劃管理的重要方法8760-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做了大量工作。華羅庚的例子：有客來訪，要請他飲茶，于是要做幾件事：洗茶杯、洗杯蓋、燒開水、泡茶到端茶。60-70年代我國開始應(yīng)用和推廣。錢學(xué)森、華羅庚等都曾為此做88客來沏茶本問題的幾道“工序”有次序,洗杯蓋端茶燒水泡茶洗杯虛時(shí)間:251020.5客來沏茶本問題的幾道“工序”有次序,洗杯蓋89第一節(jié)PERT網(wǎng)絡(luò)圖第一節(jié)PERT網(wǎng)絡(luò)圖90網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(diǎn)(事件)、箭線（作業(yè)）和路線。132一、網(wǎng)絡(luò)圖構(gòu)成網(wǎng)絡(luò)圖由三大要素構(gòu)成：節(jié)點(diǎn)(事件)、箭線（作業(yè)）和路線。1391箭線:

1、代表計(jì)劃中的一項(xiàng)作業(yè)或工序，包括人力、財(cái)力、物力的付出。2、作業(yè)的內(nèi)容可大可小，可多可少。3、箭尾表示作業(yè)開始，箭頭表示作業(yè)結(jié)束4、通常把作業(yè)的代號和作業(yè)所耗時(shí)間標(biāo)在箭線的上下。5、虛箭線：不占用時(shí)間和空間，不消耗任何資源。只是為了明確活動(dòng)的相互之間的邏輯關(guān)系。

3445A

10AijA：作業(yè)活動(dòng)代號3445AAijA：作業(yè)活動(dòng)代號92結(jié)點(diǎn)（表示事件）：

網(wǎng)絡(luò)圖中兩條或兩條以上的箭線的交接點(diǎn)就是結(jié)點(diǎn)，結(jié)點(diǎn)代表的作業(yè)開始和結(jié)束。用圓圈加上數(shù)字表示。

路線：從網(wǎng)絡(luò)圖的始點(diǎn)事件開始到終點(diǎn)事件為止，由一系列首尾相連的箭線和結(jié)點(diǎn)所代表的作業(yè)和事件所組成的通道。網(wǎng)絡(luò)圖一般有多條路線。其中最長的我們稱之為關(guān)鍵路線，關(guān)鍵路線上的工序?yàn)殛P(guān)鍵工序。結(jié)點(diǎn)（表示事件）：93（錯(cuò)誤）135624正確135624PERT圖的開始節(jié)點(diǎn)與結(jié)束節(jié)點(diǎn)均應(yīng)是唯一的。二、繪制PERT圖的原則如果在實(shí)際工作中發(fā)生不吻合時(shí)，應(yīng)將沒有緊前作業(yè)的結(jié)點(diǎn)用虛箭頭線同網(wǎng)絡(luò)始點(diǎn)事項(xiàng)連接起來，將沒有后續(xù)事項(xiàng)的結(jié)點(diǎn)用虛箭頭同終點(diǎn)事項(xiàng)邊接起來。（錯(cuò)誤）135624正確135624PERT圖的開始節(jié)點(diǎn)與結(jié)94錯(cuò)誤正確在相鄰的兩個(gè)節(jié)點(diǎn)之間，最多只能有一條箭線相連。進(jìn)入某一個(gè)結(jié)點(diǎn)的箭線可以有多條，但其它任何結(jié)點(diǎn)直接連接該結(jié)點(diǎn)的箭線只能有一條。兩個(gè)相鄰結(jié)點(diǎn)間只允許有一條箭線直接相連。若有平行活動(dòng)，可引入虛線以保證這一規(guī)則不被破壞。錯(cuò)誤正確在相鄰的兩個(gè)節(jié)點(diǎn)之間，最多只能有一條箭線相連。進(jìn)入某95錯(cuò)誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路錯(cuò)誤網(wǎng)絡(luò)圖中不能出現(xiàn)循環(huán)回路96

節(jié)點(diǎn)編號時(shí)，按照矢線箭頭的指向，升序排號，保證節(jié)點(diǎn)序號先后關(guān)系保持一致。應(yīng)將各作業(yè)的工時(shí)數(shù)據(jù)標(biāo)注在表示該作業(yè)的矢線的下面。

正確使用虛工序（不消耗資源，一般表示平行工作關(guān)系）節(jié)點(diǎn)編號時(shí)，按照矢線箭頭的指向，升序排號，保證節(jié)點(diǎn)序號先后97三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如下：@根據(jù)活動(dòng)清單中規(guī)定的關(guān)系，將活動(dòng)代號欄所有的活動(dòng)逐次地畫在網(wǎng)絡(luò)圖上，從左到右@理順活動(dòng)的緊前、緊后關(guān)系，沒有緊后活動(dòng)的活動(dòng)所對應(yīng)的箭線匯集在終止結(jié)點(diǎn)上@草圖繪制完成后，將序號標(biāo)在結(jié)點(diǎn)上，將活動(dòng)代號和時(shí)間標(biāo)在箭線上@檢查無誤后，將草圖繪制成規(guī)范圖

三、PERT圖的繪制步驟先畫草圖，再修改后變成規(guī)范圖，步驟如98作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，H作業(yè)時(shí)間D15151410661308例：某項(xiàng)工程任務(wù)經(jīng)分解后，確定由9項(xiàng)作業(yè)構(gòu)成，各項(xiàng)作業(yè)的代號、緊前作業(yè)及作業(yè)時(shí)間如表所示，畫出網(wǎng)絡(luò)圖作業(yè)名稱ABCDEFGHI緊前作業(yè)AAB，CBDDE，GF，991412346578A15B15CE6D10G1H30F6I81412346578A15B15CE6D10G1H30F6I100序號施工項(xiàng)目所需時(shí)間（月）工序代號緊前項(xiàng)目12345678清理地面打地基砌墻安裝電線粉刷畫圖案室內(nèi)工程上屋頂14434645ABCDEF

G

HA

BDD，HCEC例：建筑一幢房屋，施工順序如上表所示，要求計(jì)算工程周期及關(guān)鍵路線序號施工項(xiàng)目所需時(shí)間（月）工序代號緊前項(xiàng)目1清理地面1A例：101E51 2346785ABCDG144H344E51 2346785ABCDG144H34102活動(dòng)代號活動(dòng)描述緊后活動(dòng)活動(dòng)時(shí)間（周）ABCDEFGHIJKL系統(tǒng)分析和總體設(shè)計(jì)輸入和輸出設(shè)計(jì)模塊1詳細(xì)設(shè)計(jì)輸入和輸出程序設(shè)計(jì)模塊1程序設(shè)計(jì)模塊2詳細(xì)設(shè)計(jì)輸入和輸出及模塊1測試模塊2程序設(shè)計(jì)模塊1測試系統(tǒng)總調(diào)試穩(wěn)當(dāng)編寫系統(tǒng)測試B,CDE,FG,IG,IHJI,KJL無無346885363583某機(jī)械廠管理信息系統(tǒng)開發(fā)活動(dòng)清單例活動(dòng)代號活動(dòng)描述緊后活動(dòng)活動(dòng)時(shí)間（周）A系統(tǒng)分析和總體設(shè)計(jì)B10312346109857A3B4

C6D8E8F5H6G3J5L3K8I312346109857AB4CDEFHGJLKI3104四、PERT圖的分類（1）按工時(shí)估計(jì)的性質(zhì)：A：確定型網(wǎng)絡(luò)，每個(gè)工作的預(yù)計(jì)工時(shí)只估一個(gè)值，即，這些工作的實(shí)際完成情況一般地可按預(yù)計(jì)工時(shí)達(dá)到，也即實(shí)現(xiàn)的概率等于或近似等于1。B：概率型網(wǎng)絡(luò)，每個(gè)工作按三種情況下給定工時(shí)，最快可能完成工時(shí)，最可能完成工時(shí)，最慢可能完成工時(shí)。四、PERT圖的分類（1）按工時(shí)估計(jì)的性質(zhì)：105五、PERT圖的計(jì)算1.工作時(shí)間tij的確定:確定型:利用已知的工時(shí)定額資料給出。概率型：對于開發(fā)性任務(wù)，或?qū)ぷ魉璧墓r(shí)難以準(zhǔn)確估計(jì)時(shí)，可采用三點(diǎn)時(shí)間法來確定工作的工時(shí)。

五、PERT圖的計(jì)算1.工作時(shí)間tij的確定:106則實(shí)際計(jì)算中，完成一項(xiàng)作業(yè)的期望工時(shí)t(i,j)按如下公式計(jì)算：設(shè)：a是最樂觀的時(shí)間估計(jì)值，m是最可能的估計(jì)值，b是最悲觀的時(shí)間估計(jì)值方差為：則實(shí)際計(jì)算中，完成一項(xiàng)作業(yè)的期望工時(shí)t(i,j)按如下公式計(jì)1072.結(jié)點(diǎn)（事項(xiàng)）的時(shí)間參數(shù)確定：（1）節(jié)點(diǎn)的最早時(shí)間：它表明以它為始點(diǎn)的各工作最早可能開始的時(shí)間，也表明以它為終點(diǎn)的各工作的最早可能完成時(shí)間。等于從始點(diǎn)結(jié)點(diǎn)到該結(jié)點(diǎn)的最長路線上所有工作的工時(shí)總和。遞推公式：：整個(gè)工程的總最早完工期2.結(jié)點(diǎn)（事項(xiàng)）的時(shí)間參數(shù)確定：（1）節(jié)點(diǎn)的最早時(shí)間：它表108（2）節(jié)點(diǎn)的最遲時(shí)間：它表明在不影響任務(wù)總工期的條件下，以它為始點(diǎn)的各工作最遲必須開始的時(shí)間，也表明以它為終點(diǎn)的各工作的最遲必須完成時(shí)間。由于，一般都把任務(wù)的最早完工時(shí)間作為任務(wù)的總工期，所以結(jié)點(diǎn)的最遲時(shí)間遞推公式為：（2）節(jié)點(diǎn)的最遲時(shí)間：它表明在不影響任務(wù)總工期的條件下，以它1093.工作的時(shí)間參數(shù)確定：1。作業(yè)的最早可能開始時(shí)間（ES）是指作業(yè)最早可能開始的時(shí)間，是它的各項(xiàng)緊前作業(yè)最早結(jié)束的時(shí)間中最大的一個(gè)。2。作業(yè)的最早可能結(jié)束時(shí)間（EF）

是指作業(yè)按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間。3.工作的時(shí)間參數(shù)確定：1。作業(yè)的最早可能開始時(shí)間（ES）1103.作業(yè)的最遲必須開工時(shí)間（LS）是指作業(yè)（i,j）在不影響整個(gè)任務(wù)如期完工的前提下，必須開始的最晚時(shí)間。

4.作業(yè)的最遲必須結(jié)束時(shí)間（LF）

是指作業(yè)（i,j）按最遲時(shí)間開工，所能達(dá)到的完工時(shí)間。3.作業(yè)的最遲必須開工時(shí)間（LS）1114.時(shí)差：按性質(zhì)可以分為作業(yè)的總時(shí)差R（i,j）和作業(yè)的自由時(shí)差F（i,j）?？倳r(shí)差：在不影響任務(wù)總工期的條件下，某工作（i,j）可以延遲其開工時(shí)間的最大幅度。這是網(wǎng)絡(luò)上多于一項(xiàng)作業(yè)共同擁有的機(jī)動(dòng)時(shí)間，并非為某項(xiàng)作業(yè)單獨(dú)擁有。工作（i,j）的總時(shí)差等于它的最遲完工時(shí)間與最早完工時(shí)間的差，也等于它的最遲開工時(shí)間與最早開工時(shí)間的差。4.時(shí)差：總時(shí)差：在不影響任務(wù)總工期的條件下，某工作（i,112自由時(shí)差：不影響它的各項(xiàng)緊后作業(yè)最早開工時(shí)間條件下，該項(xiàng)作業(yè)可以推遲的開工時(shí)間的最大限度，它是一項(xiàng)作業(yè)獨(dú)自擁有的機(jī)動(dòng)時(shí)間。即自由時(shí)差等于其緊后作業(yè)的最早開工時(shí)間與本工作的最早完工時(shí)間的差。自由時(shí)差：不影響它的各項(xiàng)緊后作業(yè)最早開工時(shí)間條件下，該項(xiàng)作業(yè)113下圖是一個(gè)工程施工圖，請依次求出各時(shí)間參數(shù)。

時(shí)間參數(shù)計(jì)算舉例下圖是一個(gè)工程施工圖，請依次求出各時(shí)間參數(shù)。1141。結(jié)點(diǎn)時(shí)間參數(shù)：方括號－最早時(shí)間，三角－最晚時(shí)間1。結(jié)點(diǎn)時(shí)間參數(shù)：方括號－最早時(shí)間，三角－最晚時(shí)間1152。作業(yè)時(shí)間參數(shù)：方括號－最早開工時(shí)間，三角－最晚開工時(shí)間02。作業(yè)時(shí)間參數(shù)：方括號－最早開工時(shí)間，三角－最1163?？倳r(shí)差，自由時(shí)差：中括號－總時(shí)差，園括號－自由時(shí)差3?？倳r(shí)差，自由時(shí)差：中括號－總時(shí)差，園括號－自由時(shí)差117說明：1，由關(guān)鍵路線的意義知，這條線在時(shí)間上沒有回旋余地，即每個(gè)關(guān)鍵工作應(yīng)滿足“最早開工時(shí)間＝最遲必須開工時(shí)間”，而非關(guān)鍵路線則有富裕時(shí)間。所以，總時(shí)差為0的工作鏈就是關(guān)鍵路線。此處為2，比較總時(shí)差和自由時(shí)差的關(guān)系：工作（1，7）有自由時(shí)差13，若把它拖至13周開工，對它后面的工作的最早開工時(shí)間及時(shí)差等都沒有影響，對整個(gè)工期也沒有影響。而只有總時(shí)差沒有自由時(shí)差的工作則不然，若工作（7，8），總時(shí)差為1，自由時(shí)差為0，如果讓它推遲1周開工，雖然總工期不受影響，但其后面的工作最早時(shí)間及時(shí)差都要受影響。所以使用時(shí)差來調(diào)整工作時(shí)，應(yīng)盡量先用自由時(shí)差。說明：1，由關(guān)鍵路線的意義知，這條線在時(shí)間上沒有回旋余地，即118第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計(jì)劃的優(yōu)化路線時(shí)間最長的網(wǎng)絡(luò)路線為關(guān)鍵路線關(guān)鍵路線上的工序稱為關(guān)鍵工序不在關(guān)鍵路線上的工序?yàn)榉顷P(guān)鍵工序第二節(jié)關(guān)鍵路線與網(wǎng)絡(luò)計(jì)劃的優(yōu)化路線時(shí)間最長的網(wǎng)絡(luò)路線為關(guān)119網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整

通過繪制網(wǎng)絡(luò)圖、計(jì)算時(shí)間參數(shù)、確定關(guān)鍵路線，得到的僅是一個(gè)初步計(jì)劃方案．為了得到從各方面都較好的方案，一般一項(xiàng)工程或任務(wù)的網(wǎng)絡(luò)計(jì)劃，往往要根據(jù)項(xiàng)目的要求綜合考慮時(shí)間、資源和費(fèi)用等目標(biāo)，對初始方案進(jìn)一步改善和調(diào)整，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的方案,求得最佳效果。但目前還沒有一個(gè)能全面反映這些指標(biāo)的模型，所以，一般只是按照某一個(gè)或兩個(gè)指標(biāo)來衡量計(jì)劃的優(yōu)劣。如：網(wǎng)絡(luò)圖的優(yōu)化與調(diào)整通過繪制網(wǎng)絡(luò)圖、計(jì)算時(shí)間參數(shù)、確定1204.工期不變的條件下，如何使所用資源最少（資源優(yōu)化）。1.縮短網(wǎng)絡(luò)計(jì)劃工期(時(shí)間優(yōu)化)；2.降低人力使用高峰，使其符合人力供應(yīng)能力，并使各工種人員中的使用連續(xù)均衡，且工期最短（時(shí)間—資源優(yōu)化）；3.縮短工期并使費(fèi)用增加最少（時(shí)間費(fèi)用優(yōu)化）

；4.工期不變的條件下，如何使所用資源最少1.縮短網(wǎng)絡(luò)計(jì)劃121

在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大于關(guān)鍵線路上工序時(shí)間總和時(shí)，關(guān)鍵線路上各工序的總時(shí)差就會出現(xiàn)正值，說明完成該項(xiàng)任務(wù)的時(shí)間較寬余，必要時(shí)可適當(dāng)延長某些工序的時(shí)間，以便減少資源或節(jié)省費(fèi)用。反之，任務(wù)比較急時(shí)，規(guī)定的工期會小于總工期，則需對網(wǎng)絡(luò)進(jìn)行調(diào)整。對超過規(guī)定工期的各條線路上的某些工序，通常在組織上和技術(shù)上可采用的方法有如下幾種：1.時(shí)間優(yōu)化--縮短網(wǎng)絡(luò)計(jì)劃工期在網(wǎng)絡(luò)系統(tǒng)中，關(guān)鍵線路決定總工期。當(dāng)規(guī)定的工期大122(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時(shí)間。(b)

可能條件下采取平行交叉工序縮短工期。(c)

搞技術(shù)改造，或增加人力、物質(zhì)設(shè)備等多種措施，縮短某些工序的延續(xù)時(shí)間。(d)

利用時(shí)差，從非關(guān)鍵線路上抽調(diào)適當(dāng)?shù)娜肆?、物力集中于關(guān)鍵路線，以縮短關(guān)鍵路線的持續(xù)時(shí)間。

以上幾種縮短工期方法在使用過程中，會隨時(shí)引起網(wǎng)絡(luò)計(jì)劃的改變，每次改變后都要重新計(jì)算網(wǎng)絡(luò)時(shí)間和確定關(guān)鍵路線，直到求得最短周期為止。(a)

在關(guān)鍵線路上尋找最有利的工序來縮短其作業(yè)時(shí)間。123

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計(jì)劃時(shí)間為19周完成，現(xiàn)因特殊情況，上級要求提前3周完工，即總工期壓縮為16周，試對網(wǎng)絡(luò)進(jìn)行調(diào)整。

例圖1是某工程的網(wǎng)絡(luò)圖，初始方案計(jì)劃時(shí)間為19124解

（1）計(jì)算工序的時(shí)間參數(shù)，找出關(guān)鍵線路。如圖1，雙箭線的工序組成的線路為關(guān)鍵線路：①→②→③→⑤→⑨→⑩注：方括號內(nèi)：作業(yè)最早開始時(shí)間；三角內(nèi)：最遲開始時(shí)間解（1）計(jì)算工序的時(shí)間參數(shù)，找出關(guān)鍵線路。125

（2）縮短工期的計(jì)算：首先將終點(diǎn)事項(xiàng)⑩的最遲結(jié)束時(shí)間定為16周，從右向左逐個(gè)求出各工序的最遲開始時(shí)間tLS，標(biāo)在圖2相應(yīng)箭線下方的“△”內(nèi)，同時(shí)求出各工序總時(shí)差，用[]括起來放于相應(yīng)工序下方。（2）縮短工期的計(jì)算：首先將終點(diǎn)事項(xiàng)⑩的最遲結(jié)束時(shí)間定為1126《運(yùn)籌學(xué)》8關(guān)鍵路線法解讀課件127

圖中方括號內(nèi)的數(shù)字為總工期16周時(shí)，各工序的總時(shí)差，從計(jì)劃的結(jié)果可看出，在原先的關(guān)鍵路線上各工序的總時(shí)差為（-3），這意味著原來的關(guān)鍵路線上應(yīng)縮短3周。而其他非關(guān)鍵線路上也出現(xiàn)負(fù)時(shí)差，即在這些線路上也要進(jìn)行日期的縮短。圖中方括號內(nèi)的數(shù)字為總工期16周時(shí)，各工序的總時(shí)差，128需要縮短日期的線路和工序有：線路

時(shí)差

（1）①→②→③→⑤→⑨→⑩-3（2）②→④→⑦→⑧→⑨-2（3）⑦→⑨ -1需要縮短日期的線路和工序有：線路129

首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短3周，不妨在②→③?③→⑤?⑨→⑩上各縮1周，縮短后，通過網(wǎng)絡(luò)時(shí)間參數(shù)的計(jì)算，其結(jié)果如圖所示。

53壓縮為26壓縮為53壓縮為2首先考慮關(guān)鍵線路即線路①→②→③→⑤→⑨→⑩上縮短130由上圖可知：絕對值最大的負(fù)時(shí)差線路為：①→②→④→⑦→⑧→⑨→⑩，現(xiàn)在其中任一工序上壓縮1周，比如⑧→⑨改為5周。由上圖可知：絕對值最大的負(fù)時(shí)差線路為：①→②→④→⑦→⑧→⑨131

再計(jì)算時(shí)間參數(shù)，可知負(fù)時(shí)差已全部消滅，如圖所示6壓縮為5這時(shí)總時(shí)差為0的線路有三條：①→②→③→⑤→⑨→⑩?①→②→④→⑦→⑨→⑩和①→②→④→⑦→⑧→⑨→⑩。它們均是關(guān)鍵線路，總工期為16周，符合規(guī)定的要求。再計(jì)算時(shí)間參數(shù)，可知負(fù)時(shí)差已全部消滅，如圖所示6壓縮為132網(wǎng)絡(luò)計(jì)劃的時(shí)間—資源優(yōu)化，是指對時(shí)間和其他資源進(jìn)行統(tǒng)籌安排，達(dá)到特定的工程要求．往往要求在有限的資源條件下合理分配資源，既滿足各項(xiàng)活動(dòng)對計(jì)劃的需求，又確保整個(gè)工程項(xiàng)目在盡可能短的時(shí)間內(nèi)完成．包括以下幾個(gè)方面：2.時(shí)間—資源優(yōu)化（主要優(yōu)化資源）1．先安排關(guān)鍵工程所需資源；2．錯(cuò)開非關(guān)鍵工序的開始時(shí)間，使工程各時(shí)段對資源的需求趨于平衡；3．為達(dá)到總體效益最佳，必要時(shí)可適當(dāng)延長總工期．網(wǎng)絡(luò)計(jì)劃的時(shí)間—資源優(yōu)化，是指對時(shí)間和其他資133

例

某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項(xiàng)疫情調(diào)查，整個(gè)工作可分許多階段(工序)，各階段所需的時(shí)間和人員數(shù)量不等，具體見表1，問各階段工作應(yīng)如何合理安排，才可以使人力的使用最合理?例某市防疫站從下屬單位抽調(diào)部分人員，進(jìn)行一項(xiàng)134表1各工序所需的時(shí)間和人員數(shù)量工序工期需人員數(shù)緊前工序a①→②27—b①→③24—c①→④25—d①→⑥410—e②→③28af③→⑤33b,eg④→⑤39ch⑤→⑥42f，gi⑥→⑦312d，h表1各工序所需的時(shí)間和人員數(shù)量工序工期需人員數(shù)緊前工序a①1351764325abcdefghi442222333此時(shí)，關(guān)鍵路線為：aefhi,時(shí)間為14天。如果不做任何調(diào)整，按照正常的時(shí)間安排工作，則1－2天做a,b,c,d，需要26人；3－4天做d,e,g，需要27人；第5天做f,g，需要12人；6－7天做f，需要3人；8－11天做h，需要2人；12－14天做i需要12人，結(jié)果見下圖1764325abcdefghi442222333此時(shí)，關(guān)鍵1361764325abcdefghi442222333人數(shù)74510839212abcdefghi1764325abcdefghi442222333人數(shù)745137考慮時(shí)差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)椋嚎紤]時(shí)差，可調(diào)整d的工作，讓它延遲到第8天開工，人數(shù)安排變?yōu)?38繼續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋豪^續(xù)調(diào)整g的工作，讓它延遲到第5天開工，人數(shù)安排變?yōu)椋?39繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：最少安排12人。繼續(xù)調(diào)整b的工作，讓它延遲到第3天開工，人數(shù)安排變?yōu)椋航Y(jié)論：140工程所需時(shí)間與工程所需費(fèi)用是一對矛盾．一般情況下，縮短一道工序時(shí)間，就要采取一些措施，如加班，增加設(shè)備等，需要增加一定費(fèi)用，同時(shí)也會得到一些收益，如節(jié)約了管理費(fèi)用等．要想縮短整個(gè)工程的工期，必須從兩方面考慮：（1）要分析縮短工期所需代價(jià)；（2）要分析縮短工期帶來得收益．在一定條件下，滿足工程時(shí)間要求以期達(dá)到工程費(fèi)用的最低的網(wǎng)絡(luò)計(jì)劃安排稱為最低成本日程

3.時(shí)間—費(fèi)用優(yōu)化（主要是費(fèi)用優(yōu)化）工程所需時(shí)間與工程所需費(fèi)用是一對矛盾．141(1)費(fèi)用與時(shí)間的關(guān)系工程所需費(fèi)用，基本上分為兩大部分：

直接費(fèi)用——完成工序直接有關(guān)的費(fèi)用，如人力、機(jī)械、原材料等費(fèi)用．工序直接費(fèi)用和所需工時(shí)常假定為直線關(guān)系。

間接費(fèi)用——管理費(fèi)、設(shè)備租金等，是根據(jù)各道工序時(shí)間按比例分?jǐn)偟模ば驎r(shí)間越少，間接費(fèi)用就越少；反之，工序時(shí)間越多，間接費(fèi)用就越多．

工程總費(fèi)用W就是直接費(fèi)用U與間接費(fèi)用V的總和，即：W＝U＋V(1)費(fèi)用與時(shí)間的關(guān)系工程總費(fèi)用W就是直接費(fèi)用U142工程費(fèi)用與完工期之間的關(guān)系可用下圖表示．總費(fèi)用直接費(fèi)用正常時(shí)間間接費(fèi)用完工時(shí)間最優(yōu)時(shí)間最短時(shí)間費(fèi)用從圖中可看出，在正常工期和最短工期(縮短工期的最低限度，也簡稱趕工時(shí)間)之間，存在著一個(gè)最優(yōu)工期，此時(shí)總費(fèi)用最少．這個(gè)時(shí)間稱為最低成本日程．從關(guān)鍵路線入手，找出最少工程費(fèi)日程的方法，就是關(guān)鍵路線法(CPM)．工程費(fèi)用與完工期之間的關(guān)系可用下圖表示．總費(fèi)用直接費(fèi)用正常時(shí)143假設(shè)工序的直接費(fèi)用與工序時(shí)間是線性關(guān)系，設(shè)工序k每趕一天進(jìn)度所需要增加的費(fèi)用為q（k），則式中q（k）為費(fèi)用斜率,c為趕工所需費(fèi)用,n為正常完工所需費(fèi)用,nt為正常完工所需時(shí)間,ct為趕工時(shí)間．(2)時(shí)間—費(fèi)用優(yōu)化的計(jì)算顯然，費(fèi)用斜率越大的工序，每縮短一天，花的費(fèi)用就越多．在考慮縮短工程工期時(shí)，當(dāng)然是要縮短各關(guān)鍵工序中的某一道或某幾道工序的工期，而選擇縮短哪道工序要以總費(fèi)用最省為根據(jù)．假設(shè)工序的直接費(fèi)用與工序時(shí)間是線性關(guān)系，設(shè)工序k每趕一天144時(shí)間—費(fèi)用優(yōu)化的計(jì)算

首先應(yīng)確定工期與直接費(fèi)用的關(guān)系。即先對全部工序按正常時(shí)間計(jì)算參數(shù)，求出網(wǎng)絡(luò)圖的關(guān)鍵路線、工程周期和相應(yīng)的直接費(fèi)用。工程項(xiàng)目的總費(fèi)用=正常完工的直接費(fèi)用+趕工增加的費(fèi)用+間接費(fèi)用其次逐次壓縮費(fèi)用增長率q最小的關(guān)鍵工序延續(xù)時(shí)間，使直接費(fèi)用的增加最小。壓縮網(wǎng)絡(luò)時(shí)，按下面原則進(jìn)行：時(shí)間—費(fèi)用優(yōu)化的計(jì)算首先應(yīng)確定工期與直接費(fèi)用的關(guān)系。145(a)

壓縮關(guān)鍵線路上費(fèi)用增長率最小的工序時(shí)間，以增加最少的費(fèi)用來縮短工期。(b)

在選擇壓縮某項(xiàng)工序的延續(xù)時(shí)間時(shí)，既要滿足工序費(fèi)用一時(shí)間變化關(guān)系的限制，又要考慮網(wǎng)絡(luò)中和該作業(yè)并列的各工序時(shí)差數(shù)的限制，應(yīng)取這兩個(gè)限制的最小值。(c)

當(dāng)網(wǎng)絡(luò)圖不斷壓縮出現(xiàn)數(shù)條關(guān)鍵路線時(shí)，繼續(xù)壓縮工期，需要同時(shí)縮短這數(shù)條路線，僅縮短一條線路不會達(dá)到縮短工期的目的。(a)

壓縮關(guān)鍵線路上費(fèi)用增長率最小的工序時(shí)間，146

下面以例子說明通過縮短關(guān)鍵路線上工序時(shí)間來尋求最少工程費(fèi)日程的方法.

例某項(xiàng)工程根據(jù)有關(guān)資料，計(jì)算出了費(fèi)用斜率如表2，試制定該工程的最少工程費(fèi)計(jì)劃方案．下面以例子說明通過縮短關(guān)鍵路線上工序時(shí)間來尋求最147表2工程的有關(guān)資料及費(fèi)用斜率

工序緊前工序正常完工時(shí)間（天）正常完工直接費(fèi)用（百元）趕工時(shí)間（天）費(fèi)用斜率（百元）a/103074b/51042cb31522da,c42033ea,c52533fd63235ge5821hf,g5944合計(jì)

149

間接費(fèi)用5（百元/天）表2工程的有關(guān)資料及費(fèi)用斜率工序緊前正常完工正常完工直148圖1（a）

解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時(shí)間完工需25天，所需總費(fèi)用為:Ｗ＝14900+500×25＝27400元圖1（a）解根據(jù)表2，可繪出統(tǒng)籌圖1（a）:按正常時(shí)149圖1（b）

若使工程工期最短，即將所有工序時(shí)間都壓縮到其可能的最短時(shí)間，看其費(fèi)用情況如何．這時(shí)，統(tǒng)籌圖如圖1（b）所示．

工程完工期為17天，其趕工增加費(fèi)用(c－n)為:3×400＋1×200＋1×200＋1×300＋2×300＋3×500＋3×100+1×400＝4700元.總費(fèi)用Ｗ＝14900+4700+500×17＝28100元.顯然費(fèi)用太大，不是最優(yōu)．

圖1（b）若使工程工期最短，即將所有工序時(shí)間都壓縮到其可能150分析按正常時(shí)間完工的計(jì)劃方案，找出最少工程費(fèi)方案．由圖2（a）可以看出，在按正常時(shí)間完工的統(tǒng)籌圖中，有兩條關(guān)鍵路線：①→③→④→⑥→⑦，①→③→⑤→⑥→⑦。

圖2（a）

分析按正常時(shí)間完工的計(jì)劃方案，找出最少工程費(fèi)方案．由圖151要縮短工期，就要縮短關(guān)鍵工序的時(shí)間.

首先考慮壓縮關(guān)鍵線路上費(fèi)用增長率最小的工序時(shí)間，以增加最少的費(fèi)用來縮短工期。在上述兩條關(guān)鍵路線的情況下，縮短哪道關(guān)鍵工序，分析如下：圖1（a）

要縮短工期，就要縮短關(guān)鍵工序的時(shí)間.

首先考慮壓縮關(guān)152兩條關(guān)鍵路線在結(jié)點(diǎn)3和結(jié)點(diǎn)6之間有并聯(lián)部分，關(guān)鍵工序?yàn)閍、d、e、f、g和h，其中工序a、h為兩條關(guān)鍵路線所共有．要縮短工期，在費(fèi)用最小的情況下，首先考慮縮短共有的關(guān)鍵工序．其次考慮結(jié)點(diǎn)3和結(jié)點(diǎn)6之間的各關(guān)鍵工序d、e、f和g，因?yàn)樗鼈冎g是并聯(lián)的，所以要想縮短工程的