第9章 排序與統(tǒng)籌方法

1章

排序與統(tǒng)

運(yùn)籌學(xué)GuangdongUniversityofForeignStudies第九章排序與統(tǒng)籌方法第一節(jié)車間作業(yè)計(jì)劃模型第二節(jié)統(tǒng)籌方法

在本章中，我們將介紹車間作業(yè)計(jì)劃模型和統(tǒng)籌方法。這兩個(gè)問題盡管處理的方法有所不同，但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工作時(shí)，它們都將幫助我們應(yīng)該按照怎樣的次序、怎樣的時(shí)間表來做這些工作，使得效果最佳（例如完成全部工作所用時(shí)間最短或費(fèi)用最少等等）。2§1車間作業(yè)計(jì)劃模型

車間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。一、一臺(tái)機(jī)器、n個(gè)零件的排序問題二、兩臺(tái)機(jī)器、n個(gè)零件的排序問題3一、一臺(tái)機(jī)器、n個(gè)零件的排序問題例1.某車間只有一臺(tái)高精度的磨床，常常出現(xiàn)很多零件同時(shí)要求這臺(tái)磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間如下表所示。

應(yīng)該按照什么樣的加工順序來加工這六個(gè)零件，才能使得這六個(gè)零件在車間里停留的平均時(shí)間為最少？零件加工時(shí)間（小時(shí)）零件加工時(shí)間（小時(shí)）1231.82.00.54560.91.31.5

§1車間作業(yè)計(jì)劃模型4

例1解：如果我們用Pi表示安排在第i位加工的零件所需的時(shí)間，用Tj表示安排在第j位加工的零件在車間里總的停留時(shí)間，則有

Tj=P1+P2+…+Pj-1+Pj=

不同的加工順序得到不同的各零件的平均停留時(shí)間，如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設(shè)法找到一種簡便的算法。對(duì)于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停留時(shí)間為Tj

，Tj=

§1車間作業(yè)計(jì)劃模型5可知這六個(gè)零件的停留時(shí)間為：

T1+T2+T3+T4+T5+T6＝P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)＝6P1+5P2+4P3+3P4+2P5+P6.

那么各個(gè)零件平均停留時(shí)間為

從上式可知，對(duì)于一臺(tái)機(jī)器n個(gè)零件的排序問題，只要系數(shù)越大，配上加工時(shí)間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，加工時(shí)間越多的零件排在越后面，可使各零件的平均停留時(shí)間最少。

§1車間作業(yè)計(jì)劃模型6二、兩臺(tái)機(jī)器、n個(gè)零件例2.某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在磨床上加工，每臺(tái)機(jī)器上各零件加工時(shí)間如下表所示。

應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間為最少？零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.25

§1車間作業(yè)計(jì)劃模型7

解：由于每個(gè)零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來表示各零件加工的開始時(shí)間與完成時(shí)間，這種圖是由一根時(shí)間軸和車床、磨床在每個(gè)時(shí)間段的狀況的圖形所構(gòu)成。零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.25

§1車間作業(yè)計(jì)劃模型8圖12-1

從上圖中我們可以看出，加工時(shí)間的延長主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時(shí)間越短的零件越早加工，減少磨床等待的時(shí)間；另一方面把在磨床上加工時(shí)間越短的零件越晚加工，以便充分利用前面的時(shí)間，這樣我們就得到了使完成全部零件加工任務(wù)所需總時(shí)間最少的零件排序方法。123451車床磨床23450101.52.01.01.250.750.50.251.752.51.25

尋找例2的最優(yōu)解：我們?cè)谏媳碇姓业剿谐龅淖疃碳庸r(shí)間是0.25,它是第二道工序磨床加工零件2的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行。如表中紅色線條所示。零件車床(第一工序)磨床(第二工序)零件車床(第一工序)磨床(第二工序)1231.52.01.00.50.251.75451.250.752.51.25

