第12章排序與統(tǒng)籌方法分析

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 1 第十二章第十二章 排序與統(tǒng)籌方法排序與統(tǒng)籌方法 第一節(jié)第一節(jié) 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 第二節(jié)第二節(jié) 統(tǒng)籌方法統(tǒng)籌方法 在本章中，我們將介紹車間作業(yè)計(jì)劃模型和在本章中，我們將介紹車間作業(yè)計(jì)劃模型和 統(tǒng)籌方法。這兩個(gè)問題盡管處理的方法有所不同，統(tǒng)籌方法。這兩個(gè)問題盡管處理的方法有所不同， 但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工 作時(shí)，它們都將幫助我們應(yīng)該按照怎樣的次序、作時(shí)，它們都將幫助我們應(yīng)該按照怎樣的次序、 怎樣的時(shí)間表來做這些工作，使得效果最佳（例怎樣的時(shí)間表來做這些工作，使

2、得效果最佳（例 如完成全部工作所用時(shí)間最短或費(fèi)用最少等等）。如完成全部工作所用時(shí)間最短或費(fèi)用最少等等）。 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 2 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 車間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。車間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。 一、一臺(tái)機(jī)器、一、一臺(tái)機(jī)器、n個(gè)零件的排序問題個(gè)零件的排序問題 二、兩臺(tái)機(jī)器、二、兩臺(tái)機(jī)器、n個(gè)零件的排序問題個(gè)零件的排序問題 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 3 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 一、一臺(tái)機(jī)器、一、一臺(tái)機(jī)器、n n個(gè)零件的排序問題個(gè)零件的排序問

3、題 例例1.某車間只有一臺(tái)高精度的磨床，常常出現(xiàn)很多零件同時(shí)要求這臺(tái)某車間只有一臺(tái)高精度的磨床，常常出現(xiàn)很多零件同時(shí)要求這臺(tái) 磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間 如下表所示。如下表所示。 應(yīng)該按照什么樣的加工順序來加工這六個(gè)零件，才能使得這六個(gè)零應(yīng)該按照什么樣的加工順序來加工這六個(gè)零件，才能使得這六個(gè)零 件在車間里停留的平均時(shí)間為最少？件在車間里停留的平均時(shí)間為最少？ 零件零件加工時(shí)間加工時(shí)間 （小時(shí)）（小時(shí)） 零件零件加工時(shí)間加工時(shí)間 （小時(shí)）（小時(shí)） 1 2 3 1.8 2.0 0.5 4 5 6

4、 0.9 1.3 1.5 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 4 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 j i iP 1 j i iP 1 6 23456654321pppppP 例例1解：如果我們用解：如果我們用Pi表示安排在第表示安排在第i位加工的零件所需的時(shí)間，用位加工的零件所需的時(shí)間，用Tj表示安排表示安排 在第在第j位加工的零件在車間里總的停留時(shí)間，則有位加工的零件在車間里總的停留時(shí)間，則有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工順序得到不同的各零件的平均停留時(shí)間，如何得到一個(gè)使得各零件不同的加工順序得到不同的各零件的平均停留時(shí)間，

5、如何得到一個(gè)使得各零件 的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設(shè)的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設(shè) 法找到一種簡便的算法。法找到一種簡便的算法。 對于某種加工順序，我們知道安排在第對于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停留時(shí)間為位加工的零件在車間里總的停留時(shí)間為 Tj ， Tj = 可知這六個(gè)零件的停留時(shí)間為：可知這六個(gè)零件的停留時(shí)間為： T1 + T2 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4

6、 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各個(gè)零件平均停留時(shí)間為那么各個(gè)零件平均停留時(shí)間為 從上式可知，對于一臺(tái)機(jī)器從上式可知，對于一臺(tái)機(jī)器n個(gè)零件的排序問題，只要系數(shù)越大，配上加工時(shí)個(gè)零件的排序問題，只要系數(shù)越大，配上加工時(shí) 間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，加工間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，加工 時(shí)間越多的零件排在越后面，可使各個(gè)零件的平均停留時(shí)間為最少。時(shí)間越

