管理運(yùn)籌學(xué)-第12章 排序與統(tǒng)籌方法ppt課件

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第十二章第十二章 排序與統(tǒng)籌方法排序與統(tǒng)籌方法1 車間作業(yè)方案模型車間作業(yè)方案模型2 統(tǒng)籌方法統(tǒng)籌方法 在本章中，我們將引見車間作業(yè)方案模型和在本章中，我們將引見車間作業(yè)方案模型和統(tǒng)籌方法。這兩個問題雖然處置的方法有所不同，統(tǒng)籌方法。這兩個問題雖然處置的方法有所不同，但當(dāng)我們面臨必需完成假設(shè)干項(xiàng)不能同時進(jìn)展的但當(dāng)我們面臨必需完成假設(shè)干項(xiàng)不能同時進(jìn)展的任務(wù)時，它們都將協(xié)助我們應(yīng)該按照怎樣的次序、任務(wù)時，它們都將協(xié)助我們應(yīng)該按照怎樣的次序、怎樣的時間表來做這些任務(wù)，使得效果最正確怎樣的時間表來做這些任務(wù)，使得效果最正確例如完成全部任務(wù)所用時間

2、最短或費(fèi)用最少等例如完成全部任務(wù)所用時間最短或費(fèi)用最少等等。等。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 1 1車間作業(yè)方案模型車間作業(yè)方案模型車間作業(yè)方案是指一個工廠消費(fèi)工序的方案和安排。車間作業(yè)方案是指一個工廠消費(fèi)工序的方案和安排。一、一臺機(jī)器、一、一臺機(jī)器、n個零件的排序問題個零件的排序問題二、兩臺機(jī)器、二、兩臺機(jī)器、n個零件的排序問題個零件的排序問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 1 1車間作業(yè)方案模型車間作業(yè)方案模型一、一臺機(jī)器、一、一臺機(jī)器、n n個零件的排序問題個零件的排序問題 例例1.1.某車間只需一臺高精度的磨床，經(jīng)常出現(xiàn)很多某車間只

3、需一臺高精度的磨床，經(jīng)常出現(xiàn)很多零件同時要求這臺零件同時要求這臺磨床加工的情況，現(xiàn)有六個零件同時要求加工，這六個零件磨床加工的情況，現(xiàn)有六個零件同時要求加工，這六個零件加工所需時間加工所需時間如下表所示。如下表所示。 應(yīng)該按照什么樣的加工順序來加工這六個零件，才應(yīng)該按照什么樣的加工順序來加工這六個零件，才干使得這六個零干使得這六個零件在車間里停留的平均時間為最少？件在車間里停留的平均時間為最少？零件零件加工時間加工時間（小時）（小時）零件零件加工時間加工時間（小時）（小時）1231.82.00.54560.91.31.5管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 1 1車間作業(yè)方

4、案模型車間作業(yè)方案模型 jiiP1jiiP1623456654321pppppP 例例1解：假設(shè)我們用解：假設(shè)我們用Pi表示安排在第表示安排在第i位加工的零件所需的時間，用位加工的零件所需的時間，用Tj表表示安排在第示安排在第j位加工的零件在車間里總的停留時間，那么有位加工的零件在車間里總的停留時間，那么有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？這就是我們最后要處理的優(yōu)化問得各零件的平均停留時間最少的排序呢？這就是我們最后要

5、處理的優(yōu)化問題，而且我們要設(shè)法找到一種簡便的算法。題，而且我們要設(shè)法找到一種簡便的算法。 對于某種加工順序，我們知道安排在第對于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停位加工的零件在車間里總的停留時間為留時間為Tj ， Tj = 可知這六個零件的停留時間為：可知這六個零件的停留時間為： 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 ) 6

6、 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各個零件平均停留時間為那么各個零件平均停留時間為 從上式可知，對于一臺機(jī)器從上式可知，對于一臺機(jī)器n個零件的排序問題，只需系數(shù)越大，配上個零件的排序問題，只需系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。間為最少。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 1 1車間作業(yè)方案模