§1車間作業(yè)計(jì)劃模型10接著，我們又找到最短加工時(shí)間為0.5，這一時(shí)間與磨床（第二工序）有關(guān)，我們把磨床加工時(shí)間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時(shí)把表中的零件1所在的行劃去。如表中黃色線條所示。零件車床(第一工序)磨床(第二工序)零件車床(第一工序)磨床(第二工序)1231.52.01.00.50.251.75451.250.752.51.25

§1車間作業(yè)計(jì)劃模型11

下一個(gè)最短加工時(shí)間為0.75，這個(gè)加工時(shí)間是車床（第一工序）加工零件5的所需時(shí)間，故把零件5排在加工順序的第一位上，同時(shí)把表中的零件5所在的行劃去。如表中藍(lán)色線條所示。零件車床(第一工序)磨床(第二工序)零件車床(第一工序)磨床(第二工序)1231.52.01.00.50.251.75451.250.752.51.25

§1車間作業(yè)計(jì)劃模型12同樣，下一個(gè)最短加工時(shí)間為1，這是車床加工零件3的所需時(shí)間，故把零件3排在第二位上，同時(shí)把零件3所在的行劃去。如表中黑色線條所示。零件車床(第一工序)磨床(第二工序)零件車床(第一工序)磨床(第二工序)1231.52.01.00.50.251.75451.250.752.51.25

§1車間作業(yè)計(jì)劃模型13這樣就得到了最優(yōu)加工順序：5，3，4，1，2。0.751.01.251.52.01.251.752.50.50.255磨床車床3412534127這樣一共只需7個(gè)小時(shí)就能完成全部加工。

§1車間作業(yè)計(jì)劃模型14

從例2中我們可以歸納出關(guān)于兩臺(tái)機(jī)器n個(gè)零件的排序問題，使得全部任務(wù)總的時(shí)間最短的排序算法。步驟1:在加工所需時(shí)間表上選出最短加工時(shí)間tij，這是第i工序加工j零件所需時(shí)間，步驟2:當(dāng)i=1時(shí)，將零件j的順序盡量靠前，若i=2時(shí)，將零件j的順序盡量靠后。步驟3:在表上劃去零件j的所在行，回到步驟1。

§1車間作業(yè)計(jì)劃模型15思考題：

m臺(tái)機(jī)器n個(gè)零件的排序問題如何解決？

§1車間作業(yè)計(jì)劃模型16§2統(tǒng)籌方法

統(tǒng)籌法又稱網(wǎng)絡(luò)計(jì)劃法。它是以網(wǎng)絡(luò)圖反映、表達(dá)計(jì)劃安排，據(jù)以選擇最優(yōu)工作方案，組織協(xié)調(diào)和控制生產(chǎn)（項(xiàng)目）的進(jìn)度（時(shí)間）和費(fèi)用（成本），使其達(dá)到預(yù)定目標(biāo)，獲得更佳經(jīng)濟(jì)效益的一種優(yōu)化決策方法。

1957年，美國化學(xué)公司DuPont的M.R.Walker與Rand通用電子計(jì)算機(jī)公司的J.E.Kelly為了協(xié)調(diào)公司內(nèi)部不同業(yè)務(wù)部門的工作,共同研究出關(guān)鍵路線方法（簡記作CPM）.首次把這一方法用于一家化工廠的籌建，結(jié)果籌建工程提前兩個(gè)月完成.隨后又把這一方法用于工廠的維修，結(jié)果使停工時(shí)間縮短了47個(gè)小時(shí)，當(dāng)年就取得節(jié)約資金達(dá)百萬元的要觀效益。171958年，美國海軍武器規(guī)劃局特別規(guī)劃室研制含約3000項(xiàng)工作任務(wù)的北極星導(dǎo)彈潛艇計(jì)劃，參與的廠商達(dá)11000多家。為了有條不紊地實(shí)施如此復(fù)雜的工作，特別規(guī)劃室領(lǐng)導(dǎo)人W.Fazar積極支持與推廣由專門小組創(chuàng)建的計(jì)劃評(píng)審技術(shù)（簡記作PERT）。結(jié)果研制計(jì)劃提前兩個(gè)完成，取得了極大的成功。

