《管理運(yùn)籌學(xué)》第12章排序與統(tǒng)籌方法課件_第1頁(yè)
《管理運(yùn)籌學(xué)》第12章排序與統(tǒng)籌方法課件_第2頁(yè)
《管理運(yùn)籌學(xué)》第12章排序與統(tǒng)籌方法課件_第3頁(yè)
《管理運(yùn)籌學(xué)》第12章排序與統(tǒng)籌方法課件_第4頁(yè)
《管理運(yùn)籌學(xué)》第12章排序與統(tǒng)籌方法課件_第5頁(yè)
已閱讀5頁(yè),還剩37頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

應(yīng)該按照什么樣的加工順序來(lái)加工這六個(gè)零件,才能使得這六個(gè)零件在車間里停留的平均時(shí)間為最少?零件加工時(shí)間(小時(shí))零件加工時(shí)間(小時(shí))1231.82.00.54560.91.31.53§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題零件§1車間作業(yè)計(jì)劃模型

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

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時(shí)間,如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢?這就是我們最后要解決的優(yōu)化問(wèn)題,而且我們要設(shè)法找到一種簡(jiǎn)便的算法。對(duì)于某種加工順序,我們知道安排在第j位加工的零件在車間里總的停留時(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車間作業(yè)計(jì)劃模型例1解:如果我們用§1車間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件

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

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

同樣,下一個(gè)最短加工時(shí)間為1,這是車床加工零件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?!?車間作業(yè)計(jì)劃模型8同樣,下一個(gè)最短加工時(shí)間為1,這是車床加工§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ò)圖,也就是將工序(或稱為活動(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)籌方法統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)§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ù).

12453abcde601383815圖12-410§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表12453ab§2統(tǒng)籌方法

例4、把例3的工序進(jìn)度表做一些擴(kuò)充,如表12-9,請(qǐng)畫(huà)出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。

表12-9工序代號(hào)所需時(shí)間(天)緊前工序工序代號(hào)所需時(shí)間(天)緊前工序abcd60151338-aacefgh810165b,ddde,f,g11§2統(tǒng)籌方法例4、把例3的工序進(jìn)度表做一些擴(kuò)充,如表§2統(tǒng)籌方法

解:我們把工序f擴(kuò)充到圖12-4發(fā)生了問(wèn)題,由于d是f的緊前工序,故d的結(jié)束應(yīng)該是f的開(kāi)始,所以代表f的弧的起點(diǎn)應(yīng)該是④,由于工序b的結(jié)束也是④,所以工序b也成了工序f的緊前工序,與題意不符。為此我們?cè)O(shè)立虛工序。虛工序是實(shí)際上并不存在而虛設(shè)的工序,用來(lái)表示相鄰工序的銜接關(guān)系,不需要人力、物力等資源與時(shí)間。

152643a60b158e1013dc38f圖12-512§2統(tǒng)籌方法解:我們把工序f擴(kuò)充到圖12-§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加g、h工序得網(wǎng)絡(luò)圖12-6。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧,因此增加了一個(gè)點(diǎn)和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-613§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加g、h§2統(tǒng)籌方法在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí),要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-714§2統(tǒng)籌方法1257834a6015bec13d388h5§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線在繪制出網(wǎng)絡(luò)圖之后,我們可以由網(wǎng)絡(luò)圖求出:1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開(kāi)始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下,其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線,具體過(guò)程如表12-10,求:完成此工程的最少時(shí)間,關(guān)鍵路線及相應(yīng)的關(guān)鍵工序,各工序的最早開(kāi)始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下,其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。15§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線15§2統(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)籌方法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間(天)緊前§2統(tǒng)籌方法解:據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。圖12-8如圖12-8,①-②-③-⑦-⑧就是一條關(guān)鍵路線,我們要干完所有的工序就必須走完所有這樣的路線,由于很多工序可以同時(shí)進(jìn)行,所以網(wǎng)絡(luò)中最長(zhǎng)的路線就決定了完成整個(gè)工程所需的最少時(shí)間,這條路線稱為關(guān)鍵路線。12346785a60b45echj35ig1030d204025f181517§2統(tǒng)籌方法解:據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。1§2統(tǒng)籌方法下面我們給出找關(guān)鍵路線的辦法首先,從網(wǎng)絡(luò)的發(fā)點(diǎn)開(kāi)始,按順序計(jì)算出每個(gè)工序的最早開(kāi)始時(shí)間(ES)和最早結(jié)束時(shí)間(EF),設(shè)一個(gè)工序所需的時(shí)間為t,這對(duì)于同一個(gè)工序來(lái)說(shuō),有EF=ES+t。

工序a的最早開(kāi)始時(shí)間工序a的最早完成時(shí)間11a[0,60]60圖12-918§2統(tǒng)籌方法下面我們給出找關(guān)鍵路線的辦法工序a的最早工序a§2統(tǒng)籌方法

