第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)籌方法。這兩個問題盡管處理的方法有所不同，統(tǒng)籌方法。這兩個問題盡管處理的方法有所不同， 但當(dāng)我們面臨必須完成若干項(xiàng)不能同時進(jìn)行的工但當(dāng)我們面臨必須完成若干項(xiàng)不能同時進(jìn)行的工 作時，它們都將幫助我們應(yīng)該按照怎樣的次序、作時，它們都將幫助我們應(yīng)該按照怎樣的次序、 怎樣的時間表來做這些工作，使得效果最佳（例怎樣的時間表來做這些工作，使

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

3、題 例例1.某車間只有一臺高精度的磨床，常常出現(xiàn)很多零件同時要求這臺某車間只有一臺高精度的磨床，常常出現(xiàn)很多零件同時要求這臺 磨床加工的情況，現(xiàn)有六個零件同時要求加工，這六個零件加工所需時間磨床加工的情況，現(xiàn)有六個零件同時要求加工，這六個零件加工所需時間 如下表所示。如下表所示。 應(yīng)該按照什么樣的加工順序來加工這六個零件，才能使得這六個零應(yīng)該按照什么樣的加工順序來加工這六個零件，才能使得這六個零 件在車間里停留的平均時間為最少？件在車間里停留的平均時間為最少？ 零件零件加工時間加工時間 （小時）（小時） 零件零件加工時間加工時間 （小時）（小時） 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位加工的零件所需的時間，用位加工的零件所需的時間，用Tj表示安排表示安排 在第在第j位加工的零件在車間里總的停留時間，則有位加工的零件在車間里總的停留時間，則有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件不同的加工順序得到不同的各零件的平均停留時間，

5、如何得到一個使得各零件 的平均停留時間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設(shè)的平均停留時間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設(shè) 法找到一種簡便的算法。法找到一種簡便的算法。 對于某種加工順序，我們知道安排在第對于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停留時間為位加工的零件在車間里總的停留時間為 Tj ， Tj = 可知這六個零件的停留時間為：可知這六個零件的停留時間為： 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. 那么各個零件平均停留時間為那么各個零件平均停留時間為 從上式可知，對于一臺機(jī)器從上式可知，對于一臺機(jī)器n個零件的排序問題，只要系數(shù)越大，配上加工時個零件的排序問題，只要系數(shù)越大，配上加工時 間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工 時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。時間越

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