7、型車間作業(yè)方案模型二、兩臺機(jī)器、二、兩臺機(jī)器、n n個零件個零件 例例2.2.某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在再在磨床上加工，每臺機(jī)器上各零件加工時間如表磨床上加工，每臺機(jī)器上各零件加工時間如表12-512-5所示。所示。表表12-512-5 應(yīng)該如何安排這五個零件的先后順序才干使完成這五個零件的總的加工應(yīng)該如何安排這五個零件的先后順序才干使完成這五個零件的總的加工時間為時間為最少？最少？ 解：由于每個零件必需先進(jìn)展車床加工，再進(jìn)展磨床加工，所以在車床解：由于每個零件必需先進(jìn)展車床加工，再進(jìn)展磨床加工，

8、所以在車床上加上加工零件的順序與在磨床上加工零件的順序是一樣的。工零件的順序與在磨床上加工零件的順序是一樣的。 假設(shè)這些零件在車床上和磨床上加工順序都為假設(shè)這些零件在車床上和磨床上加工順序都為1 1，2 2，3 3，4 4，5 5。我們用圖。我們用圖12-112-1中的線條圖來表示各零件加工的開場時間與完成時間，這種圖是由一根時間軸和中的線條圖來表示各零件加工的開場時間與完成時間，這種圖是由一根時間軸和車床、磨床在每個時間段的情況的圖形所構(gòu)成。車床、磨床在每個時間段的情況的圖形所構(gòu)成。零件零件車床車床磨床磨床零件零件車床車床磨床磨床1231.52.01.00.50.251.75451.250.

9、752.51.25管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 1 1車間作業(yè)方案模型車間作業(yè)方案模型 圖圖 12-1 從上圖中我們可以看出，加工時間的延伸主要是由于磨床的停工待料從上圖中我們可以看出，加工時間的延伸主要是由于磨床的停工待料呵斥的，只需減少磨床的停工待料的時間就能減少整個加工義務(wù)的總時間。呵斥的，只需減少磨床的停工待料的時間就能減少整個加工義務(wù)的總時間。為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時間越短的零為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時間越短的零件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的件越早加工，減少磨床等待

10、的時間；另一方面把在磨床上加工時間越長的零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件加工義務(wù)所需總時間最少的零件排序方法。零件加工義務(wù)所需總時間最少的零件排序方法。123451車床車床磨床磨床2345010管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1車間作業(yè)方案模型車間作業(yè)方案模型 尋覓例尋覓例2的最優(yōu)解：我們在表的最優(yōu)解：我們在表12-5中找到所列出的最短加工時間是中找到所列出的最短加工時間是0.25,它是第二道工序磨床它是第二道工序磨床加工零件加工零件2的所需時間，由于這個時間與磨床有

11、關(guān)，故我們把零件的所需時間，由于這個時間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第放在加工順序的末尾，即第五五位，并在表中劃去零件位，并在表中劃去零件2 所在行。如表所在行。如表12-6中紅色線條所示。中紅色線條所示。 接著，我們又找到最短加工時間為接著，我們又找到最短加工時間為0.5，這一時間與磨床第二工序有關(guān)，我們把，這一時間與磨床第二工序有關(guān)，我們把 磨床加磨床加工時間為工時間為0.5的零件的零件1放到除第五外的加工順序的末尾，即第四位加工，同時把放到除第五外的加工順序的末尾，即第四位加工，同時把 表中的零件表中的零件1所在所在的行劃去。如表的行劃去。如表12-6中黃色線條所示。

12、中黃色線條所示。 下一個最短加工時間為下一個最短加工時間為0.75，這個加工時間是車床第一工序加工零件，這個加工時間是車床第一工序加工零件5的所需時間，故的所需時間，故把零件把零件5排在加工順序的第一位上，同時把表中的零件排在加工順序的第一位上，同時把表中的零件5所在的行劃去。如表所在的行劃去。如表12-6中藍(lán)色線條所中藍(lán)色線條所示。示。零件零件車床車床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）零件零件車床車床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表表12-6管管 理理 運(yùn)運(yùn) 籌籌

13、學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 同樣，下一個最短加工時間為同樣，下一個最短加工時間為1，這是車床加工零件，這是車床加工零件3的所需時間，故的所需時間，故把零件把零件3排在第二位上，同時把零件排在第二位上，同時把零件3所在的行劃去。如表所在的行劃去。如表12-6中黑色線條中黑色線條所示。所示。 這樣就得到了最優(yōu)加工順序：這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需。一共只需7個小時就能個小時就能完成全部加工。完成全部加工。 從例從例2中我們可以歸納出關(guān)于兩臺機(jī)器中我們可以歸納出關(guān)于兩臺機(jī)器n個零件的排序問題，使得全部個零件的排序問題，使得全部義務(wù)總的時間義務(wù)總的時間 最短的排序算法。

