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

2、有六個零件同時要求加工，這六個零件加工所需時間 如下表所示。 應該按照什么樣的加工順序來加工這六個零件，才能使得這六個零 件在車間里停留的平均時間為最少？,4,1車間作業(yè)計劃模型,例1解：如果我們用Pi表示安排在第i位加工的零件所需的時間，用Tj表示安排在第j位加工的零件在車間里總的停留時間，則有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設法找到一種簡便的算法。 對于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停留時間為Tj ， T

3、j = 可知這六個零件的停留時間為： 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 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各個零件平均停留時間為 從上式可知，對于一臺機器n個零件的排序問題，只要系數越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使

4、各個零件的平均停留時間為最少。,5,1車間作業(yè)計劃模型,二、兩臺機器、n個零件 例2.某工廠根據合同定做一些零件，這些零件要求先在車床上車削，然后再在 磨床上加工，每臺機器上各零件加工時間如表12-5所示。 表12-5 應該如何安排這五個零件的先后順序才能使完成這五個零件的總的加工時間為 最少？ 解：由于每個零件必須先進行車床加工，再進行磨床加工，所以在車床上加 工零件的順序與在磨床上加工零件的順序是一樣的。 如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1 中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和 車床、磨床在每個時間段的狀況的圖形所

5、構成。,6,1車間作業(yè)計劃模型,圖 12-1 從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料 造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。 為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零 件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的 零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部 零件加工任務所需總時間最少的零件排序方法。,7,1車間作業(yè)計劃模型,尋找例2的最優(yōu)解：我們在表12-5中找到所列出的最短加工時間是0.25,它是第二道工序磨床 加工零件2的所需時間，由于這個時間與磨床有關，故我們把零件2放在加

6、工順序的末尾，即第五 位，并在表中劃去零件2 所在行。如表12-6中紅色線條所示。 接著，我們又找到最短加工時間為0.5，這一時間與磨床（第二工序）有關，我們把 磨床加 工時間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時把 表中的零件1所在 的行劃去。如表12-6中黃色線條所示。 下一個最短加工時間為0.75，這個加工時間是車床（第一工序）加工零件5的所需時間，故 把零件5排在加工順序的第一位上，同時把表中的零件5所在的行劃去。如表12-6中藍色線條所 示。,表12-6,8,同樣，下一個最短加工時間為1，這是車床加工零件3的所需時間，故 把零件3排在第二位上，同時把零件3所

7、在的行劃去。如表12-6中黑色線條 所示。 這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個小時就能 完成全部加工。 從例2中我們可以歸納出關于兩臺機器n個零件的排序問題，使得全部 任務總的時間 最短的排序算法。 在加工所需時間表上選出最短加工時間tij，這是第i工序加工j零件所需 時間，當i=1時，將零件j的順序盡量靠前，若i=2時，將零件j的順序盡量 靠后。在表上劃去零件j的所在行，回到步驟1。,1車間作業(yè)計劃模型,9,2統籌方法,統籌方法包括繪制計劃網絡圖、進度安排、網絡優(yōu)化等環(huán)節(jié)，下面進 行分別討論： 一、計劃網絡圖 統籌方法的第一步工作就是繪制計劃網絡圖，也就是將工序（或稱

8、為 活動）進度表轉換為統籌方法的網絡圖。 例3、某公司研制新產品的部分工序與所需時間以及它們之間的相互 關系都顯示在其工序進度表如表12-8所示，請畫出其統籌方法網絡圖。 表12-8,10,2統籌方法,解:用網絡圖表示上述的工序進度表 網絡圖中的點表示一個事件,是一個或若干個工序的開始或結束,是相 鄰工序在時間上的分界點,點用圓圈表示,圓圈里的數字表示點的編號。弧 表示一個工序（或活動），弧的方向是從工序開始指向工序的結束，弧上 是各工序的代號，下面標以完成此工序所需的時間（或資源）等數據，即 為對此弧所賦的權數,a,b,c,d,e,60,13,8,38,15,圖12-4,11,2統籌方法,例

9、、把例的工序進度表做一些擴充，如表12-9，請畫出其統籌方法的網絡圖。 表12-9,12,2統籌方法,解：我們把工序擴充到圖12-4發(fā)生了問題，由于是的緊前工序，故的結束應該是的開始，所以代表的弧的起點應該是，由于工序的結束也是，所以工序也成了工序的緊前工序，與題意不符。 為此我們設立虛工序。虛工序是實際上并不存在而虛設的工序，用來表示相鄰工序的銜接關系，不需要人力、物力等資源與時間。,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,圖12-5,13,2統籌方法,在網絡圖上添加、工序得網絡圖12-6。 在統籌方法的網絡圖中不允許兩個點之間多于一條弧，因此增加了

10、一個點和虛工序如圖12-7。,1,2,5,6,7,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,g,16,圖12-6,14,2統籌方法,在繪制統籌方法的網絡圖時，要注意圖中不能有缺口和回路。,1,2,5,7,8,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,6,16,g,圖12-7,15,2統籌方法,二、網絡時間與關鍵路線 在繪制出網絡圖之后，我們可以由網絡圖求出： 1、完成此工程項目所需的最少時間。 2、每個工序的開始時間與結束時間。 3、關鍵路線及其應用的關鍵工序。 4、非關鍵工序在不影響工程的完成時間的前提下，其開始時間與結束時 間

