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

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

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

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

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

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

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

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

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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 6 1 1 車間作業(yè)計劃模型車間作業(yè)計劃模型 圖圖 12-1 從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料 造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。 為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零

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

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

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

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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 8 同樣，下一個最短加工時間為同樣，下一個最短加工時間為1，這是車床加工零件，這是車床加工零件3的所需時間，故的所需時間，故 把零件把零件3排在第二位上，同時把零件排在第二位上，同時把零件3所在的行劃去。如表所在的行劃去。如表12-6中黑色線條中黑色線條 所示。所示。 這樣就得到了最優(yōu)加工順序：這樣就得到

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

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

16、某公司研制新產品的部分工序與所需時間以及它們之間的相互 關系都顯示在其工序進度表如表關系都顯示在其工序進度表如表12-8所示，請畫出其統(tǒng)籌方法網(wǎng)絡圖。所示，請畫出其統(tǒng)籌方法網(wǎng)絡圖。 表表12-8 工序代號工序代號工序內容工序內容所需時間（天所需時間（天)緊前工序緊前工序 a b c d e 產品設計與工藝設計產品設計與工藝設計 外購配套零件外購配套零件 外購生產原料外購生產原料 自制主件自制主件 主配可靠性試驗主配可靠性試驗 60 15 13 38 8 - a a c b,d 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 10 2 2 統(tǒng)籌方法統(tǒng)籌方法 解解:用網(wǎng)絡圖表示上述的工序

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

18、 60 13 8 38 15 圖圖12-4 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 11 2 2 統(tǒng)籌方法統(tǒng)籌方法 例、把例的工序進度表做一些擴充，如表例、把例的工序進度表做一些擴充，如表12-9，請畫出其統(tǒng)籌方法，請畫出其統(tǒng)籌方法 的網(wǎng)絡圖。的網(wǎng)絡圖。 表表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， 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 12 2 2 統(tǒng)籌方法統(tǒng)

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

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

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

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

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

24、析 17 2 2 統(tǒng)籌方法統(tǒng)籌方法 解：據(jù)表解：據(jù)表12-10,繪制網(wǎng)絡圖如圖繪制網(wǎng)絡圖如圖12-8。 圖圖12-8 如圖如圖12-8 ,-就是一條關鍵路線，我們要干完所有的工序就是一條關鍵路線，我們要干完所有的工序 就必須走完所有這樣的路線，由于很多工序可以同時進行，所以網(wǎng)絡中最就必須走完所有這樣的路線，由于很多工序可以同時進行，所以網(wǎng)絡中最 長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關鍵路長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關鍵路 線。線。 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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 18 2 2 統(tǒng)籌方法統(tǒng)籌方法 下面我們給出找關鍵路線的辦法下面我們給出找關鍵路線的辦法 首先，從網(wǎng)絡的發(fā)點開始，按順序計算出每個工序的最早開始時間首先，從網(wǎng)絡的發(fā)點開始，按順序計算出每個工序的最早開始時間 （ES )和最早結束時間（和最早結束時間（EF) ，設一個工序所需的時間為，設一個工序所需的時間為t，這對于同一，這對于同一 個工序來說，有個工序來說，有 EF=ES+t。 工序工序a的最早的最早 開始時間開始時間 工序工序a的最早的最早 完成時間完成時間 11 a0，60 60 圖圖12-9 管管 理理 運運 籌籌 學學

26、第12章排序與統(tǒng)籌方法分析 19 2 2 統(tǒng)籌方法統(tǒng)籌方法 圖圖12-10 其次其次,從網(wǎng)絡的收點開始計算出在不影響整個工程最早結束時間的情從網(wǎng)絡的收點開始計算出在不影響整個工程最早結束時間的情 況下各個工序的最晚開始時間況下各個工序的最晚開始時間(縮寫為縮寫為LS)和最晚結束時間（縮寫為和最晚結束時間（縮寫為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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 20 2 2 統(tǒng)籌方法統(tǒng)籌方法 運用此法則，可以從首點開始計算出每個工序的運用此法則，可以從首點開始計算出每個工序的LF與與LS，如圖，如圖12-11 所示。所示。 接著，可以計算出每一個工序的時差，把在不影響工程最早結束時間接著，可以計算出每一個工序的時差，把在不影響工程最早結束時間 的條件下，工序最早開始（或結束）的時間可以推遲的時間，成為該工序的條件下，工序最早開始（或結束）的時間可以推遲的時間，成為該工序 的時差，對每個工序來說其時差記為的時差，對每個工序來說其時差記為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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 21 2 2 統(tǒng)籌方法統(tǒng)籌方法 最后將各工序的時差，以及其他信息構成工序時間表如表最后將各工序的時差，以及其他信息構成工序時間表如表12-11所所 示。示。 這樣就找到了一條由關鍵工

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