7、多的零件排在越后面，可使各個(gè)零件的平均停留時(shí)間為最少。 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 5 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 二、兩臺(tái)機(jī)器、二、兩臺(tái)機(jī)器、n n個(gè)零件個(gè)零件 例例2.某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在 磨床上加工，每臺(tái)機(jī)器上各零件加工時(shí)間如表磨床上加工，每臺(tái)機(jī)器上各零件加工時(shí)間如表12-5所示。所示。 表表12-5 應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間 為為

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

9、零件零件車床車床磨床磨床零件零件車床車床磨床磨床 1 2 3 1.5 2.0 1.0 0.5 0.25 1.75 4 5 1.25 0.75 2.5 1.25 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 6 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 圖圖 12-1 從上圖中我們可以看出，加工時(shí)間的延長主要是由于磨床的停工待料從上圖中我們可以看出，加工時(shí)間的延長主要是由于磨床的停工待料 造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。 為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時(shí)間越短的零

10、為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時(shí)間越短的零 件越早加工，減少磨床等待的時(shí)間；另一方面把在磨床上加工時(shí)間越長的件越早加工，減少磨床等待的時(shí)間；另一方面把在磨床上加工時(shí)間越長的 零件越晚加工，以便充分利用前面的時(shí)間，這樣我們就得到了使完成全部零件越晚加工，以便充分利用前面的時(shí)間，這樣我們就得到了使完成全部 零件加工任務(wù)所需總時(shí)間最少的零件排序方法。零件加工任務(wù)所需總時(shí)間最少的零件排序方法。 12345 1 車床車床 磨床磨床 2 345 010 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 7 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 尋找例尋找例2的最優(yōu)解：我們

11、在表的最優(yōu)解：我們在表12-5中找到所列出的最短加工時(shí)間是中找到所列出的最短加工時(shí)間是0.25,它是第二道工序磨床它是第二道工序磨床 加工零件加工零件2的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五放在加工順序的末尾，即第五 位，并在表中劃去零件位，并在表中劃去零件2 所在行。如表所在行。如表12-6中紅色線條所示。中紅色線條所示。 接著，我們又找到最短加工時(shí)間為接著，我們又找到最短加工時(shí)間為0.5，這一時(shí)間與磨床（第二工序）有關(guān)，我們把，這一時(shí)間與磨床（第二工序）有關(guān)，我們把 磨床加磨床加 工時(shí)間為工時(shí)間為0.5的

12、零件的零件1放到除第五外的加工順序的末尾，即第四位加工，同時(shí)把放到除第五外的加工順序的末尾，即第四位加工，同時(shí)把 表中的零件表中的零件1所在所在 的行劃去。如表的行劃去。如表12-6中黃色線條所示。中黃色線條所示。 下一個(gè)最短加工時(shí)間為下一個(gè)最短加工時(shí)間為0.75，這個(gè)加工時(shí)間是車床（第一工序）加工零件，這個(gè)加工時(shí)間是車床（第一工序）加工零件5的所需時(shí)間，故的所需時(shí)間，故 把零件把零件5排在加工順序的第一位上，同時(shí)把表中的零件排在加工順序的第一位上，同時(shí)把表中的零件5所在的行劃去。如表所在的行劃去。如表12-6中藍(lán)色線條所中藍(lán)色線條所 示。示。 零件零件車床車床 （第一工序）（第一工序） 磨床

13、磨床 （第二工序）（第二工序） 零件零件車床車床 （第一工序）（第一工序） 磨床磨床 （第二工序）（第二工序） 1 2 3 1.5 2.0 1.0 0.5 0.25 1.75 4 5 1.25 0.75 2.5 1.25 表表12-6 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 8 同樣，下一個(gè)最短加工時(shí)間為同樣，下一個(gè)最短加工時(shí)間為1，這是車床加工零件，這是車床加工零件3的所需時(shí)間，故的所需時(shí)間，故 把零件把零件3排在第二位上，同時(shí)把零件排在第二位上，同時(shí)把零件3所在的行劃去。如表所在的行劃去。如表12-6中黑色線條中黑色線條 所示。所示。 這樣就得到了最優(yōu)加工順序：這樣就得到