CPM在民用企業(yè)與PERT在軍事工業(yè)中的顯著成效,自然引起了普遍的重視。很快CPM與PERT就被應(yīng)用于工業(yè)、農(nóng)業(yè)、國防與科研等等復(fù)雜的計(jì)劃管理工作中,隨后又推廣到世界各國。在應(yīng)用推廣CPM與PERT的過程中,又派生出多種各具特點(diǎn)，各有側(cè)重的類似方法。但是萬變不離其宗，各種有所不同的方法，其基本原理都源于CPM與PERT。

CPM與PERT兩種方法實(shí)質(zhì)上大同小異，因此，人們把CPM與PERT及其他類似方法統(tǒng)稱為網(wǎng)絡(luò)計(jì)劃技術(shù)，簡稱為網(wǎng)絡(luò)技術(shù)或網(wǎng)絡(luò)方法，簡記為統(tǒng)籌法。

統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)行分別討論：一、計(jì)劃網(wǎng)絡(luò)圖統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖?！?統(tǒng)籌方法19網(wǎng)絡(luò)圖畫法(一)、結(jié)構(gòu)網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)數(shù)。例如：5a12§2統(tǒng)籌方法20(二)、畫法注意事項(xiàng)：(1)、從左→右123456782433121§2統(tǒng)籌方法21(2)、兩事項(xiàng)間只有一個(gè)工序bij75a3§2統(tǒng)籌方法22(3)、不允許回路123§2統(tǒng)籌方法23(4)、虛工序的運(yùn)用120②正確表達(dá)工序的前行、后續(xù)關(guān)系(連結(jié)、隔離)①解決畫法中問題：網(wǎng)絡(luò)圖中只有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)，中間點(diǎn)前后均要有弧相連接，不允許中斷?！?統(tǒng)籌方法24123465782403130201§2統(tǒng)籌方法25ijk750a3b§2統(tǒng)籌方法26例1、假設(shè)某工作有a,b,c,d四個(gè)工序,c在a,b完工后開始，d在b完工后開始。cabdabcd§2統(tǒng)籌方法27例3、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表12-8所示，請(qǐng)畫出其統(tǒng)籌方法網(wǎng)絡(luò)圖。工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d§2統(tǒng)籌方法28解：用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表。５３abcde601383815２１４工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d§2統(tǒng)籌方法29

例４、把例３的工序進(jìn)度表做一些擴(kuò)充，如下表，請(qǐng)畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間(天)緊前工序abcd60151338－aacefgh810165b，ｄdde,ｆ,ｇ§2統(tǒng)籌方法30工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間(天)緊前工序abcd60151338－aacefgh810165b，ｄdde,ｆ,ｇ152643a60b158e1013dc38f7g168由于ｄ是ｆ的緊前工序，故ｄ的結(jié)束應(yīng)該是ｆ的開始，所以代表ｆ的弧的起點(diǎn)應(yīng)該是④，由于工序ｂ的結(jié)束也是④，所以工序ｂ也成了工序ｆ的緊前工序，與題意不符。為此我們?cè)O(shè)立虛工序。虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時(shí)間。§2統(tǒng)籌方法31工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間(天)緊前工序abcd60151338－aacefgh810165b，ｄdde,ｆ,ｇ152643a60b158e1013dc38fg16在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此需增加一個(gè)點(diǎn)和虛工序§2統(tǒng)籌方法32工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間(天)緊前工序abcd60151338－aacefgh810165b，ｄdde,ｆ,ｇ152643a60b158e1013dc38f716g8h5在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。§2統(tǒng)籌方法33練習(xí)工序內(nèi)容工時(shí)(天)緊前工序