8、 最少？最少？ 解：由于每個零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加解：由于每個零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加 工零件的順序與在磨床上加工零件的順序是一樣的。工零件的順序與在磨床上加工零件的順序是一樣的。 如果這些零件在車床上和磨床上加工順序都為如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖。我們用圖12-1 中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和 車床、磨床在每個時間段的狀況的圖形所構(gòu)成。車床、磨床在每個時間段的狀況的圖形所構(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 從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料 造成的，只要減少磨床的停工待料的時間就能減少整個加工任務(wù)的總時間。造成的，只要減少磨床的停工待料的時間就能減少整個加工任務(wù)的總時間。 為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時間越短的零

10、為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時間越短的零 件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的 零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部 零件加工任務(wù)所需總時間最少的零件排序方法。零件加工任務(wù)所需總時間最少的零件排序方法。 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中找到所列出的最短加工時間是中找到所列出的最短加工時間是0.25,它是第二道工序磨床它是第二道工序磨床 加工零件加工零件2的所需時間，由于這個時間與磨床有關(guān)，故我們把零件的所需時間，由于這個時間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五放在加工順序的末尾，即第五 位，并在表中劃去零件位，并在表中劃去零件2 所在行。如表所在行。如表12-6中紅色線條所示。中紅色線條所示。 接著，我們又找到最短加工時間為接著，我們又找到最短加工時間為0.5，這一時間與磨床（第二工序）有關(guān)，我們把，這一時間與磨床（第二工序）有關(guān)，我們把 磨床加磨床加 工時間為工時間為0.5的

12、零件的零件1放到除第五外的加工順序的末尾，即第四位加工，同時把放到除第五外的加工順序的末尾，即第四位加工，同時把 表中的零件表中的零件1所在所在 的行劃去。如表的行劃去。如表12-6中黃色線條所示。中黃色線條所示。 下一個最短加工時間為下一個最短加工時間為0.75，這個加工時間是車床（第一工序）加工零件，這個加工時間是車床（第一工序）加工零件5的所需時間，故的所需時間，故 把零件把零件5排在加工順序的第一位上，同時把表中的零件排在加工順序的第一位上，同時把表中的零件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 同樣，下一個最短加工時間為同樣，下一個最短加工時間為1，這是車床加工零件，這是車床加工零件3的所需時間，故的所需時間，故 把零件把零件3排在第二位上，同時把零件排在第二位上，同時把零件3所在的行劃去。如表所在的行劃去。如表12-6中黑色線條中黑色線條 所示。所示。 這樣就得到了最優(yōu)加工順序：這樣就得到

14、了最優(yōu)加工順序：5，3，4，1，2。一共只需。一共只需7個小時就能個小時就能 完成全部加工。完成全部加工。 從例從例2中我們可以歸納出關(guān)于兩臺機(jī)器中我們可以歸納出關(guān)于兩臺機(jī)器n個零件的排序問題，使得全部個零件的排序問題，使得全部 任務(wù)總的時間任務(wù)總的時間 最短的排序算法。最短的排序算法。 在加工所需時間表上選出最短加工時間在加工所需時間表上選出最短加工時間tij，這是第，這是第i工序加工工序加工j零件所需零件所需 時間，當(dāng)時間，當(dāng)i=1時，將零件時，將零件j的順序盡量靠前，若的順序盡量靠前，若i=2時，將零件時，將零件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ò)圖，也就是將工序（或稱為 活動）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。活動）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。 例例3、某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互、

16、某公司研制新產(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)容所需時間（天所需時間（天)緊前工序緊前工序 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)表示一個事件網(wǎng)絡(luò)圖中的點(diǎn)表示一個事件,是一個或若干個工序的開始或結(jié)束是一個或若干個工序的開始或結(jié)束,是相是相 鄰工序在時間上的分界點(diǎn)鄰工序在時間上的分界點(diǎn),點(diǎn)用圓圈表示點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號?；A圈里的數(shù)字表示點(diǎn)的編號?；?表示一個工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上表示一個工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上 是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(shù)據(jù)，即是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(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 工序代號工序代號所需時間（天）所需時間（天）緊前工序緊前工序工序代號工序代號所需時間（天）所需時間（天）緊前工序緊前工序 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)系，不需要人力、物力等資源與時間。用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。 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ò)圖中不允許兩個點(diǎn)之間多于一條弧，因此增加在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點(diǎn)之間多于一條弧，因此增加 了一個點(diǎn)和虛工序如圖了一個點(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ò)圖時，要注意圖中不能有缺口和回路在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。 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ò)時間與關(guān)鍵路線二、網(wǎng)絡(luò)時間與關(guān)鍵路線 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出： 1、完成此工程項(xiàng)目所需的最少時間。、完成此工程項(xiàng)目所需的最少時間。 2、每個工序的開始時間與結(jié)束時間。、每個工序的開始時間與結(jié)束時間。 3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工

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