14、了最優(yōu)加工順序：5，3，4，1，2。一共只需。一共只需7個(gè)小時(shí)就能個(gè)小時(shí)就能 完成全部加工。完成全部加工。 從例從例2中我們可以歸納出關(guān)于兩臺(tái)機(jī)器中我們可以歸納出關(guān)于兩臺(tái)機(jī)器n個(gè)零件的排序問題，使得全部個(gè)零件的排序問題，使得全部 任務(wù)總的時(shí)間任務(wù)總的時(shí)間 最短的排序算法。最短的排序算法。 在加工所需時(shí)間表上選出最短加工時(shí)間在加工所需時(shí)間表上選出最短加工時(shí)間tij，這是第，這是第i工序加工工序加工j零件所需零件所需 時(shí)間，當(dāng)時(shí)間，當(dāng)i=1時(shí)，將零件時(shí)，將零件j的順序盡量靠前，若的順序盡量靠前，若i=2時(shí)，將零件時(shí)，將零件j的順序盡量的順序盡量 靠后。在表上劃去零件靠后。在表上劃去零件j的所在行，

15、回到步驟的所在行，回到步驟1。 1 1 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃模型 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 9 2 2 統(tǒng)籌方法統(tǒng)籌方法 統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn) 行分別討論：行分別討論： 一、計(jì)劃網(wǎng)絡(luò)圖一、計(jì)劃網(wǎng)絡(luò)圖 統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為 活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。 例例3、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互、

16、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互 關(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)容所需時(shí)間（天所需時(shí)間（天)緊前工序緊前工序 a b c d e 產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì) 外購配套零件外購配套零件 外購生產(chǎn)原料外購生產(chǎn)原料 自制主件自制主件 主配可靠性試驗(yàn)主配可靠性試驗(yàn) 60 15 13 38 8 - a a c b,d 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 10 2 2 統(tǒng)籌方法統(tǒng)籌方法 解解:用網(wǎng)絡(luò)圖表示上述的工序