A初步研究1/B研究選點(diǎn)2AC準(zhǔn)備調(diào)研方案4AD聯(lián)系調(diào)研點(diǎn)2BE培訓(xùn)工作人員3B,CF準(zhǔn)備表格1CG實(shí)地調(diào)研5D,E,FH寫調(diào)研報(bào)告2GI開會(huì)匯總3H12325FE200C413DBAGHI123456789§2統(tǒng)籌方法35二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線路線：在網(wǎng)絡(luò)圖上從始點(diǎn)（發(fā)點(diǎn)）開始，沿弧的方向（即按各工序的順序）連續(xù)不斷地到終點(diǎn)（收點(diǎn)）的一條路線。例如：12325FE200C413DBAGHI123456789§2統(tǒng)籌方法36關(guān)鍵路線：網(wǎng)絡(luò)中最長的路線，通常可用雙線標(biāo)出。關(guān)鍵路線的長等于該路線上各工序的時(shí)間之和，又稱為工程時(shí)間或工期，其它路線稱為非關(guān)鍵路線。關(guān)鍵（非關(guān)鍵）工序：關(guān)鍵路線上的各工序，其它工序稱為非關(guān)鍵工序。12325FE200C413DBAGHI123456789工期T＝18§2統(tǒng)籌方法37顯然，縮短工期就是要縮短關(guān)鍵路線的長度，也就是說要加快關(guān)鍵工序的進(jìn)度。而縮短非關(guān)鍵路線的長度或縮短非關(guān)鍵工序的時(shí)間均不能縮短工期。12325FE200C413DBAGHI123456789工期T＝18§2統(tǒng)籌方法38在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線，具體過程如下表,求：完成此工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久。§2統(tǒng)籌方法39工序代號(hào)工序內(nèi)容所需時(shí)間(天)緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h§2統(tǒng)籌方法40解：據(jù)表繪制網(wǎng)絡(luò)圖如圖。12346785a60b45echj35ig1030d204025f1815如圖,①-②-③-⑦-⑧就是一條關(guān)鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時(shí)進(jìn)行，所以網(wǎng)絡(luò)中最長的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線就是關(guān)鍵路線?！?統(tǒng)籌方法41下面我們給出找關(guān)鍵路線的辦法首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個(gè)工序的最早開始時(shí)間（ES)和最早結(jié)束時(shí)間（EF)，設(shè)一個(gè)工序所需的時(shí)間為t，這對(duì)于同一個(gè)工序來說，有:EF=ES+t。工序a的最早開始時(shí)間工序a的最早完成時(shí)間11a[0，60]60§2統(tǒng)籌方法42g[80,110]30d[60.80]20e[60.100]h[100,115]15j[135,170]a[0,60]60其次,從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情況下各個(gè)工序的最晚開始時(shí)間(縮寫為LS)和最晚結(jié)束時(shí)間（縮寫為LF),顯然對(duì)同一工序有:LS=LF-t85b[60,105]4535i[110,135]4025f[70,88]1841017263c[60,70]§2統(tǒng)籌方法43f[70,88]10[107,117]40[80,120]e[60.100]30[80,110]g[80,110]d[60.80]20[60,80]i[110.135]15[120,135]j[135,170]35[135,170]a[0,60]60[0,60]

運(yùn)用此法則，可以從首點(diǎn)開始計(jì)算出每個(gè)工序的LF與LS，如下圖所示。185b[60,105]45[90,135]c[60,70]h[100,115]25[110,135]18[117,135]4接著，可以計(jì)算出每一個(gè)工序的時(shí)差，把在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的時(shí)差，對(duì)每個(gè)工序來說其時(shí)差記為Ts有

Ts=LS-ES=LF-EF7236