30、所示，要求繪制 出統(tǒng)籌方法的網(wǎng)絡圖，設法求出網(wǎng)絡時間和關鍵路線，并確定開始這個組出統(tǒng)籌方法的網(wǎng)絡圖，設法求出網(wǎng)絡時間和關鍵路線，并確定開始這個組 織工作的時間以保證培訓工作如期舉行?？椆ぷ鞯臅r間以保證培訓工作如期舉行。 解：由表解：由表12-12，繪出統(tǒng)籌方法的網(wǎng)絡圖如圖，繪出統(tǒng)籌方法的網(wǎng)絡圖如圖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)籌方法 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 23 2 2 統(tǒng)籌方法統(tǒng)籌方法 活動（工序）活動（工序）活動（工序）內容活動（工序）內容緊前活動緊前活動 （工序）

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

32、確定完成每個活動所需時間， 但對所需時間做了三種估計：但對所需時間做了三種估計： 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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 25 2 2 統(tǒng)籌方法統(tǒng)籌方法 顯然這三種完成活動所需時間都具有一定概率，由經驗，我們可以顯然這三種完成活動所需時間都具有一定概率，由經驗，我們可以 可以假定這些時間的概率分布近似服從可以假定這些時間的概率分布近似服從 分布。我們可以用如下公式計分布。我們可以用如下公式計 算出完成活動所需的平均時間：算出完成活動所需的平均時間： 以及方差以及方差 例如：完成工作例如：完成工作g g所需平均時間：所需平均時間： 同時求出方差為同時求出

34、方差為 6 4bma T 2 6 2 )( ab 4 6 0.75.340.3 6 4 bma T g 9 4 管管 理理 運運 籌籌 學學 第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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 27

35、2 2 統(tǒng)籌方法統(tǒng)籌方法 下面就用平均時間代替完成活動所需時間，并在網(wǎng)絡圖上標上每個活下面就用平均時間代替完成活動所需時間，并在網(wǎng)絡圖上標上每個活 動最早開始時間和最早結束時間，如圖動最早開始時間和最早結束時間，如圖12-14所示。所示。 1 2 3 4 5 87 6 同樣也可以標上最晚開始時間和最晚完成時間等。同樣也可以標上最晚開始時間和最晚完成時間等。 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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 28 2 2 統(tǒng)籌方法統(tǒng)籌方法 從表從表12-15上我們找到了一條從發(fā)點到收點由關鍵工序上我們找到了一條從發(fā)點到收點由關鍵工序a,b,g,h,i組成的組成的 關鍵路線，用雙線標出來。則完成培訓工作所需的平均時間為各關鍵路線關鍵路線，用雙線標出來。則完成培訓工作所需的平均時間為各關鍵路線 的時間之和：的時間之和： =2+3+4+4+2=15（周）（周） 同時完成時間近似服從一定的概率分布正態(tài)分布，

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

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

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

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

41、所示。 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 32 2 2 統(tǒng)籌方法統(tǒng)籌方法 在圖的上半部中，工序代號后的數(shù)字是人數(shù)，線下面的數(shù)字是非關鍵在圖的上半部中，工序代號后的數(shù)字是人數(shù)，線下面的數(shù)字是非關鍵 工序時差長度。圖的下半部表示從第工序時差長度。圖的下半部表示從第60天至天至135天內的天內的75天里，所需機械天里，所需機械 加工工人數(shù)，這樣的圖稱為資源負荷圖。加工工人數(shù)，這樣的圖稱為資源負荷圖。 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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 33 2 2 統(tǒng)籌方法統(tǒng)籌方法 同時我們應優(yōu)先安排關鍵工序所需的工人，再利用非關鍵工序的時同時我們應優(yōu)先安排關鍵工序所需的工人，再利用非關鍵工序的時 差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經過調整，我差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經過調整，我 們讓非關鍵工序們讓非關鍵工序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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 34 2 2 統(tǒng)籌方法統(tǒng)籌方法 2.時間時間-費用優(yōu)化費用優(yōu)化 需要考慮時間與費用的問題：在既定的時間前工程完工的前提下，使需要考慮時間與費用的問題：在既定的時間前工程完工的前提下，使 得所需的費用最少，或者在不超工程預算的條件

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

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

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

47、序（為工序（i ,j)的直接費用的直接費用 變動率。得到這個問題的線性規(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 管管 理理 運運 籌籌 學學 第12章排序與統(tǒng)籌方法分析 36 2 2 統(tǒng)籌方法統(tǒng)籌方法 例例7. 例例5所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道

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