17、進(jìn)度表用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表 網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開始或結(jié)束是一個(gè)或若干個(gè)工序的開始或結(jié)束,是相是相 鄰工序在時(shí)間上的分界點(diǎn)鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號?；A圈里的數(shù)字表示點(diǎn)的編號?；?表示一個(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上表示一個(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上 是各工序的代號，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即是各工序的代號，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即 為對此弧所賦的權(quán)數(shù)為對此弧所賦的權(quán)數(shù) ab cd e

18、 60 13 8 38 15 圖圖12-4 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 11 2 2 統(tǒng)籌方法統(tǒng)籌方法 例、把例的工序進(jìn)度表做一些擴(kuò)充，如表例、把例的工序進(jìn)度表做一些擴(kuò)充，如表12-9，請畫出其統(tǒng)籌方法，請畫出其統(tǒng)籌方法 的網(wǎng)絡(luò)圖。的網(wǎng)絡(luò)圖。 表表12-9 工序代號工序代號所需時(shí)間（天）所需時(shí)間（天）緊前工序緊前工序工序代號工序代號所需時(shí)間（天）所需時(shí)間（天）緊前工序緊前工序 a b c d 60 15 13 38 a a c e f g h 8 10 16 5 b， d d e， 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 12 2 2 統(tǒng)籌方法統(tǒng)

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

20、60 b 15 8 e 10 13 d c 38 f 圖圖12-5 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 13 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ò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加 了一個(gè)點(diǎn)和虛工序如圖了一個(gè)點(diǎn)和虛工序如圖12-7。 1 25 6 7 34 a 6015 b e c 13 d 38 8h 5 10 f g 16 圖圖12-6 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 14 2 2 統(tǒng)籌方法統(tǒng)籌方法 在繪制統(tǒng)

21、籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。 1 25 7 8 34 a 6015 b e c 13 d 38 8h 5 10 f 6 16 g 圖圖12-7 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 15 2 2 統(tǒng)籌方法統(tǒng)籌方法 二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出： 1、完成此工程項(xiàng)目所需的最少時(shí)間。、完成此工程項(xiàng)目所需的最少時(shí)間。 2、每個(gè)工序的開始時(shí)間與結(jié)束時(shí)間。、每個(gè)工序的開始時(shí)間與結(jié)束時(shí)間。 3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工

22、序。、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。 4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí) 間可以推遲多久。間可以推遲多久。 例例5、某公司裝配一條新的生產(chǎn)線，具體過程如表、某公司裝配一條新的生產(chǎn)線，具體過程如表12-10,求：完成此求：完成此 工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時(shí)間和工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時(shí)間和 非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以 推遲多久。推遲多久。

23、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 16 2 2 統(tǒng)籌方法統(tǒng)籌方法 表表12-10 工序代號工序代號工序內(nèi)容工序內(nèi)容所需時(shí)間（天）所需時(shí)間（天）緊前工序緊前工序 a b c d e f g h i j 生產(chǎn)線設(shè)計(jì)生產(chǎn)線設(shè)計(jì) 外購零配件外購零配件 下料、鍛件下料、鍛件 工裝制造工裝制造1 木模、鑄件木模、鑄件 機(jī)械加工機(jī)械加工1 工裝制造工裝制造2 機(jī)械加工機(jī)械加工2 機(jī)械加工機(jī)械加工3 裝配調(diào)試裝配調(diào)試 60 45 10 20 40 18 30 15 25 35 / a a a a c d d,e g b,i,f,h 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分

24、析 17 2 2 統(tǒng)籌方法統(tǒng)籌方法 解：據(jù)表解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖繪制網(wǎng)絡(luò)圖如圖12-8。 圖圖12-8 如圖如圖12-8 ,-就是一條關(guān)鍵路線，我們要干完所有的工序就是一條關(guān)鍵路線，我們要干完所有的工序 就必須走完所有這樣的路線，由于很多工序可以同時(shí)進(jìn)行，所以網(wǎng)絡(luò)中最就必須走完所有這樣的路線，由于很多工序可以同時(shí)進(jìn)行，所以網(wǎng)絡(luò)中最 長的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路長的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路 線。線。 12 3 46 78 5 a 60 b 45 e c h j 35 ig 10 30 d 20 40 25 f 18

25、 15 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 18 2 2 統(tǒng)籌方法統(tǒng)籌方法 下面我們給出找關(guān)鍵路線的辦法下面我們給出找關(guān)鍵路線的辦法 首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個(gè)工序的最早開始時(shí)間首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個(gè)工序的最早開始時(shí)間 （ES )和最早結(jié)束時(shí)間（和最早結(jié)束時(shí)間（EF) ，設(shè)一個(gè)工序所需的時(shí)間為，設(shè)一個(gè)工序所需的時(shí)間為t，這對于同一，這對于同一 個(gè)工序來說，有個(gè)工序來說，有 EF=ES+t。 工序工序a的最早的最早 開始時(shí)間開始時(shí)間 工序工序a的最早的最早 完成時(shí)間完成時(shí)間 11 a0，60 60 圖圖12-9 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)

26、第12章排序與統(tǒng)籌方法分析 19 2 2 統(tǒng)籌方法統(tǒng)籌方法 圖圖12-10 其次其次,從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情 況下各個(gè)工序的最晚開始時(shí)間況下各個(gè)工序的最晚開始時(shí)間(縮寫為縮寫為LS)和最晚結(jié)束時(shí)間（縮寫為和最晚結(jié)束時(shí)間（縮寫為LF), 顯然對同一工序有顯然對同一工序有 LS=LF-t 12 3 6 78 5 a0,60 60 b60,105 45 e60.100 c60,70 h100,115 j135,170 35 i110.135g80,110 30 d60.80 20 40 25 f70,88 18 4

27、 10 15 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 20 2 2 統(tǒng)籌方法統(tǒng)籌方法 運(yùn)用此法則，可以從首點(diǎn)開始計(jì)算出每個(gè)工序的運(yùn)用此法則，可以從首點(diǎn)開始計(jì)算出每個(gè)工序的LF與與LS，如圖，如圖12-11 所示。所示。 接著，可以計(jì)算出每一個(gè)工序的時(shí)差，把在不影響工程最早結(jié)束時(shí)間接著，可以計(jì)算出每一個(gè)工序的時(shí)差，把在不影響工程最早結(jié)束時(shí)間 的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序 的時(shí)差，對每個(gè)工序來說其時(shí)差記為的時(shí)差，對每個(gè)工序來說其時(shí)差記為Ts有有 Ts=LS-ES=LF-EF 12