14、最短的排序算法。 在加工所需時間表上選出最短加工時間在加工所需時間表上選出最短加工時間tij，這是第，這是第i工序加工工序加工j零件所需零件所需時間，當(dāng)時間，當(dāng)i=1時，將零件時，將零件j的順序盡量靠前，假設(shè)的順序盡量靠前，假設(shè)i=2時，將零件時，將零件j的順序盡量的順序盡量靠后。在表上劃去零件靠后。在表上劃去零件j的所在行，回到步驟的所在行，回到步驟1。 1 1車間作業(yè)方案模型車間作業(yè)方案模型管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法 統(tǒng)籌方法包括繪制方案網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)統(tǒng)籌方法包括繪制方案網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)行

15、分別討論：行分別討論：一、方案網(wǎng)絡(luò)圖一、方案網(wǎng)絡(luò)圖 統(tǒng)籌方法的第一步任務(wù)就是繪制方案網(wǎng)絡(luò)圖，也就是將工序或稱為統(tǒng)籌方法的第一步任務(wù)就是繪制方案網(wǎng)絡(luò)圖，也就是將工序或稱為活動進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。活動進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。 例例3、某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互、某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表關(guān)系都顯示在其工序進(jìn)度表如表12-8所示，請畫出其統(tǒng)籌方法網(wǎng)絡(luò)圖。所示，請畫出其統(tǒng)籌方法網(wǎng)絡(luò)圖。 表表12-8工序代號工序代號工序內(nèi)容工序內(nèi)容所需時間（天所需時間（天)緊前工序緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)產(chǎn)品

16、設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購配套零件外購生產(chǎn)原料外購生產(chǎn)原料自制主件自制主件主配可靠性試驗(yàn)主配可靠性試驗(yàn)601513388-aacb,d管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法解解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表 網(wǎng)絡(luò)圖中的點(diǎn)表示一個事件網(wǎng)絡(luò)圖中的點(diǎn)表示一個事件,是一個或假設(shè)干個工序的開場或終了是一個或假設(shè)干個工序的開場或終了,是是相相鄰工序在時間上的分界點(diǎn)鄰工序在時間上的分界點(diǎn),點(diǎn)用圓圈表示點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號。弧圓圈里的數(shù)字表示點(diǎn)的編號。弧表示一個工序或活動，弧的方向是從工序開場指向工序的終了，弧上表示一個

17、工序或活動，弧的方向是從工序開場指向工序的終了，弧上是各工序的代號，下面標(biāo)以完成此工序所需的時間或資源等數(shù)據(jù)，即是各工序的代號，下面標(biāo)以完成此工序所需的時間或資源等數(shù)據(jù)，即為對此弧所賦的權(quán)數(shù)為對此弧所賦的權(quán)數(shù) abcde601383815圖圖12-4管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法 例、把例的工序進(jìn)度表做一些擴(kuò)展，如例、把例的工序進(jìn)度表做一些擴(kuò)展，如表表12-9，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。 表表12-9工序代號工序代號所需時間（天）所需時間（天）緊前工序緊前工序工序代號工序代號所需時間（天）所需時間（天）緊前工序緊前工序

18、abcd60151338aacefgh810165b，dde，管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法 解：我們把工序擴(kuò)展到圖解：我們把工序擴(kuò)展到圖12-4發(fā)生了問發(fā)生了問題，由于是的緊前工序，故的終了應(yīng)題，由于是的緊前工序，故的終了應(yīng)該是的開場，所以代表的弧的起點(diǎn)應(yīng)該該是的開場，所以代表的弧的起點(diǎn)應(yīng)該是，由于工序的終了也是，所以工序是，由于工序的終了也是，所以工序也成了工序的緊前工序，與題意不符。也成了工序的緊前工序，與題意不符。 為此我們設(shè)立虛工序。虛工序是實(shí)踐為此我們設(shè)立虛工序。虛工序是實(shí)踐上并不存在而虛設(shè)的工序，用來表示相鄰工上并不存在而虛設(shè)的工序