23、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第12章排序與統(tǒng)籌方法分析 16 2 2 統(tǒng)籌方法統(tǒng)籌方法 表表12-10 工序代號工序代號工序內(nèi)容工序內(nèi)容所需時間（天）所需時間（天）緊前工序緊前工序 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)鍵路線，我們要干完所有的工序 就必須走完所有這樣的路線，由于很多工序可以同時進(jìn)行，所以網(wǎng)絡(luò)中最就必須走完所有這樣的路線，由于很多工序可以同時進(jìn)行，所以網(wǎng)絡(luò)中最 長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(guān)鍵路長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(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ì)算出每個工序的最早開始時間首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個工序的最早開始時間 （ES )和最早結(jié)束時間（和最早結(jié)束時間（EF) ，設(shè)一個工序所需的時間為，設(shè)一個工序所需的時間為t，這對于同一，這對于同一 個工序來說，有個工序來說，有 EF=ES+t。 工序工序a的最早的最早 開始時間開始時間 工序工序a的最早的最早 完成時間完成時間 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ì)算出在不影響整個工程最早結(jié)束時間的情從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算出在不影響整個工程最早結(jié)束時間的情 況下各個工序的最晚開始時間況下各個工序的最晚開始時間(縮寫為縮寫為LS)和最晚結(jié)束時間（縮寫為和最晚結(jié)束時間（縮寫為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ì)算出每個工序的運(yùn)用此法則，可以從首點(diǎn)開始計(jì)算出每個工序的LF與與LS，如圖，如圖12-11 所示。所示。 接著，可以計(jì)算出每一個工序的時差，把在不影響工程最早結(jié)束時間接著，可以計(jì)算出每一個工序的時差，把在不影響工程最早結(jié)束時間 的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序 的時差，對每個工序來說其時差記為的時差，對每個工序來說其時差記為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)籌方法 最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表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 三、完成工序所需時間與關(guān)鍵路線三、完成工序所需時間與關(guān)鍵路線 當(dāng)完成工序所需時間不確定的情況下如何求網(wǎng)絡(luò)時間和關(guān)鍵路線？當(dāng)完成工序所需時間不確定的情況下如何求網(wǎng)絡(luò)時間和關(guān)鍵路線？ 例例6. 長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn)，長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn)， 培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項(xiàng)活動的信息如表培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項(xiàng)活動的信息如表12-12所示，要求繪制

30、所示，要求繪制 出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時間和關(guān)鍵路線，并確定開始這個組出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時間和關(guān)鍵路線，并確定開始這個組 織工作的時間以保證培訓(xùn)工作如期舉行?？椆ぷ鞯臅r間以保證培訓(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)籌方法 活動（工序）活動（工序）活動（工序）內(nèi)容活動（工序）內(nèi)容緊前活動緊前活動 （工序）

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ì)來確定完成每個活動所需時間，由于是第一次搞培訓(xùn)，缺乏統(tǒng)計(jì)來

32、確定完成每個活動所需時間， 但對所需時間做了三種估計(jì)：但對所需時間做了三種估計(jì)： 1.樂觀時間。指所需最少時間，用樂觀時間。指所需最少時間，用a表示。表示。 2.最可能時間。指正常時間，用最可能時間。指正常時間，用m表示。表示。 3.悲觀時間。指不順利情況下，最多時間，用悲觀時間。指不順利情況下，最多時間，用b表示。如表表示。如表12-13所示：所示： 表表12-13 單位：周單位：周 活動活動 樂觀時間樂觀時間最可能時間最可能時間悲觀時間悲觀時間 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)籌方法 顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我們可以顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我們可以 可以假定這些時間的概率分布近似服從可以假定這些時間的概率分布近似服從 分布。我們可以用如下公式計(jì)分布。我們可以用如下公式計(jì) 算出完成活動所需的平均時間：算出完成活動所需的平均時間： 以及方差以及方差 例如：完成工作例如：完成工作g g所需平均時間：所需平均時間： 同時求出方差為同時求出

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)籌方法 同樣可以求出每個活動的完成所需平均時間及方差，如表同樣可以求出每個活動的完成所需平均時間及方差，如表12-14： 表表12-14 活動活動T（平均時（平均時 間）間） 方差方差活動活動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)籌方法 下面就用平均時間代替完成活動所需時間，并在網(wǎng)絡(luò)圖上標(biāo)上每個活下面就用平均時間代替完成活動所需時間，并在網(wǎng)絡(luò)圖上標(biāo)上每個活 動最早開始時間和最早結(jié)束時間，如圖動最早開始時間和最早結(jié)束時間，如圖12-14所示。所示。 1 2 3 4 5 87 6 同樣也可以標(biāo)上最晚開始時間和最晚完成時間等。同樣也可以標(biāo)上最晚開始時間和最晚完成時間等。 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)工作所需的平均時間為各關(guān)鍵路線關(guān)鍵路線，用雙線標(biāo)出來。則完成培訓(xùn)工作所需的平均時間為各關(guān)鍵路線 的時間之和：的時間之和： =2+3+4+4+2=15（周）（周） 同時完成時間近似服從一定的概率分布正態(tài)分布，