28、3 6 78 5 a0,60 600,60 b60,105 4590,135 e60.100 c60,70 h100,115 j135,170 35135,170 i110.135g80,110 3080,110 d60.80 2060,80 4080,120 25110,135 f70,88 18117,135 4 10107,117 15120,135 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 21 2 2 統(tǒng)籌方法統(tǒng)籌方法 最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表12-11所所 示。示。 這樣就找到了一條由關(guān)鍵工

29、序這樣就找到了一條由關(guān)鍵工序a,d,g,i和和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的依次連接成的從發(fā)點(diǎn)到收點(diǎn)的 關(guān)鍵路線。關(guān)鍵路線。 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 22 三、完成工序所需時(shí)間與關(guān)鍵路線三、完成工序所需時(shí)間與關(guān)鍵路線 當(dāng)完成工序所需時(shí)間不確定的情況下如何求網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線？當(dāng)完成工序所需時(shí)間不確定的情況下如何求網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線？ 例例6. 長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn)，長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn)， 培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項(xiàng)活動(dòng)的信息如表培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項(xiàng)活動(dòng)的信息如表12-12所示，要求繪制

30、所示，要求繪制 出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線，并確定開始這個(gè)組出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線，并確定開始這個(gè)組 織工作的時(shí)間以保證培訓(xùn)工作如期舉行。織工作的時(shí)間以保證培訓(xùn)工作如期舉行。 解：由表解：由表12-12，繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖如圖，繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖如圖12-12所示。所示。 1 2 3 5 6 487 a b e c d f g h i 圖圖12-12 2 2 統(tǒng)籌方法統(tǒng)籌方法 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 23 2 2 統(tǒng)籌方法統(tǒng)籌方法 活動(dòng)（工序）活動(dòng)（工序）活動(dòng)（工序）內(nèi)容活動(dòng)（工序）內(nèi)容緊前活動(dòng)緊前活動(dòng) （工序）

31、（工序） a b c d e f g h i 制定培訓(xùn)計(jì)劃制定培訓(xùn)計(jì)劃 選聘培訓(xùn)教師選聘培訓(xùn)教師 列出一些可供選擇的培訓(xùn)地點(diǎn)列出一些可供選擇的培訓(xùn)地點(diǎn) 確定培訓(xùn)地點(diǎn)確定培訓(xùn)地點(diǎn) 確定培訓(xùn)的日程安排確定培訓(xùn)的日程安排 落實(shí)教學(xué)設(shè)備，器材，資料落實(shí)教學(xué)設(shè)備，器材，資料 發(fā)培訓(xùn)通知并確定學(xué)員名單發(fā)培訓(xùn)通知并確定學(xué)員名單 訂旅館房間訂旅館房間 處理最后的一些事務(wù)處理最后的一些事務(wù) - a - c b,d e b,d g f,g 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 24 2 2 統(tǒng)籌方法統(tǒng)籌方法 由于是第一次搞培訓(xùn)，缺乏統(tǒng)計(jì)來確定完成每個(gè)活動(dòng)所需時(shí)間，由于是第一次搞培訓(xùn)，缺乏統(tǒng)計(jì)來

32、確定完成每個(gè)活動(dòng)所需時(shí)間， 但對所需時(shí)間做了三種估計(jì)：但對所需時(shí)間做了三種估計(jì)： 1.樂觀時(shí)間。指所需最少時(shí)間，用樂觀時(shí)間。指所需最少時(shí)間，用a表示。表示。 2.最可能時(shí)間。指正常時(shí)間，用最可能時(shí)間。指正常時(shí)間，用m表示。表示。 3.悲觀時(shí)間。指不順利情況下，最多時(shí)間，用悲觀時(shí)間。指不順利情況下，最多時(shí)間，用b表示。如表表示。如表12-13所示：所示： 表表12-13 單位：周單位：周 活動(dòng)活動(dòng) 樂觀時(shí)間樂觀時(shí)間最可能時(shí)間最可能時(shí)間悲觀時(shí)間悲觀時(shí)間 a b c d e f g h i 1.5 2.0 1.0 1.5 0.5 1.0 3.0 3.0 1.5 2.0 2.5 2.0 2.0 1.0