圖12-10其次,從網(wǎng)絡(luò)的收點(diǎn)開(kāi)始計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情況下各個(gè)工序的最晚開(kāi)始時(shí)間(縮寫(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)籌方法1236785a[0,60]60b[60,1§2統(tǒng)籌方法

運(yùn)用此法則,可以從首點(diǎn)開(kāi)始計(jì)算出每個(gè)工序的LF與LS,如圖12-11所示。

接著,可以計(jì)算出每一個(gè)工序的時(shí)差,把在不影響工程最早結(jié)束時(shí)間的條件下,工序最早開(kāi)始(或結(jié)束)的時(shí)間可以推遲的時(shí)間,成為該工序的時(shí)差,對(duì)每個(gè)工序來(lái)說(shuō)其時(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)籌方法運(yùn)用此法則,可以從首點(diǎn)開(kāi)始計(jì)算§2統(tǒng)籌方法

最后將各工序的時(shí)差,以及其他信息構(gòu)成工序時(shí)間表如表12-11所示。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。21§2統(tǒng)籌方法最后將各工序的時(shí)差,以及其他信息構(gòu)第十二章排序與統(tǒng)籌方法§1車間作業(yè)計(jì)劃模型§2統(tǒng)籌方法在本章中,我們將介紹車間作業(yè)計(jì)劃模型和統(tǒng)籌方法。這兩個(gè)問(wèn)題盡管處理的方法有所不同,但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工作時(shí),它們都將幫助我們應(yīng)該按照怎樣的次序、怎樣的時(shí)間表來(lái)做這些工作,使得效果最佳(例如完成全部工作所用時(shí)間最短或費(fèi)用最少等等)。22第十二章排序與統(tǒng)籌方法§1車間作業(yè)計(jì)劃模型§1車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題二、兩臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題23§1車間作業(yè)計(jì)劃模型2§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題例1.某車間只有一臺(tái)高精度的磨床,常常出現(xiàn)很多零件同時(shí)要求這臺(tái)磨床加工的情況,現(xiàn)有六個(gè)零件同時(shí)要求加工,這六個(gè)零件加工所需時(shí)間如下表所示。

應(yīng)該按照什么樣的加工順序來(lái)加工這六個(gè)零件,才能使得這六個(gè)零件在車間里停留的平均時(shí)間為最少?零件加工時(shí)間(小時(shí))零件加工時(shí)間(小時(shí))1231.82.00.54560.91.31.524§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題零件§1車間作業(yè)計(jì)劃模型

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

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時(shí)間,如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢?這就是我們最后要解決的優(yōu)化問(wèn)題,而且我們要設(shè)法找到一種簡(jiǎn)便的算法。對(duì)于某種加工順序,我們知道安排在第j位加工的零件在車間里總的停留時(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í)間為最少。25§1車間作業(yè)計(jì)劃模型例1解:如果我們用§1車間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件

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

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

同樣,下一個(gè)最短加工時(shí)間為1,這是車床加工零件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。§1車間作業(yè)計(jì)劃模型29同樣,下一個(gè)最短加工時(shí)間為1,這是車床加工§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ò)圖,也就是將工序(或稱為活動(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,d30§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)§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ù).

12453abcde601383815圖12-431§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表12453ab§2統(tǒng)籌方法

例4、把例3的工序進(jìn)度表做一些擴(kuò)充,如表12-9,請(qǐng)畫(huà)出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。

表12-9工序代號(hào)所需時(shí)間(天)緊前工序工序代號(hào)所需時(shí)間(天)緊前工序abcd60151338-aacefgh810165b,ddde,f,g32§2統(tǒng)籌方法例4、把例3的工序進(jìn)度表做一些擴(kuò)充,如表§2統(tǒng)籌方法

解:我們把工序f擴(kuò)充到圖12-4發(fā)生了問(wèn)題,由于d是f的緊前工序,故d的結(jié)束應(yīng)該是f的開(kāi)始,所以代表f的弧的起點(diǎn)應(yīng)該是④,由于工序b的結(jié)束也是④,所以工序b也成了工序f的緊前工序,與題意不符。為此我們?cè)O(shè)立虛工序。虛工序是實(shí)際上并不存在而虛設(shè)的工序,用來(lái)表示相鄰工序的銜接關(guān)系,不需要人力、物力等資源與時(shí)間。

152643a60b158e1013dc38f圖12-533§2統(tǒng)籌方法解:我們把工序f擴(kuò)充到圖12-§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加g、h工序得網(wǎng)絡(luò)圖12-6。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧,因此增加了一個(gè)點(diǎn)和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-634§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加g、h§2統(tǒng)籌方法在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí),要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-735§2統(tǒng)籌方法1257834a6015bec13d388h5§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線在繪制出網(wǎng)絡(luò)圖之后,我們可以由網(wǎng)絡(luò)圖求出:1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開(kāi)始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下,其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線,具體過(guò)程如表12-10,求:完成此工程的最少時(shí)間,關(guān)鍵路線及相應(yīng)的關(guān)鍵工序,各工序的最早開(kāi)始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下,其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。36§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線15§2統(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,h37§2統(tǒng)籌方法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間(天)緊前§2統(tǒng)籌方法解:據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。圖12-8如圖12-8,①-②-③-⑦-⑧就是一條關(guān)鍵路線,我們要干完所有的工序就必須走完所有這樣的路線,由于很多工序可以同時(shí)進(jìn)行,所以網(wǎng)絡(luò)中最長(zhǎng)的路線就決定了完成整個(gè)工程所需的最少時(shí)間,這條路線稱為關(guān)鍵路線。12346785a60b45echj35ig

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論