37、則均值為關(guān)鍵路線同時完成時間近似服從一定的概率分布正態(tài)分布，則均值為關(guān)鍵路線 上各關(guān)鍵活動之均值之和上各關(guān)鍵活動之均值之和15，方差也為關(guān)鍵路線上各關(guān)鍵活動方差之和，方差也為關(guān)鍵路線上各關(guān)鍵活動方差之和 1.05。 由此我們可以計(jì)算出此項(xiàng)培訓(xùn)組織工作不同完工時間的概率，如由此我們可以計(jì)算出此項(xiàng)培訓(xùn)組織工作不同完工時間的概率，如16周周 內(nèi)完工的概率。內(nèi)完工的概率。 為求此概率，可以先求為求此概率，可以先求u值。值。 式中的式中的T為預(yù)定完工時間為預(yù)定完工時間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.時間時間-資源優(yōu)化資源優(yōu)化 做法：做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。）優(yōu)先安排關(guān)鍵工序所需的資源。 2）利用非關(guān)鍵工序的時差，錯開各工序的開始時間。）利用非關(guān)鍵工序的時差，錯開各工序的開始時間。 3）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡。）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡。 下面列舉一個拉平資源需要量最高峰的實(shí)例。在例下面列舉一個拉平資源需要量最高峰的實(shí)例。在例5中，若加工工人中，若加工工人 為為65人，并假定這些工人可完成這人，并假定這些工人可完成這5個工序任一個

40、，下面來尋求一個時間個工序任一個，下面來尋求一個時間- 資源最優(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ù) 最早開最早開 始時間始時間 所需時所需時 間間 時差時差 d5860200 f22701847 g428030 h391001520 i26110250 若上述工序都按最早開始時間安排，那么從第若上述工序都按最早開始時間安排，那么從第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)鍵 工序時差長度。圖的下半部表示從第工序時差長度。圖的下半部表示從第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)籌方法 同時我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時同時我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時 差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我 們讓非關(guān)鍵工序們讓非關(guān)鍵工序f從第從第80天開始，工序天開始，工序h從第從第110天開始。找到了時間天開始。找到了時間-資源資源 優(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.時間時間-費(fèi)用優(yōu)化費(fèi)用優(yōu)化 需要考慮時間與費(fèi)用的問題：在既定的時間前工程完工的前提下，使需要考慮時間與費(fèi)用的問題：在既定的時間前工程完工的前提下，使 得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件

44、下使工程最早完工。這些得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。這些 是時間是時間-費(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è)完成工序j的正常所需時間為的正常所需時間為Tj;直接費(fèi)用為直接費(fèi)用為cj;完成工序完成工序j的最快完成時的最快完成時 間為間為Tj,直接費(fèi)用為直接費(fèi)用為cj。這樣我們可以計(jì)算出縮短工序。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接的一天工期所增加的直接 費(fèi)用，用費(fèi)用，用kj表示，稱為直接費(fèi)用變動率。有表示，稱為直接費(fèi)用變動率。有 時間時間-費(fèi)用優(yōu)化問題可建立兩個線性規(guī)劃模型。費(fèi)用優(yōu)化問題可建立兩個線性規(guī)劃模

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

47、序（為工序（i ,j)的直接費(fèi)用的直接費(fèi)用 變動率。得到這個問題的線性規(guī)劃模型如下：變動率。得到這個問題的線性規(guī)劃模型如下： minf= （Kij*Yij) （i,j) S.t. Xj-Xi Tij-Yij,對一切?。▽σ磺谢。╥, 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、工序 所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的 所需的直接費(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)用 變動率變動率 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)籌方法 該工程要求在該工