11、可以推遲多久。 例5、某公司裝配一條新的生產線，具體過程如表12-10,求：完成此 工程的最少時間，關鍵路線及相應的關鍵工序，各工序的最早開始時間和 非關鍵工序在不影響工程完成時間的前提下，其開始時間與結束時間可以 推遲多久。,16,2統籌方法,表12-10,17,2統籌方法,解：據表12-10,繪制網絡圖如圖12-8。 圖12-8 如圖12-8 ,-就是一條關鍵路線，我們要干完所有的工序 就必須走完所有這樣的路線，由于很多工序可以同時進行，所以網絡中最 長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關鍵路 線。,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,3

12、5,i,g,10,30,d,20,40,25,f,18,15,18,2統籌方法,下面我們給出找關鍵路線的辦法 首先，從網絡的發(fā)點開始，按順序計算出每個工序的最早開始時間 （ES )和最早結束時間（EF) ，設一個工序所需的時間為t，這對于同一 個工序來說，有 EF=ES+t。,工序a的最早 開始時間,工序a的最早 完成時間,1,1,a0，60,60,圖12-9,19,2統籌方法,圖12-10 其次,從網絡的收點開始計算出在不影響整個工程最早結束時間的情 況下各個工序的最晚開始時間(縮寫為LS)和最晚結束時間（縮寫為LF), 顯然對同一工序有 LS=LF-t,1,2,3,6,7,8,5,a0,6

13、0,60,b60,105,45,e60.100,c60,70,h100,115,j135,170,35,i110.135,g80,110,30,d60.80,20,40,25,f70,88,18,4,10,15,20,2統籌方法,運用此法則，可以從首點開始計算出每個工序的LF與LS，如圖12-11 所示。 接著，可以計算出每一個工序的時差，把在不影響工程最早結束時間 的條件下，工序最早開始（或結束）的時間可以推遲的時間，成為該工序 的時差，對每個工序來說其時差記為Ts有 Ts=LS-ES=LF-EF,1,2,3,6,7,8,5,a0,60,600,60,b60,105,4590,135,e60

14、.100,c60,70,h100,115,j135,170,35135,170,i110.135,g80,110,3080,110,d60.80,2060,80,4080,120,25110,135,f70,88,18117,135,4,10107,117,15120,135,21,2統籌方法,最后將各工序的時差，以及其他信息構成工序時間表如表12-11所 示。 這樣就找到了一條由關鍵工序a,d,g,i和j依次連接成的從發(fā)點到收點的 關鍵路線。,22,三、完成工序所需時間與關鍵路線 當完成工序所需時間不確定的情況下如何求網絡時間和關鍵路線？ 例6. 長征研究院培訓中心負責明年春天的各干部的工商

15、管理培訓，培訓中心列出有關培訓組織的各項活動的信息如表12-12所示，要求繪制出統籌方法的網絡圖，設法求出網絡時間和關鍵路線，并確定開始這個組織工作的時間以保證培訓工作如期舉行。 解：由表12-12，繪出統籌方法的網絡圖如圖12-12所示。,圖12-12,2統籌方法,23,2統籌方法,24,2統籌方法,由于是第一次搞培訓，缺乏統計來確定完成每個活動所需時間， 但對所需時間做了三種估計： 1.樂觀時間。指所需最少時間，用a表示。 2.最可能時間。指正常時間，用m表示。 3.悲觀時間。指不順利情況下，最多時間，用b表示。如表12-13所示： 表12-13 單位：周,25,2統籌方法,顯然這三種完成

16、活動所需時間都具有一定概率，由經驗，我們可以 可以假定這些時間的概率分布近似服從 分布。我們可以用如下公式計 算出完成活動所需的平均時間： 以及方差 例如：完成工作g所需平均時間： 同時求出方差為,26,2統籌方法,同樣可以求出每個活動的完成所需平均時間及方差，如表12-14： 表12-14,27,2統籌方法,下面就用平均時間代替完成活動所需時間，并在網絡圖上標上每個活 動最早開始時間和最早結束時間，如圖12-14所示。,1,2,3,4,5,8,7,6,同樣也可以標上最晚開始時間和最晚完成時間等。,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,i13,15,h9,13,

17、3,2,2,2,1,4,2,4,2,1,2,3,4,5,8,7,6,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,i13,15,h9,13,21,3,110,11,45,9,49,13,23,5,20,2,32,5,213,15,211,13,圖12-14,圖12-15,28,2統籌方法,從表12-15上我們找到了一條從發(fā)點到收點由關鍵工序a,b,g,h,i組成的 關鍵路線，用雙線標出來。則完成培訓工作所需的平均時間為各關鍵路線 的時間之和： =2+3+4+4+2=15（周） 同時完成時間近似服從一定的概率分布正態(tài)分布，則均值為關鍵路線 上各關鍵活動之均值之和15，方差

