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

應該按照什么樣的加工順序來加工這六個零件，才能使得這六個零件在車間里停留的平均時間為最少？零件加工時間（小時）零件加工時間（小時）1231.82.00.54560.91.31.53§1車間作業(yè)計劃模型一、一臺機器、n個零件的排序問題零件§1車間作業(yè)計劃模型

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

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設法找到一種簡便的算法。對于某種加工順序，我們知道安排在第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)＝6P1+5P2+4P3+3P4+2P5+P6.那么各個零件平均停留時間為

從上式可知，對于一臺機器n個零件的排序問題，只要系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。4§1車間作業(yè)計劃模型例1解：如果我們用§1車間作業(yè)計劃模型二、兩臺機器、n個零件

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

應該如何安排這五個零件的先后順序才能使完成這五個零件的總的加工時間為最少？解：由于每個零件必須先進行車床加工，再進行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和車床、磨床在每個時間段的狀況的圖形所構成。零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.255§1車間作業(yè)計劃模型二、兩臺機器、n個零件零件車床磨床零§1車間作業(yè)計劃模型圖12-1從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件加工任務所需總時間最少的零件排序方法。123451車床磨床23450106§1車間作業(yè)計劃模型123451車床磨床23450106§1車間作業(yè)計劃模型尋找例2的最優(yōu)解：我們在表12-5中找到所列出的最短加工時間是0.25,它是第二道工序磨床加工零件2的所需時間，由于這個時間與磨床有關，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行。如表12-6中紅色線條所示。

接著，我們又找到最短加工時間為0.5，這一時間與磨床（第二工序）有關，我們把磨床加工時間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時把表中的零件1所在的行劃去。如表12-6中黃色線條所示。下一個最短加工時間為0.75，這個加工時間是車床（第一工序）加工零件5的所需時間，故把零件5排在加工順序的第一位上，同時把表中的零件5所在的行劃去。如表12-6中藍色線條所示。零件車床（第一工序）磨床（第二工序）零件車床（第一工序）磨床（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表12-67§1車間作業(yè)計劃模型尋找例2的最優(yōu)解：我

同樣，下一個最短加工時間為1，這是車床加工零件3的所需時間，故把零件3排在第二位上，同時把零件3所在的行劃去。如表12-6中黑色線條所示。這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個小時就能完成全部加工。從例2中我們可以歸納出關于兩臺機器n個零件的排序問題，使得全部任務總的時間最短的排序算法。在加工所需時間表上選出最短加工時間tij，這是第i工序加工j零件所需時間，當i=1時，將零件j的順序盡量靠前，若i=2時，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1?！?車間作業(yè)計劃模型8同樣，下一個最短加工時間為1，這是車床加工§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計劃網(wǎng)絡圖、進度安排、網(wǎng)絡優(yōu)化等環(huán)節(jié)，下面進行分別討論：一、計劃網(wǎng)絡圖統(tǒng)籌方法的第一步工作就是繪制計劃網(wǎng)絡圖，也就是將工序（或稱為活動）進度表轉換為統(tǒng)籌方法的網(wǎng)絡圖。例3、某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關系都顯示在其工序進度表如表12-8所示，請畫出其統(tǒng)籌方法網(wǎng)絡圖。表12-8工序代號工序內容所需時間（天)緊前工序abcde產(chǎn)品設計與工藝設計外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗601513388-aacb,d9§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計劃網(wǎng)絡圖、進§2統(tǒng)籌方法解:用網(wǎng)絡圖表示上述的工序進度表網(wǎng)絡圖中的點表示一個事件,是一個或若干個工序的開始或結束,是相鄰工序在時間上的分界點,點用圓圈表示,圓圈里的數(shù)字表示點的編號?；”硎疽粋€工序（或活動），弧的方向是從工序開始指向工序的結束，弧上是各工序的代號，下面標以完成此工序所需的時間（或資源）等數(shù)據(jù)，即為對此弧所賦的權數(shù)．

１２４５３abcde601383815圖12-410§2統(tǒng)籌方法解:用網(wǎng)絡圖表示上述的工序進度表１２４５３ab§2統(tǒng)籌方法

例４、把例３的工序進度表做一些擴充，如表12-9，請畫出其統(tǒng)籌方法的網(wǎng)絡圖。

表12-9工序代號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ11§2統(tǒng)籌方法例４、把例３的工序進度表做一些擴充，如表§2統(tǒng)籌方法

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

152643a60b158e1013dc38f圖12-512§2統(tǒng)籌方法解：我們把工序ｆ擴充到圖12-§2統(tǒng)籌方法在網(wǎng)絡圖上添加ｇ、ｈ工序得網(wǎng)絡圖12-6。