19、，用來表示相鄰工序的銜接關(guān)系，不需求人力、物力等資源與序的銜接關(guān)系，不需求人力、物力等資源與時間。時間。 152643a60b158e1013dc38f圖圖12-5管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法 在網(wǎng)絡(luò)圖上添加、工序得網(wǎng)絡(luò)圖在網(wǎng)絡(luò)圖上添加、工序得網(wǎng)絡(luò)圖12-6。 在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點(diǎn)之間多于一條弧，在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點(diǎn)之間多于一條弧，因此添加了一個點(diǎn)和虛工序如圖因此添加了一個點(diǎn)和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖圖12-6管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)

20、2 2統(tǒng)籌方法統(tǒng)籌方法 在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要留意圖中不能有缺口和回在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要留意圖中不能有缺口和回路。路。1257834a6015bec13d388h510f616g圖圖12-7管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法二、網(wǎng)絡(luò)時間與關(guān)鍵道路二、網(wǎng)絡(luò)時間與關(guān)鍵道路 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程工程所需的最少時間。、完成此工程工程所需的最少時間。2、每個工序的開場時間與終了時間。、每個工序的開場時間與終了時間。3、關(guān)鍵道路及其運(yùn)用的關(guān)鍵工序。、關(guān)鍵道路及其運(yùn)用的關(guān)鍵

21、工序。4、非關(guān)鍵工序在不影響工程的完成時間的前提下，其開場時間與終了時、非關(guān)鍵工序在不影響工程的完成時間的前提下，其開場時間與終了時間可以推遲多久。間可以推遲多久。 例例5、某公司裝配一條新的消費(fèi)線，詳細(xì)過程如表、某公司裝配一條新的消費(fèi)線，詳細(xì)過程如表12-10,求：完成此求：完成此工程的最少時間，關(guān)鍵道路及相應(yīng)的關(guān)鍵工序，各工序的最早開場時間和工程的最少時間，關(guān)鍵道路及相應(yīng)的關(guān)鍵工序，各工序的最早開場時間和非關(guān)鍵工序在不影響工程完成時間的前提下，其開場時間與終了時間可以非關(guān)鍵工序在不影響工程完成時間的前提下，其開場時間與終了時間可以推遲多久。推遲多久。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理

22、運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法表表12-10工序代號工序代號工序內(nèi)容工序內(nèi)容所需時間（天）所需時間（天）緊前工序緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)生產(chǎn)線設(shè)計(jì)外購零配件外購零配件下料、鍛件下料、鍛件工裝制造工裝制造1木模、鑄件木模、鑄件機(jī)械加工機(jī)械加工1工裝制造工裝制造2機(jī)械加工機(jī)械加工2機(jī)械加工機(jī)械加工3裝配調(diào)試裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法解：據(jù)表解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖繪制網(wǎng)絡(luò)圖如圖12-8。 圖圖12-8 如圖如圖12-8 ,-就是一條

23、關(guān)鍵道路，我們要干完一切的工序就是一條關(guān)鍵道路，我們要干完一切的工序就必需走完一切這樣的道路，由于很多工序可以同時進(jìn)展，所以網(wǎng)絡(luò)中最就必需走完一切這樣的道路，由于很多工序可以同時進(jìn)展，所以網(wǎng)絡(luò)中最長的道路就決議了完成整個工程所需的最少時間，這條道路稱為關(guān)鍵路長的道路就決議了完成整個工程所需的最少時間，這條道路稱為關(guān)鍵路線。線。12346785a60b45echj35ig1030d204025f1815管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法下面我們給出找關(guān)鍵道路的方法下面我們給出找關(guān)鍵道路的方法 首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開場，按順序計(jì)算出每個工序的最早開場時首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開場，按順序計(jì)算出每個工序的最早開場時間間ES )和最早終了時間和最早終了時間EF) ，設(shè)一個工序所需的時間為，設(shè)一個工序所需的時間為t，這對于同，這對于同一一個工序來說，有個工序來說，有 EF=ES+t。 工序工序a的最早的最早開場時間開場時間工序工序a的最早的最早完成時間完成時間11a0，6060圖圖12-9管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2統(tǒng)籌方法統(tǒng)籌方法 圖圖12-10 其次其次,從網(wǎng)絡(luò)的收點(diǎn)開場計(jì)算出在不影響整個工程最早終了時間