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

第十二章排序與統(tǒng)籌方法§1車(chē)間作業(yè)計(jì)劃模型§2統(tǒng)籌方法在本章中，我們將介紹車(chē)間作業(yè)計(jì)劃模型和統(tǒng)籌方法。這兩個(gè)問(wèn)題盡管處理的方法有所不同，但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工作時(shí)，它們都將幫助我們應(yīng)該按照怎樣的次序、怎樣的時(shí)間表來(lái)做這些工作，使得效果最佳（例如完成全部工作所用時(shí)間最短或費(fèi)用最少等等）。1§1車(chē)間作業(yè)計(jì)劃模型車(chē)間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題二、兩臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題2§1車(chē)間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題例1.某車(chē)間只有一臺(tái)高精度的磨床，常常出現(xiàn)很多零件同時(shí)要求這臺(tái)磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間如下表所示。

應(yīng)該按照什么樣的加工順序來(lái)加工這六個(gè)零件，才能使得這六個(gè)零件在車(chē)間里停留的平均時(shí)間為最少？零件加工時(shí)間（小時(shí)）零件加工時(shí)間（小時(shí)）1231.82.00.54560.91.31.53§1車(chē)間作業(yè)計(jì)劃模型

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

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時(shí)間，如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問(wèn)題，而且我們要設(shè)法找到一種簡(jiǎn)便的算法。對(duì)于某種加工順序，我們知道安排在第j位加工的零件在車(chē)間里總的停留時(shí)間為T(mén)j，Tj=可知這六個(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è)零件的排序問(wèn)題，只要系數(shù)越大，配上加工時(shí)間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，加工時(shí)間越多的零件排在越后面，可使各個(gè)零件的平均停留時(shí)間為最少。4§1車(chē)間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件

例2.某工廠根據(jù)合同定做一些零件，這些零件要求先在車(chē)床上車(chē)削，然后再在磨床上加工，每臺(tái)機(jī)器上各零件加工時(shí)間如表12-5所示。表12-5

應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間為最少？解：由于每個(gè)零件必須先進(jìn)行車(chē)床加工，再進(jìn)行磨床加工，所以在車(chē)床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車(chē)床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來(lái)表示各零件加工的開(kāi)始時(shí)間與完成時(shí)間，這種圖是由一根時(shí)間軸和車(chē)床、磨床在每個(gè)時(shí)間段的狀況的圖形所構(gòu)成。零件車(chē)床磨床零件車(chē)床磨床1231.52.01.00.50.251.75451.250.752.51.255§1車(chē)間作業(yè)計(jì)劃模型圖12-1從上圖中我們可以看出，加工時(shí)間的延長(zhǎng)主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。為了減少磨床的停工待料，我們應(yīng)該一方面把在車(chē)床上加工時(shí)間越短的零件越早加工，減少磨床等待的時(shí)間；另一方面把在磨床上加工時(shí)間越長(zhǎng)的零件越晚加工，以便充分利用前面的時(shí)間，這樣我們就得到了使完成全部零件加工任務(wù)所需總時(shí)間最少的零件排序方法。123451車(chē)床磨床23450106§1車(chē)間作業(yè)計(jì)劃模型尋找例2的最優(yōu)解：我們?cè)诒?2-5中找到所列出的最短加工時(shí)間是0.25,它是第二道工序磨床加工零件2的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行。如表12-6中紅色線條所示。

接著，我們又找到最短加工時(shí)間為0.5，這一時(shí)間與磨床（第二工序）有關(guān)，我們把磨床加工時(shí)間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時(shí)把表中的零件1所在的行劃去。如表12-6中黃色線條所示。下一個(gè)最短加工時(shí)間為0.75，這個(gè)加工時(shí)間是車(chē)床（第一工序）加工零件5的所需時(shí)間，故把零件5排在加工順序的第一位上，同時(shí)把表中的零件5所在的行劃去。如表12-6中藍(lán)色線條所示。零件車(chē)床（第一工序）磨床（第二工序）零件車(chē)床（第一工序）磨床（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表12-67