33、 2.0 3.5 4.0 2.0 2.5 6.0 3.0 2.5 1.5 3.0 7.0 5.0 2.5 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 25 2 2 統(tǒng)籌方法統(tǒng)籌方法 顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我們可以顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我們可以 可以假定這些時(shí)間的概率分布近似服從可以假定這些時(shí)間的概率分布近似服從 分布。我們可以用如下公式計(jì)分布。我們可以用如下公式計(jì) 算出完成活動(dòng)所需的平均時(shí)間：算出完成活動(dòng)所需的平均時(shí)間： 以及方差以及方差 例如：完成工作例如：完成工作g g所需平均時(shí)間：所需平均時(shí)間： 同時(shí)求出方差為同時(shí)求出

34、方差為 6 4bma T 2 6 2 )( ab 4 6 0.75.340.3 6 4 bma T g 9 4 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 26 2 2 統(tǒng)籌方法統(tǒng)籌方法 同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差，如表同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差，如表12-14： 表表12-14 活動(dòng)活動(dòng)T（平均時(shí)（平均時(shí) 間）間） 方差方差活動(dòng)活動(dòng)T方差方差 a 20.028f20.111 b30.445g40.445 c20.111h40.111 d20.028i20.028 e10.028 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 27

35、2 2 統(tǒng)籌方法統(tǒng)籌方法 下面就用平均時(shí)間代替完成活動(dòng)所需時(shí)間，并在網(wǎng)絡(luò)圖上標(biāo)上每個(gè)活下面就用平均時(shí)間代替完成活動(dòng)所需時(shí)間，并在網(wǎng)絡(luò)圖上標(biāo)上每個(gè)活 動(dòng)最早開始時(shí)間和最早結(jié)束時(shí)間，如圖動(dòng)最早開始時(shí)間和最早結(jié)束時(shí)間，如圖12-14所示。所示。 1 2 3 4 5 87 6 同樣也可以標(biāo)上最晚開始時(shí)間和最晚完成時(shí)間等。同樣也可以標(biāo)上最晚開始時(shí)間和最晚完成時(shí)間等。 a0,2 g5,9 b2,5e5,6 d2,4 f6,8 c0,2 i13,15 h9,13 3 2 22 1 4 2 4 2 1 2 3 4 5 87 6 a0,2 g5,9 b2,5 e5,6 d2,4 f6,8 c0,2 i13,15

36、 h9,13 21,3 110,11 45,949,13 23,5 20,2 32,5 213,15 211,13 圖12-14 圖12-15 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 28 2 2 統(tǒng)籌方法統(tǒng)籌方法 從表從表12-15上我們找到了一條從發(fā)點(diǎn)到收點(diǎn)由關(guān)鍵工序上我們找到了一條從發(fā)點(diǎn)到收點(diǎn)由關(guān)鍵工序a,b,g,h,i組成的組成的 關(guān)鍵路線，用雙線標(biāo)出來。則完成培訓(xùn)工作所需的平均時(shí)間為各關(guān)鍵路線關(guān)鍵路線，用雙線標(biāo)出來。則完成培訓(xùn)工作所需的平均時(shí)間為各關(guān)鍵路線 的時(shí)間之和：的時(shí)間之和： =2+3+4+4+2=15（周）（周） 同時(shí)完成時(shí)間近似服從一定的概率分布正態(tài)分布，

37、則均值為關(guān)鍵路線同時(shí)完成時(shí)間近似服從一定的概率分布正態(tài)分布，則均值為關(guān)鍵路線 上各關(guān)鍵活動(dòng)之均值之和上各關(guān)鍵活動(dòng)之均值之和15，方差也為關(guān)鍵路線上各關(guān)鍵活動(dòng)方差之和，方差也為關(guān)鍵路線上各關(guān)鍵活動(dòng)方差之和 1.05。 由此我們可以計(jì)算出此項(xiàng)培訓(xùn)組織工作不同完工時(shí)間的概率，如由此我們可以計(jì)算出此項(xiàng)培訓(xùn)組織工作不同完工時(shí)間的概率，如16周周 內(nèi)完工的概率。內(nèi)完工的概率。 為求此概率，可以先求為求此概率，可以先求u值。值。 式中的式中的T為預(yù)定完工時(shí)間為預(yù)定完工時(shí)間16，E（T）=15， 算得算得u=0.976。查正態(tài)分布函數(shù)表可知概率為。查正態(tài)分布函數(shù)表可知概率為0.8355。即。即16周內(nèi)完工周內(nèi)

38、完工 的概率為的概率為83.55%. )(TET u 025. 105. 1 ihgbaTTTTT 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 29 2 2 統(tǒng)籌方法統(tǒng)籌方法 其正態(tài)分布圖如圖其正態(tài)分布圖如圖12-16所示：所示： 16 15)( 025. 1 TE 圖圖12-16 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 30 2 2 統(tǒng)籌方法統(tǒng)籌方法 四、網(wǎng)絡(luò)優(yōu)化四、網(wǎng)絡(luò)優(yōu)化 得到初始的計(jì)劃方案，但通常要對初始方案進(jìn)行調(diào)整與完善。根據(jù)計(jì)得到初始的計(jì)劃方案，但通常要對初始方案進(jìn)行調(diào)整與完善。根據(jù)計(jì) 劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(jì)

39、劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(jì) 劃方案。劃方案。 1.時(shí)間時(shí)間-資源優(yōu)化資源優(yōu)化 做法：做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。）優(yōu)先安排關(guān)鍵工序所需的資源。 2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間。）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間。 3）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡。）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡。 下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。在例下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。在例5中，若加工工人中，若加工工人 為為65人，并假定這些工人可完成這人，并假定這些工人可完成這5個(gè)工序任一個(gè)

40、，下面來尋求一個(gè)時(shí)間個(gè)工序任一個(gè)，下面來尋求一個(gè)時(shí)間- 資源最優(yōu)方案。如表資源最優(yōu)方案。如表12-16所示：所示： 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 31 2 2 統(tǒng)籌方法統(tǒng)籌方法 表表12-16 工序工序需要人需要人 數(shù)數(shù) 最早開最早開 始時(shí)間始時(shí)間 所需時(shí)所需時(shí) 間間 時(shí)差時(shí)差 d5860200 f22701847 g428030 h391001520 i26110250 若上述工序都按最早開始時(shí)間安排，那么從第若上述工序都按最早開始時(shí)間安排，那么從第60天至第天至第135天的天的75天天 里，所需的機(jī)械加工工人人數(shù)如圖里，所需的機(jī)械加工工人人數(shù)如圖12-17所示。

41、所示。 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 32 2 2 統(tǒng)籌方法統(tǒng)籌方法 在圖的上半部中，工序代號后的數(shù)字是人數(shù)，線下面的數(shù)字是非關(guān)鍵在圖的上半部中，工序代號后的數(shù)字是人數(shù)，線下面的數(shù)字是非關(guān)鍵 工序時(shí)差長度。圖的下半部表示從第工序時(shí)差長度。圖的下半部表示從第60天至天至135天內(nèi)的天內(nèi)的75天里，所需機(jī)械天里，所需機(jī)械 加工工人數(shù)，這樣的圖稱為資源負(fù)荷圖。加工工人數(shù)，這樣的圖稱為資源負(fù)荷圖。 2746 3 5 f(22人）人） 18 h(39人人) 15 58人人 64人人 80人人81人人 42人人 26人人 65人人 60 80 100 120 130 d(58人

42、）人） i(26人）人） g(42人）人） 302025 圖圖12-17 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 33 2 2 統(tǒng)籌方法統(tǒng)籌方法 同時(shí)我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時(shí)同時(shí)我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時(shí) 差，錯(cuò)開各工序的開始時(shí)間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我差，錯(cuò)開各工序的開始時(shí)間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我 們讓非關(guān)鍵工序們讓非關(guān)鍵工序f從第從第80天開始，工序天開始，工序h從第從第110天開始。找到了時(shí)間天開始。找到了時(shí)間-資源資源 優(yōu)化的方案，如圖優(yōu)化的方案，如圖12-18所示，在不增加工

43、人的情況下保證了工程按期完所示，在不增加工人的情況下保證了工程按期完 成。成。 2467 5 3 f(22人）人） h(39人）人） d(58人）人） i(26人）人） g(42人）人） 工人數(shù)工人數(shù) 65人人 60 80 100 120 130 58人人 42人人 64人人 26人人 65人人 圖圖12-18 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 34 2 2 統(tǒng)籌方法統(tǒng)籌方法 2.時(shí)間時(shí)間-費(fèi)用優(yōu)化費(fèi)用優(yōu)化 需要考慮時(shí)間與費(fèi)用的問題：在既定的時(shí)間前工程完工的前提下，使需要考慮時(shí)間與費(fèi)用的問題：在既定的時(shí)間前工程完工的前提下，使 得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件

44、下使工程最早完工。這些得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。這些 是時(shí)間是時(shí)間-費(fèi)用優(yōu)化要研究和解決的問題。費(fèi)用優(yōu)化要研究和解決的問題。 直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這 需要增加一筆費(fèi)用，成為直接費(fèi)用。需要增加一筆費(fèi)用，成為直接費(fèi)用。 間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用 稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。 管管 理理

45、運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 35 2 2 統(tǒng)籌方法統(tǒng)籌方法 工序的最快完成時(shí)間：指完成時(shí)間的最高限度。工序的最快完成時(shí)間：指完成時(shí)間的最高限度。 我們設(shè)完成工序我們設(shè)完成工序j的正常所需時(shí)間為的正常所需時(shí)間為Tj;直接費(fèi)用為直接費(fèi)用為cj;完成工序完成工序j的最快完成時(shí)的最快完成時(shí) 間為間為Tj,直接費(fèi)用為直接費(fèi)用為cj。這樣我們可以計(jì)算出縮短工序。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接的一天工期所增加的直接 費(fèi)用，用費(fèi)用，用kj表示，稱為直接費(fèi)用變動(dòng)率。有表示，稱為直接費(fèi)用變動(dòng)率。有 時(shí)間時(shí)間-費(fèi)用優(yōu)化問題可建立兩個(gè)線性規(guī)劃模型。費(fèi)用優(yōu)化問題可建立兩個(gè)線性規(guī)劃模

46、型。 模型一，在既定的時(shí)間模型一，在既定的時(shí)間T完工的前提下，問各工序的完成時(shí)間為多少才使因完工的前提下，問各工序的完成時(shí)間為多少才使因 縮短工期而增加的直接費(fèi)用最少。縮短工期而增加的直接費(fèi)用最少。 設(shè)工序（設(shè)工序（i ,j)的提前完工時(shí)間為的提前完工時(shí)間為Yij,我們用我們用Tij,Tij分別表示正常完工時(shí)間與最快分別表示正常完工時(shí)間與最快 完工的時(shí)間，則有工序（完工的時(shí)間，則有工序（i ,j)的實(shí)際完工時(shí)間為：的實(shí)際完工時(shí)間為：Tij-Yij。我們用。我們用Cij,Cij表示用正表示用正 常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，Kij為工

47、序（為工序（i ,j)的直接費(fèi)用的直接費(fèi)用 變動(dòng)率。得到這個(gè)問題的線性規(guī)劃模型如下：變動(dòng)率。得到這個(gè)問題的線性規(guī)劃模型如下： minf= （Kij*Yij) （i,j) S.t. Xj-Xi Tij-Yij,對一切弧（對一切弧（i, j) Yij Tij-Tij, 對一切?。▽σ磺谢。╥, j) Xn-X1 T, Xi 0， Yij 0。 jj jj j TT cc k 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 36 2 2 統(tǒng)籌方法統(tǒng)籌方法 例例7. 例例5所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道

48、工序 所需正常完工時(shí)間與最快完工時(shí)間，以及對應(yīng)正常完工時(shí)間與最快完工時(shí)間的所需正常完工時(shí)間與最快完工時(shí)間，以及對應(yīng)正常完工時(shí)間與最快完工時(shí)間的 所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表12-17所示。所示。 表表12-17 工序工序Tij正常正常 完工完工 Cij直接直接 費(fèi)用費(fèi)用 Tij最快最快 完工完工 Cij直接直接 費(fèi)用費(fèi)用 直接費(fèi)用直接費(fèi)用 變動(dòng)率變動(dòng)率 a60100006010000- b454500306300120 c10280054300300 d2070001011000400 e40100003512500500 f183600105440230 g3090002012500350 h153750105750400 i256250159150290 j35120003512000- 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 37 2 2 統(tǒng)籌方法統(tǒng)籌方法 該工程要求在該工