在統(tǒng)籌方法的網(wǎng)絡圖中不允許兩個點之間多于一條弧，因此增加了一個點和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-613§2統(tǒng)籌方法在網(wǎng)絡圖上添加ｇ、ｈ§2統(tǒng)籌方法在繪制統(tǒng)籌方法的網(wǎng)絡圖時，要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-714§2統(tǒng)籌方法1257834a6015bec13d388h5§2統(tǒng)籌方法二、網(wǎng)絡時間與關鍵路線在繪制出網(wǎng)絡圖之后，我們可以由網(wǎng)絡圖求出：1、完成此工程項目所需的最少時間。2、每個工序的開始時間與結束時間。3、關鍵路線及其應用的關鍵工序。4、非關鍵工序在不影響工程的完成時間的前提下，其開始時間與結束時間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線，具體過程如表12-10,求：完成此工程的最少時間，關鍵路線及相應的關鍵工序，各工序的最早開始時間和非關鍵工序在不影響工程完成時間的前提下，其開始時間與結束時間可以推遲多久。15§2統(tǒng)籌方法二、網(wǎng)絡時間與關鍵路線15§2統(tǒng)籌方法表12-10工序代號工序內容所需時間（天）緊前工序abcdefghij生產(chǎn)線設計外購零配件下料、鍛件工裝制造1木模、鑄件機械加工1工裝制造2機械加工2機械加工3裝配調試60451020401830152535/aaaacdd,egb,i,f,h16§2統(tǒng)籌方法表12-10工序代號工序內容所需時間（天）緊前§2統(tǒng)籌方法解：據(jù)表12-10,繪制網(wǎng)絡圖如圖12-8。圖12-8如圖12-8,①-②-③-⑦-⑧就是一條關鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時進行，所以網(wǎng)絡中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關鍵路線。12346785a60b45echj35ig1030d204025f181517§2統(tǒng)籌方法解：據(jù)表12-10,繪制網(wǎng)絡圖如圖12-8。1§2統(tǒng)籌方法下面我們給出找關鍵路線的辦法首先，從網(wǎng)絡的發(fā)點開始，按順序計算出每個工序的最早開始時間（ES)和最早結束時間（EF)，設一個工序所需的時間為t，這對于同一個工序來說，有EF=ES+t。

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

圖12-10其次,從網(wǎng)絡的收點開始計算出在不影響整個工程最早結束時間的情況下各個工序的最晚開始時間(縮寫為LS)和最晚結束時間（縮寫為LF),顯然對同一工序有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)籌方法

運用此法則，可以從首點開始計算出每個工序的LF與LS，如圖12-11所示。

接著，可以計算出每一個工序的時差，把在不影響工程最早結束時間的條件下，工序最早開始（或結束）的時間可以推遲的時間，成為該工序的時差，對每個工序來說其時差記為Ts有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)籌方法運用此法則，可以從首點開始計算§2統(tǒng)籌方法

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

應該按照什么樣的加工順序來加工這六個零件，才能使得這六個零件在車間里停留的平均時間為最少？零件加工時間（小時）零件加工時間（小時）1231.82.00.54560.91.31.524§1車間作業(yè)計劃模型一、一臺機器、n個零件的排序問題零件§1車間作業(yè)計劃模型

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

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設法找到一種簡便的算法。對于某種加工順序，我們知道安排在第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)＝6P1+5P2+4P3+3P4+2P5+P6.那么各個零件平均停留時間為

從上式可知，對于一臺機器n個零件的排序問題，只要系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。25§1車間作業(yè)計劃模型例1解：如果我們用§1車間作業(yè)計劃模型二、兩臺機器、n個零件

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

應該如何安排這五個零件的先后順序才能使完成這五個零件的總的加工時間為最少？解：由于每個零件必須先進行車床加工，再進行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和車床、磨床在每個時間段的狀況的圖形所構成。零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.2526§1車間作業(yè)計劃模型二、兩臺機器、n個零件零件車床磨床零§1車間作業(yè)計劃模型圖12-1從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件加工任務所需總時間最少的零件排序方法。123451車床磨床234501027§1車間作業(yè)計劃模型123451車床磨床23450106§1車間作業(yè)計劃模型尋找例2的最優(yōu)解：我們在表12-5中找到所列出的最短加工時間是0.25,它是第二道工序磨床加工零件2的所需時間，由于這個時間與磨床有關，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行。如表12-6中紅色線條所示。

接著，我們又找到最短加工時間為0.5，這一時間與磨床（第二工序）有關，我們把磨床加工時間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時把表中的零件1所在的行劃去。如表12-6中黃色線條所示。下一個最短加工時間為0.75，這個加工時間是車床（第一工序）加工零件5的所需時間，故把零件5排在加工順序的第一位上，同時把表中的零件5所在的行劃去。如表12-6中藍色線條所示。零件車床（第一工序）磨床（第二工序）零件車床（第一工序）磨床（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表12-628§1車間作業(yè)計劃模型尋找例2的最優(yōu)解：我