同樣，下一個(gè)最短加工時(shí)間為1，這是車(chē)床加工零件3的所需時(shí)間，故把零件3排在第二位上，同時(shí)把零件3所在的行劃去。如表12-6中黑色線條所示。這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個(gè)小時(shí)就能完成全部加工。從例2中我們可以歸納出關(guān)于兩臺(tái)機(jī)器n個(gè)零件的排序問(wèn)題，使得全部任務(wù)總的時(shí)間最短的排序算法。在加工所需時(shí)間表上選出最短加工時(shí)間tij，這是第i工序加工j零件所需時(shí)間，當(dāng)i=1時(shí)，將零件j的順序盡量靠前，若i=2時(shí)，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1?！?車(chē)間作業(yè)計(jì)劃模型8§2統(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ò)圖，也就是將工序（或稱(chēng)為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例3、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表12-8所示，請(qǐng)畫(huà)出其統(tǒng)籌方法網(wǎng)絡(luò)圖。表12-8工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購(gòu)配套零件外購(gòu)生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d9§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開(kāi)始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開(kāi)始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)數(shù)．

１２４５３abcde601383815圖12-410§2統(tǒng)統(tǒng)籌方法法例４、把把例３的的工序進(jìn)進(jìn)度表做做一些擴(kuò)擴(kuò)充，如如表12-9，，請(qǐng)畫(huà)出出其統(tǒng)籌籌方法的的網(wǎng)絡(luò)圖圖。表12-9工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ11§2統(tǒng)統(tǒng)籌方法法解：我們們把工序序ｆ擴(kuò)充充到圖12-4發(fā)生了了問(wèn)題，，由于ｄｄ是ｆ的的緊前工工序，故故ｄ的結(jié)結(jié)束應(yīng)該該是ｆ的的開(kāi)始，，所以代代表ｆ的的弧的起起點(diǎn)應(yīng)該該是④，，由于工工序ｂ的的結(jié)束也也是④，，所以工工序ｂ也也成了工工序ｆ的的緊前工工序，與與題意不不符。為此我們們?cè)O(shè)立虛虛工序。。虛工序序是實(shí)際際上并不不存在而而虛設(shè)的的工序，，用來(lái)表表示相鄰鄰工序的的銜接關(guān)關(guān)系，不不需要人人力、物物力等資資源與時(shí)時(shí)間。152643a60b158e1013dc38f圖12-512§2統(tǒng)統(tǒng)籌方法法在網(wǎng)絡(luò)圖圖上添加加ｇ、ｈｈ工序得得網(wǎng)絡(luò)圖圖12-6。在統(tǒng)籌方方法的網(wǎng)網(wǎng)絡(luò)圖中中不允許許兩個(gè)點(diǎn)點(diǎn)之間多多于一條條弧，因因此增加加了一個(gè)個(gè)點(diǎn)和虛虛工序如如圖12-7。。1256734a6015bec13d388h510fg16圖12-613§2統(tǒng)統(tǒng)籌方法法在繪制統(tǒng)統(tǒng)籌方法法的網(wǎng)絡(luò)絡(luò)圖時(shí)，，要注意意圖中不不能有缺缺口和回回路。1257834a6015bec13d388h510f616g圖12-714§2統(tǒng)統(tǒng)籌方法法二、網(wǎng)絡(luò)絡(luò)時(shí)間與與關(guān)鍵路路線在繪制出出網(wǎng)絡(luò)圖圖之后，，我們可可以由網(wǎng)網(wǎng)絡(luò)圖求求出：1、完成成此工程程項(xiàng)目所所需的最最少時(shí)間間。2、每個(gè)個(gè)工序的的開(kāi)始時(shí)時(shí)間與結(jié)結(jié)束時(shí)間間。3、關(guān)鍵鍵路線及及其應(yīng)用用的關(guān)鍵鍵工序。。4、非關(guān)關(guān)鍵工序序在不影影響工程程的完成成時(shí)間的的前提下下，其開(kāi)開(kāi)始時(shí)間間與結(jié)束束時(shí)間可以推推遲多久久。例5、某某公司裝裝配一條條新的生生產(chǎn)線，，具體過(guò)過(guò)程如表表12-10,求：完完成此工程的最最少時(shí)間間，關(guān)鍵鍵路線及及相應(yīng)的的關(guān)鍵工工序，各各工序的的最早開(kāi)開(kāi)始時(shí)間間和非關(guān)鍵工工序在不不影響工工程完成成時(shí)間的的前提下下，其開(kāi)開(kāi)始時(shí)間間與結(jié)束束時(shí)間可可以推遲多久久。15§2統(tǒng)統(tǒng)籌方法法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購(gòu)零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h16§2統(tǒng)統(tǒng)籌方法法解：據(jù)表表12-10,繪制網(wǎng)網(wǎng)絡(luò)圖如如圖12-8。。圖12-8如圖12-8,①-②-③③-⑦-⑧就是是一條關(guān)關(guān)鍵路線線，我們們要干完完所有的的工序就必須走走完所有有這樣的的路線，，由于很很多工序序可以同同時(shí)進(jìn)行行，所以以網(wǎng)絡(luò)中中最長(zhǎng)的路線線就決定定了完成成整個(gè)工工程所需需的最少少時(shí)間，，這條路路線稱(chēng)為為關(guān)鍵路路線。12346785a60b45echj35ig1030d204025f181517§2統(tǒng)統(tǒng)籌方法法下面我們們給出找找關(guān)鍵路路線的辦辦法首先，從從網(wǎng)絡(luò)的的發(fā)點(diǎn)開(kāi)開(kāi)始，按按順序計(jì)計(jì)算出每每個(gè)工序序的最早早開(kāi)始時(shí)時(shí)間（ES)和最最早結(jié)束束時(shí)間（（EF)，設(shè)設(shè)一個(gè)工工序所需需的時(shí)間間為t，，這對(duì)于于同一個(gè)工序來(lái)來(lái)說(shuō)，有有EF=ES+t。。工序a的的最早開(kāi)始時(shí)間間工序a的的最早完成時(shí)間間11a[0，，60]60圖12-918§2統(tǒng)統(tǒng)籌方法法圖12-10其次,從從網(wǎng)絡(luò)的的收點(diǎn)開(kāi)開(kāi)始計(jì)算算出在不不影響整整個(gè)工程程最早結(jié)結(jié)束時(shí)間間的情況下各個(gè)個(gè)工序的的最晚開(kāi)開(kāi)始時(shí)間間(縮寫(xiě)寫(xiě)為L(zhǎng)S)和最最晚結(jié)束束時(shí)間（（縮寫(xiě)為為L(zhǎng)F),顯然對(duì)同同一工序序有LS=LF-t1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]184101519§2統(tǒng)統(tǒng)籌方法法運(yùn)用此法法則，可可以從首首點(diǎn)開(kāi)始始計(jì)算出出每個(gè)工工序的LF與LS，如如圖12-11所示。接著，可可以計(jì)算算出每一一個(gè)工序序的時(shí)差差，把在在不影響響工程最最早結(jié)束束時(shí)間的條件下下，工序序最早開(kāi)開(kāi)始（或或結(jié)束））的時(shí)間間可以推推遲的時(shí)時(shí)間，成成為該工工序的時(shí)差，，對(duì)每個(gè)個(gè)工序來(lái)來(lái)說(shuō)其時(shí)時(shí)差記為為T(mén)s有Ts=LS-ES=LF-EF1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,13520§2統(tǒng)統(tǒng)籌方法法最后將各各工序的的時(shí)差，，以及其其他信息息構(gòu)成工工序時(shí)間間表如表表12-11所所示。這樣就找找到了一一條由關(guān)關(guān)鍵工序序a,d,g,i和j依次連連接成的的從發(fā)點(diǎn)點(diǎn)到收點(diǎn)點(diǎn)的關(guān)鍵路線線。21三、完成成工序所所需時(shí)間間與關(guān)鍵鍵路線當(dāng)完成工工序所需需時(shí)間不不確定的的情況下下如何求求網(wǎng)絡(luò)時(shí)時(shí)間和關(guān)關(guān)鍵路線線？例6.長(zhǎng)長(zhǎng)征征研究院院培訓(xùn)中中心負(fù)責(zé)責(zé)明年春春天的各各干部的的工商管管理培訓(xùn)訓(xùn)，培訓(xùn)訓(xùn)中心列列出有關(guān)關(guān)培訓(xùn)組組織的各各項(xiàng)活動(dòng)動(dòng)的信息息如表12-12所示示，要求求繪制出出統(tǒng)籌方方法的網(wǎng)網(wǎng)絡(luò)圖，，設(shè)法求求出網(wǎng)絡(luò)絡(luò)時(shí)間和和關(guān)鍵路路線，并并確定開(kāi)開(kāi)始這個(gè)個(gè)組織工工作的時(shí)時(shí)間以保保證培訓(xùn)訓(xùn)工作如如期舉行行。解：由表表12-12，，繪出統(tǒng)統(tǒng)籌方法法的網(wǎng)絡(luò)絡(luò)圖如圖圖12-12所所示。12356487abecdfghi圖12-12§2統(tǒng)統(tǒng)籌方法法22§2統(tǒng)統(tǒng)籌方法法