最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如下表所示。一般來說，關(guān)鍵工序的時(shí)差為零。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線?！?統(tǒng)籌方法45練習(xí)：設(shè)某工程的資料如以下網(wǎng)絡(luò)圖所示，用時(shí)差的方法求關(guān)鍵線路。1253411252248967423abcde4fghijk§2統(tǒng)籌方法46三、完成工序所需時(shí)間與關(guān)鍵路線當(dāng)完成工序所需時(shí)間不確定的情況下如何求網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線？例6.長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn),培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項(xiàng)活動(dòng)的信息如表12-12所示,要求繪制出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線，并確定開始這個(gè)組織工作的時(shí)間以保證培訓(xùn)工作如期舉行?！?統(tǒng)籌方法47活動(dòng)(工序)活動(dòng)（工序）內(nèi)容緊前活動(dòng)(工序)abcdefghi制定培訓(xùn)計(jì)劃選聘培訓(xùn)教師列出一些可供選擇的培訓(xùn)地點(diǎn)確定培訓(xùn)地點(diǎn)確定培訓(xùn)的日程安排落實(shí)教學(xué)設(shè)備,器材,資料發(fā)培訓(xùn)通知并確定學(xué)員名單訂旅館房間處理最后的一些事務(wù)-a-cb,deb,dgf,g§2統(tǒng)籌方法4812356487abecdfghi活動(dòng)活動(dòng)（工序）內(nèi)容緊前活動(dòng)abcdefghi制定培訓(xùn)計(jì)劃選聘培訓(xùn)教師列出一些可供選擇的培訓(xùn)地點(diǎn)確定培訓(xùn)地點(diǎn)確定培訓(xùn)的日程安排落實(shí)教學(xué)設(shè)備,器材,資料發(fā)培訓(xùn)通知并確定學(xué)員名單訂旅館房間處理最后的一些事務(wù)-a-cb,deb,dgf,g

由于是第一次搞培訓(xùn)，缺乏統(tǒng)計(jì)來確定完成每個(gè)活動(dòng)所需時(shí)間，但對(duì)所需時(shí)間做了三種估計(jì)：1.樂觀時(shí)間。指所需最少時(shí)間，用a表示。2.最可能時(shí)間。指正常時(shí)間，用m表示。3.悲觀時(shí)間。指不順利情況下，最多時(shí)間，用b表示。如下表（單位：周）所示：活動(dòng)樂觀時(shí)間最可能時(shí)間悲觀時(shí)間abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5

顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時(shí)間的概率分布近似服從分布。我們可以用如下公式計(jì)算出完成活動(dòng)所需的平均時(shí)間：

以及方差

§2統(tǒng)籌方法51例如：完成工作g所需平均時(shí)間：同時(shí)求出方差為§2統(tǒng)籌方法52

同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差，如下表：

活動(dòng)T（平均時(shí)間）方差活動(dòng)T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.028§2統(tǒng)籌方法53i[13,15]2i[13,15]

下面就用平均時(shí)間代替完成活動(dòng)所需時(shí)間，并在網(wǎng)絡(luò)圖上標(biāo)上每個(gè)活動(dòng)最早開始時(shí)間和最早結(jié)束時(shí)間，如圖12-14所示。2345876同樣也可以標(biāo)上最晚開始時(shí)間和最晚完成時(shí)間等。a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]h[9,13]3222142412345876a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]h[9,13]2[1,3]1[10,11]4[5,9]4[9,13]2[3,5]2[0,2]3[2,5]2[13,15]2[11,13]圖12-14圖12-151

從表12-15上我們找到了一條從發(fā)點(diǎn)到收點(diǎn)由關(guān)鍵工序a,b,g,h,i組成的關(guān)鍵路線，用雙線標(biāo)出來。則完成培訓(xùn)工作所需的平均時(shí)間為各關(guān)鍵路線的時(shí)間之和：

=2+3+4+4+2=15（周）同時(shí)完成時(shí)間近似服從一定的概率分布正態(tài)分布，則均值為關(guān)鍵路線上各關(guān)鍵活動(dòng)之均值之和15，方差也為關(guān)鍵路線上各關(guān)鍵活動(dòng)方差之和1.05。由此我們可以計(jì)算出此項(xiàng)培訓(xùn)組織工作不同完工時(shí)間的概率，如16周內(nèi)完工的概率。§2統(tǒng)籌方法55

為求此概率，可以先求u值。式中的T為預(yù)定完工時(shí)間16，E（T）=15，算得u=0.976。查正態(tài)分布函數(shù)表可知概率為0.8355。即16周內(nèi)完工的概率為83.55%.§2統(tǒng)籌方法56其正態(tài)分布圖如圖12-16所示：16圖12-16§2統(tǒng)籌方法57四、網(wǎng)絡(luò)優(yōu)化得到初始的計(jì)劃方案，但通常要對(duì)初始方案進(jìn)行調(diào)整與完善。根據(jù)計(jì)劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(jì)劃方案。