同樣，下一個最短加工時間為1，這是車床加工零件3的所需時間，故把零件3排在第二位上，同時把零件3所在的行劃去。如表12-6中黑色線條所示。這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個小時就能完成全部加工。從例2中我們可以歸納出關于兩臺機器n個零件的排序問題，使得全部任務總的時間最短的排序算法。在加工所需時間表上選出最短加工時間tij，這是第i工序加工j零件所需時間，當i=1時，將零件j的順序盡量靠前，若i=2時，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1?！?車間作業(yè)計劃模型29同樣，下一個最短加工時間為1，這是車床加工§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計劃網(wǎng)絡圖、進度安排、網(wǎng)絡優(yōu)化等環(huán)節(jié)，下面進行分別討論：一、計劃網(wǎng)絡圖統(tǒng)籌方法的第一步工作就是繪制計劃網(wǎng)絡圖，也就是將工序（或稱為活動）進度表轉換為統(tǒng)籌方法的網(wǎng)絡圖。例3、某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關系都顯示在其工序進度表如表12-8所示，請畫出其統(tǒng)籌方法網(wǎng)絡圖。表12-8工序代號工序內容所需時間（天)緊前工序abcde產(chǎn)品設計與工藝設計外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗601513388-aacb,d30§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計劃網(wǎng)絡圖、進§2統(tǒng)籌方法解:用網(wǎng)絡圖表示上述的工序進度表網(wǎng)絡圖中的點表示一個事件,是一個或若干個工序的開始或結束,是相鄰工序在時間上的分界點,點用圓圈表示,圓圈里的數(shù)字表示點的編號?；”硎疽粋€工序（或活動），弧的方向是從工序開始指向工序的結束，弧上是各工序的代號，下面標以完成此工序所需的時間（或資源）等數(shù)據(jù)，即為對此弧所賦的權數(shù)．

１２４５３abcde601383815圖12-431§2統(tǒng)籌方法解:用網(wǎng)絡圖表示上述的工序進度表１２４５３ab§2統(tǒng)籌方法

例４、把例３的工序進度表做一些擴充，如表12-9，請畫出其統(tǒng)籌方法的網(wǎng)絡圖。

表12-9工序代號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ32§2統(tǒng)籌方法例４、把例３的工序進度表做一些擴充，如表§2統(tǒng)籌方法

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

152643a60b158e1013dc38f圖12-533§2統(tǒng)籌方法解：我們把工序ｆ擴充到圖12-§2統(tǒng)籌方法在網(wǎng)絡圖上添加ｇ、ｈ工序得網(wǎng)絡圖12-6。

在統(tǒng)籌方法的網(wǎng)絡圖中不允許兩個點之間多于一條弧，因此增加了一個點和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-634§2統(tǒng)籌方法在網(wǎng)絡圖上添加ｇ、ｈ§2統(tǒng)籌方法在繪制統(tǒng)籌方法的網(wǎng)絡圖時，要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-735§2統(tǒng)籌方法1257834a6015bec13d388h5§2統(tǒng)籌方法二、網(wǎng)絡時間與關鍵路線在繪制出網(wǎng)絡圖之后，我們可以由網(wǎng)絡圖求出：1、完成此工程項目所需的最少時間。2、每個工序的開始時間與結束時間。3、關鍵路線及其應用的關鍵工序。4、非關鍵工序在不影響工程的完成時間的前提下，其開始時間與結束時間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線，具體過程如表12-10,求：完成此工程的最少時間，關鍵路線及相應的關鍵工序，各工序的最早開始時間和非關鍵工序在不影響工程完成時間的前提下，其開始時間與結束時間可以推遲多久。36§2統(tǒng)籌方法二、網(wǎng)絡時間與關鍵路線15§2統(tǒng)籌方法表12-10工序代號工序內容所需時間（天）緊前工序abcdefghij生產(chǎn)線設計外購零配件下料、鍛件工裝制造1木模、鑄件機械加工1工裝制造2機械加工2機械加工3裝配調試60451020401830152535/aaaacdd,egb,i,f,h37§2統(tǒng)籌方法表12-10工序代號工序內容所需時間（天）緊前§2統(tǒng)籌方法解：據(jù)表12-10,繪制網(wǎng)絡圖如圖12-8。圖12-8如圖12-8,①-②-③-⑦-⑧就是一條關鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時進行，所以網(wǎng)絡中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關鍵路線。12346785a60b45echj35ig