活動(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,g23§2統(tǒng)統(tǒng)籌方法法由于是第第一次搞搞培訓(xùn)，，缺乏統(tǒng)統(tǒng)計(jì)來(lái)確確定完成成每個(gè)活活動(dòng)所需需時(shí)間，，但對(duì)所需需時(shí)間做做了三種種估計(jì)：：1.樂(lè)觀觀時(shí)間。。指所需需最少時(shí)時(shí)間，用用a表示示。2.最可可能時(shí)間間。指正正常時(shí)間間，用m表示。。3.悲觀觀時(shí)間。。指不順順利情況況下，最最多時(shí)間間，用b表示。。如表12-13所示示：表12-13單單位位：周活動(dòng)樂(lè)觀時(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.524§2統(tǒng)統(tǒng)籌方法法顯然這三三種完成成活動(dòng)所所需時(shí)間間都具有有一定概概率，由由經(jīng)驗(yàn)，，我們可可以可以假定定這些時(shí)時(shí)間的概概率分布布近似服服從分分布布。我們們可以用用如下公公式計(jì)算出完成成活動(dòng)所所需的平平均時(shí)間間：以及方差差例如：完完成工作作g所需需平均時(shí)時(shí)間：同時(shí)求出出方差為為25§2統(tǒng)統(tǒng)籌方法法同樣可以以求出每每個(gè)活動(dòng)動(dòng)的完成成所需平平均時(shí)間間及方差差，如表表12-14：：表12-14活動(dòng)T（平均時(shí)間）方差活動(dòng)T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02826§2統(tǒng)統(tǒng)籌方法法下面就用用平均時(shí)時(shí)間代替替完成活活動(dòng)所需需時(shí)間，，并在網(wǎng)網(wǎng)絡(luò)圖上上標(biāo)上每每個(gè)活動(dòng)最早開(kāi)開(kāi)始時(shí)間間和最早早結(jié)束時(shí)時(shí)間，如如圖12-14所示。。12345876同樣也可以以標(biāo)上最晚晚開(kāi)始時(shí)間間和最晚完完成時(shí)間等等。a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]32221424212345876a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]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-1527§2統(tǒng)籌籌方法從表12-15上我我們找到了了一條從發(fā)發(fā)點(diǎn)到收點(diǎn)點(diǎn)由關(guān)鍵工工序a,b,g,h,i組成成的關(guān)鍵路線，，用雙線標(biāo)標(biāo)出來(lái)。則則完成培訓(xùn)訓(xùn)工作所需需的平均時(shí)時(shí)間為各關(guān)關(guān)鍵路線的時(shí)間之和和：=2+3+4+4+2=15（周）同時(shí)完成時(shí)時(shí)間近似服服從一定的的概率分布布正態(tài)分布布，則均值值為關(guān)鍵路路線上各關(guān)鍵活活動(dòng)之均值值之和15，方差也也為關(guān)鍵路路線上各關(guān)關(guān)鍵活動(dòng)方方差之和1.05。。由此我們可可以計(jì)算出出此項(xiàng)培訓(xùn)訓(xùn)組織工作作不同完工工時(shí)間的概概率，如16周內(nèi)完工的概概率。為求此概率率，可以先先求u值。。式中的T為為預(yù)定完工工時(shí)間16，E（T）=15，算得u=0.976。查正態(tài)態(tài)分布函數(shù)數(shù)表可知概概率為0.8355。即16周內(nèi)完工工的概率為83.55%.28§2統(tǒng)籌籌方法其正態(tài)分布布圖如圖12-16所示：16圖12-1629§2統(tǒng)籌籌方法四、網(wǎng)絡(luò)優(yōu)優(yōu)化得到初始的的計(jì)劃方案案，但通常常要對(duì)初始始方案進(jìn)行行調(diào)整與完完善。根據(jù)據(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ò)開(kāi)各工工序的開(kāi)始始時(shí)間。3）統(tǒng)籌兼兼顧工程進(jìn)進(jìn)度的要求求和現(xiàn)有資資源的限制制，多次綜綜合平衡。。下面列舉一一個(gè)拉平資資源需要量量最高峰的的實(shí)例。在在例5中，，若加工工工人為65人，，并假定這這些工人可可完成這5個(gè)工序任任一個(gè)，下下面來(lái)尋求求一個(gè)時(shí)間間-資源最優(yōu)方方案。如表表12-16所示：：30§2統(tǒng)籌籌方法表12-16工序需要人數(shù)最早開(kāi)始時(shí)間所需時(shí)間時(shí)差d5860200f22701847g428030h391001520i26110250若上述工序序都按最早早開(kāi)始時(shí)間間安排，那那么從第60天至第第135天天的75天天里，所需需的機(jī)械加加工工人人人數(shù)如圖12-17所示。31§2統(tǒng)籌籌方法在圖的上半半部中，工工序代號(hào)后后的數(shù)字是是人數(shù)，線線下面的數(shù)數(shù)字是非關(guān)關(guān)鍵工序時(shí)差長(zhǎng)長(zhǎng)度。圖的的下半部表表示從第60天至135天內(nèi)內(nèi)的75天天里，所需需機(jī)械加工工人數(shù)數(shù)，這樣的的圖稱(chēng)為資資源負(fù)荷圖圖。274635f(22人人）18h(39人人)1558人64人80人81人42人26人65人6080100120130d(58人人）i(26人人）g(42人人）302025圖12-1732§2統(tǒng)籌籌方法同時(shí)我們應(yīng)應(yīng)優(yōu)先安排排關(guān)鍵工序序所需的工工人，再利利用非關(guān)鍵鍵工序的時(shí)時(shí)差，錯(cuò)開(kāi)各各工序的開(kāi)開(kāi)始時(shí)間，，從而拉平平工人需要要量的高峰峰。經(jīng)過(guò)調(diào)調(diào)整，我們讓非關(guān)鍵鍵工序f從從第80天天開(kāi)始，工工序h從第第110天天開(kāi)始。找找到了時(shí)間間-資源優(yōu)化的方案案，如圖12-18所示，在在不增加工工人的情況況下保證了了工程按期期完成。246753f(22人人）h(39人人）d(58人人）i(26人人）g(42人人）工人數(shù)65人608010012013058人42人64人26人65人圖12-1833§2統(tǒng)籌籌方法2.時(shí)間-費(fèi)用優(yōu)化化需要考慮時(shí)時(shí)間與費(fèi)用用的問(wèn)題：：在既定的的時(shí)間前工工程完工的的前提下，，使得所需的費(fèi)費(fèi)用最少，，或者在不不超工程預(yù)預(yù)算的條件件下使工程程最早完工工。這些是時(shí)間-費(fèi)費(fèi)用優(yōu)化要要研究和解解決的問(wèn)題題。直接費(fèi)用：：為了加快快工程進(jìn)度度，需要增增加人力、、設(shè)備和工工作班次，，這需要增加一一筆費(fèi)用，，成為直接接費(fèi)用。間接費(fèi)用：：由于工程程早日完工工，減少了了管理人員員的工資辦辦公費(fèi)等費(fèi)費(fèi)用稱(chēng)為間接費(fèi)費(fèi)用。一般般說(shuō)工序越越短，直接接費(fèi)用越多多，間接費(fèi)費(fèi)用越少。。34§2統(tǒng)籌籌方法工序的最快快完成時(shí)間間：指完成成時(shí)間的最最高限度。。我們?cè)O(shè)完成成工序j的的正常所需需時(shí)間為T(mén)j;直接費(fèi)用用為cj;完成工序序j的最快快完成時(shí)間為T(mén)`j,直接費(fèi)用用為c`j。這樣我們們可以計(jì)算算出縮短工工序j的一一天工期所所增加的直直接費(fèi)用，用kj表示，稱(chēng)為為直接費(fèi)用用變動(dòng)率。。有時(shí)間--費(fèi)費(fèi)用優(yōu)化問(wèn)問(wèn)題可建立立兩個(gè)線性性規(guī)劃模型型。模型一，在在既定的時(shí)時(shí)間T完工工的前提下下，問(wèn)各工工序的完成成時(shí)間為多多少才使因因縮短工期而而增加的直直接費(fèi)用最最少。設(shè)工序（i,j)的提前完完工時(shí)間為為Yij,我們用Tij,T`ij分別表示正正常完工時(shí)時(shí)間與最快快完工的時(shí)間間，則有工工序（i,j)的的實(shí)際完工工時(shí)間為：：Tij-Yij。我們用Cij,C`ij表示用正常完工時(shí)間間和最快完完成時(shí)間完完成工序所所需要的費(fèi)費(fèi)用，Kij為工序（i,j)的直接費(fèi)費(fèi)用變動(dòng)率。得得到這個(gè)問(wèn)問(wèn)題的線性性規(guī)劃模型型如下：minf=（Kij*Yij)（i,j)j-XiTij-Y`ij,對(duì)一切弧?。╥,j)YijTij-T`ij,對(duì)對(duì)一切弧弧（i,j)Xn-X1T,Xi0，Yij0。35§2統(tǒng)籌籌方法例7.例例5所所提供的信信息都作為為本例的信信息，另外外還給出了了在裝配過(guò)過(guò)程中各道道工序所需需正常完工工時(shí)間與最最快完工時(shí)時(shí)間，以及及對(duì)應(yīng)正常常完工時(shí)間間與最快完完工時(shí)間的的所需的直直接費(fèi)用和和每縮短一一天工期所所需增加的的直接費(fèi)用用，如表12-17所示。表12-17工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接費(fèi)用直接費(fèi)用變動(dòng)率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-36§2統(tǒng)籌籌方法該工程要求求在150天內(nèi)完工工，問(wèn)每個(gè)個(gè)工序應(yīng)比比正常完工工時(shí)間提前前多少天完成，才能能使整個(gè)工工程因縮短短工期而增增加的直接接費(fèi)用為最最少。如果果工期要求在140天完工呢呢？12345678abfechgijd圖12-1937§2統(tǒng)籌籌方法解：繪出如如圖12-19所示示，根據(jù)此此網(wǎng)絡(luò)圖建建立數(shù)學(xué)模模型。設(shè)此網(wǎng)絡(luò)圖圖上第i點(diǎn)點(diǎn)發(fā)生的時(shí)時(shí)間為xi，工序提前前完工的時(shí)時(shí)間為yij。目標(biāo)函數(shù)minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.2-x160-y12,x7-x24