1.時(shí)間-資源優(yōu)化做法：1）優(yōu)先安排關(guān)鍵工序所需的資源。2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間。3）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡?！?統(tǒng)籌方法58下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。在例5中，若加工工人為65人，并假定這些工人可完成這5個(gè)工序任一個(gè)，下面來尋求一個(gè)時(shí)間-資源最優(yōu)方案。如表12-16所示：表12-16工序需要人數(shù)最早開始時(shí)間所需時(shí)間時(shí)差d5860200f22701847g428030h391001520i26110250§2統(tǒng)籌方法59d(58人）2015h(39人)g(42人）i(26人）

在圖的上半部中，工序代號(hào)后的數(shù)字是人數(shù)，線下面的數(shù)字是非關(guān)鍵工序時(shí)差長度。圖的下半部表示從第60天至135天內(nèi)的75天里，所需機(jī)械加工工人數(shù)，這樣的圖稱為資源負(fù)荷圖。274635f(22人）1858人64人80人81人42人26人65人60801001201303025圖12-17

若上述工序都按最早開始時(shí)間安排，那么從第60天至第135天的75天里，所需的機(jī)械加工工人人數(shù)如圖12-17所示。h(39人）g(42人）d(58人）i(26人）

同時(shí)我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我們讓非關(guān)鍵工序f從第80天開始，工序h從第110天開始。找到了時(shí)間-資源優(yōu)化的方案，如圖12-18所示，在不增加工人的情況下保證了工程按期完成。246753f(22人）工人數(shù)65人608010012013058人42人64人26人65人圖12-182.時(shí)間-費(fèi)用優(yōu)化需要考慮時(shí)間與費(fèi)用的問題：在既定的時(shí)間前工程完工的前提下，使得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。這些是時(shí)間-費(fèi)用優(yōu)化要研究和解決的問題。直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。§2統(tǒng)籌方法62

工序的最快完成時(shí)間：指完成時(shí)間的最高限度。我們?cè)O(shè)完成工序j的正常所需時(shí)間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時(shí)間為T`j,直接費(fèi)用為c`j。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動(dòng)率。有

時(shí)間--費(fèi)用優(yōu)化問題可建立兩個(gè)線性規(guī)劃模型。模型一，在既定的時(shí)間T完工的前提下，問各工序的完成時(shí)間為多少才使因縮短工期而增加的直接費(fèi)用最少。§2統(tǒng)籌方法63設(shè)工序（i,j)的提前完工時(shí)間為Yij,我們用Tij,T`ij分別表示正常完工時(shí)間與最快完工的時(shí)間，則有工序（i,j)的實(shí)際完工時(shí)間為：Tij-Yij。我們用Cij,C`ij表示用正常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，Kij為工序（i,j)的直接費(fèi)用變動(dòng)率。得到這個(gè)問題的線性規(guī)劃模型如下：S.t.Xj-XiTij-Y`ij,對(duì)一切?。╥,j)YijTij-T`ij,對(duì)一切弧（i,j)Xn-X1T,

Xi0，Yij0?！?統(tǒng)籌方法64例7.例5所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時(shí)間與最快完工時(shí)間，以及對(duì)應(yīng)正常完工時(shí)間與最快完工時(shí)間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表12-17所示?！?統(tǒng)籌方法65工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接費(fèi)用直接費(fèi)用變動(dòng)率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-c

該工程要求在150天內(nèi)完工，問每個(gè)工序應(yīng)比正常完工時(shí)間提前多少天完成，才能使整個(gè)工程因縮短工期而增加的直接費(fèi)用為最少。如果工期要求在140天完工呢？12345678abfehgijd§2統(tǒng)籌方法67解：根據(jù)此網(wǎng)絡(luò)圖建立數(shù)學(xué)模型。設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為yij。目標(biāo)函數(shù):minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40虛擬?。?，5）

x7-x515-y57x7-x625-y67x1=0,y120,