18、也為關鍵路線上各關鍵活動方差之和 1.05。 由此我們可以計算出此項培訓組織工作不同完工時間的概率，如16周 內完工的概率。 為求此概率，可以先求u值。 式中的T為預定完工時間16，E（T）=15， 算得u=0.976。查正態(tài)分布函數表可知概率為0.8355。即16周內完工 的概率為83.55%.,29,2統籌方法,其正態(tài)分布圖如圖12-16所示：,16,圖12-16,30,2統籌方法,四、網絡優(yōu)化 得到初始的計劃方案，但通常要對初始方案進行調整與完善。根據計 劃目標，綜合考慮資源和降低成本等目標，進行網絡優(yōu)化，確定最優(yōu)的計 劃方案。 1.時間-資源優(yōu)化 做法： 1）優(yōu)先安排關鍵工序所需的資源

19、。 2）利用非關鍵工序的時差，錯開各工序的開始時間。 3）統籌兼顧工程進度的要求和現有資源的限制，多次綜合平衡。 下面列舉一個拉平資源需要量最高峰的實例。在例5中，若加工工人 為65人，并假定這些工人可完成這5個工序任一個，下面來尋求一個時間- 資源最優(yōu)方案。如表12-16所示：,31,2統籌方法,表12-16,若上述工序都按最早開始時間安排，那么從第60天至第135天的75天里，所需的機械加工工人人數如圖12-17所示。,32,2統籌方法,在圖的上半部中，工序代號后的數字是人數，線下面的數字是非關鍵 工序時差長度。圖的下半部表示從第60天至135天內的75天里，所需機械 加工工人數，這樣的圖

20、稱為資源負荷圖。,2,7,4,6,3,5,f(22人）,18,h(39人),15,58人,64人,80人,81人,42人,26人,65人,60 80 100 120 130,d(58人）,i(26人）,g(42人）,30,20,25,圖12-17,33,2統籌方法,同時我們應優(yōu)先安排關鍵工序所需的工人，再利用非關鍵工序的時 差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經過調整，我 們讓非關鍵工序f從第80天開始，工序h從第110天開始。找到了時間-資源 優(yōu)化的方案，如圖12-18所示，在不增加工人的情況下保證了工程按期完 成。,2,4,6,7,5,3,f(22人）,h(39人）,d(5

21、8人）,i(26人）,g(42人）,工人數,65人,60 80 100 120 130,58人,42人,64人,26人,65人,圖12-18,34,2統籌方法,2.時間-費用優(yōu)化 需要考慮時間與費用的問題：在既定的時間前工程完工的前提下，使 得所需的費用最少，或者在不超工程預算的條件下使工程最早完工。這些 是時間-費用優(yōu)化要研究和解決的問題。 直接費用：為了加快工程進度，需要增加人力、設備和工作班次，這 需要增加一筆費用，成為直接費用。 間接費用：由于工程早日完工，減少了管理人員的工資辦公費等費用 稱為間接費用。一般說工序越短，直接費用越多，間接費用越少。,35,2統籌方法,工序的最快完成時間

22、：指完成時間的最高限度。 我們設完成工序j的正常所需時間為Tj;直接費用為cj;完成工序j的最快完成時 間為Tj,直接費用為cj。這樣我們可以計算出縮短工序j的一天工期所增加的直接 費用，用kj表示，稱為直接費用變動率。有 時間-費用優(yōu)化問題可建立兩個線性規(guī)劃模型。 模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少才使因 縮短工期而增加的直接費用最少。 設工序（i ,j)的提前完工時間為Yij,我們用Tij,Tij分別表示正常完工時間與最快 完工的時間，則有工序（i ,j)的實際完工時間為：Tij-Yij。我們用Cij,Cij表示用正 常完工時間和最快完成時間完成工序所需要的費用，

23、Kij為工序（i ,j)的直接費用 變動率。得到這個問題的線性規(guī)劃模型如下： minf= （Kij*Yij) （i,j) S.t. Xj-Xi Tij-Yij,對一切?。╥, j) Yij Tij-Tij, 對一切弧（i, j) Xn-X1 T, Xi 0， Yij 0。,36,2統籌方法,例7. 例5所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應正常完工時間與最快完工時間的所需的直接費用和每縮短一天工期所需增加的直接費用，如表12-17所示。 表12-17,37,2統籌方法,該工程要求在150天內完工，問每個工序應比正常完工時間提前多少

24、天 完成，才能使整個工程因縮短工期而增加的直接費用為最少。如果工期要 求在140天完工呢？,1,2,3,4,5,6,7,8,a,b,f,e,c,h,g,i,j,d,圖12-19,38,2統籌方法,解：繪出如圖12-19所示，根據此網絡圖建立數學模型。 設此網絡圖上第i點發(fā)生的時間為xi，工序提前完工的時間為yij。 目標函數minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67. s.t. x2-x1 60-y12, x7- x2 45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40虛擬弧（4，5） x7-x515-y57 x7-x625-y67,39,2統籌方法,x1 =0, y120