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

應該按照什么樣的加工順序來加工這六個零件，才能使得這六個零件在車間里停留的平均時間為最少？零件加工時間（小時）零件加工時間（小時）1231.82.00.54560.91.31.53§1車間作業計劃模型

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

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？這就是我們最后要解決的優化問題，而且我們要設法找到一種簡便的算法。對于某種加工順序，我們知道安排在第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個零件的排序問題，只要系數越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。4§1車間作業計劃模型二、兩臺機器、n個零件

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

應該如何安排這五個零件的先后順序才能使完成這五個零件的總的加工時間為最少？解：由于每個零件必須先進行車床加工，再進行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和車床、磨床在每個時間段的狀況的圖形所構成。零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.255§1車間作業計劃模型圖12-1從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件加工任務所需總時間最少的零件排序方法。123451車床磨床23450106§1車間作業計劃模型尋找例2的最優解：我們在表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，這是車床加工零件3的所需時間，故把零件3排在第二位上，同時把零件3所在的行劃去。如表12-6中黑色線條所示。這樣就得到了最優加工順序：5，3，4，1，2。一共只需7個小時就能完成全部加工。從例2中我們可以歸納出關于兩臺機器n個零件的排序問題，使得全部任務總的時間最短的排序算法。在加工所需時間表上選出最短加工時間tij，這是第i工序加工j零件所需時間，當i=1時，將零件j的順序盡量靠前，若i=2時，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1?！?車間作業計劃模型8§2統籌方法統籌方法包括繪制計劃網絡圖、進度安排、網絡優化等環節，下面進行分別討論：一、計劃網絡圖統籌方法的第一步工作就是繪制計劃網絡圖，也就是將工序（或稱為活動）進度表轉換為統籌方法的網絡圖。例3、某公司研制新產品的部分工序與所需時間以及它們之間的相互關系都顯示在其工序進度表如表12-8所示，請畫出其統籌方法網絡圖。表12-8工序代號工序內容所需時間（天)緊前工序abcde產品設計與工藝設計外購配套零件外購生產原料自制主件主配可靠性試驗601513388-aacb,d9§2統籌方法解:用網絡圖表示上述的工序進度表網絡圖中的點表示一個事件,是一個或若干個工序的開始或結束,是相鄰工序在時間上的分界點,點用圓圈表示,圓圈里的數字表示點的編號。弧表示一個工序（或活動），弧的方向是從工序開始指向工序的結束，弧上是各工序的代號，下面標以完成此工序所需的時間（或資源）等數據，即為對此弧所賦的權數．

１２４５３abcde601383815圖12-410§2統統籌方法法例４、把把例３的的工序進進度表做做一些擴擴充，如如表12-9，，請畫出出其統籌籌方法的的網絡圖圖。表12-9工序代號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ11§2統統籌方法法解：我們們把工序序ｆ擴充充到圖12-4發生了了問題，，由于ｄｄ是ｆ的的緊前工工序，故故ｄ的結結束應該該是ｆ的的開始，，所以代代表ｆ的的弧的起起點應該該是④，，由于工工序ｂ的的結束也也是④，，所以工工序ｂ也也成了工工序ｆ的的緊前工工序，與與題意不不符。為此我們們設立虛虛工序。。虛工序序是實際際上并不不存在而而虛設的的工序，，用來表表示相鄰鄰工序的的銜接關關系，不不需要人人力、物物力等資資源與時時間。152643a60b158e1013dc38f圖12-512§2統統籌方法法在網絡圖圖上添加加ｇ、ｈｈ工序得得網絡圖圖12-6。在統籌方方法的網網絡圖中中不允許許兩個點點之間多多于一條條弧，因因此增加加了一個個點和虛虛工序如如圖12-7。。1256734a6015bec13d388h510fg16圖12-613§2統統籌方法法在繪制統統籌方法法的網絡絡圖時，，要注意意圖中不不能有缺缺口和回回路。1257834a6015bec13d388h510f616g圖12-714§2統統籌方法法二、網絡絡時間與與關鍵路路線在繪制出出網絡圖圖之后，，我們可可以由網網絡圖求求出：1、完成成此工程程項目所所需的最最少時間間。2、每個個工序的的開始時時間與結結束時間間。3、關鍵鍵路線及及其應用用的關鍵鍵工序。。4、非關關鍵工序序在不影影響工程程的完成成時間的的前提下下，其開開始時間間與結束束時間可以推推遲多久久。例5、某某公司裝裝配一條條新的生生產線，，具體過過程如表表12-10,求：完完成此工程的最最少時間間，關鍵鍵路線及及相應的的關鍵工工序，各各工序的的最早開開始時間間和非關鍵工工序在不不影響工工程完成成時間的的前提下下，其開開始時間間與結束束時間可可以推遲多久久。15§2統統籌方法法表12-10工序代號工序內容所需時間（天）緊前工序abcdefghij生產線設計外購零配件下料、鍛件工裝制造1木模、鑄件機械加工1工裝制造2機械加工2機械加工3裝配調試60451020401830152535/aaaacdd,egb,i,f,h16§2統統籌方法法解：據表表12-10,繪制網網絡圖如如圖12-8。。圖12-8如圖12-8,①-②-③③-⑦-⑧就是是一條關關鍵路線線，我們們要干完完所有的的工序就必須走走完所有有這樣的的路線，，由于很很多工序序可以同同時進行行，所以以網絡中中最長的路線線就決定定了完成成整個工工程所需需的最少少時間，，這條路路線稱為為關鍵路路線。12346785a60b45echj35ig1030d204025f181517§2統統籌方法法下面我們們給出找找關鍵路路線的辦辦法首先，從從網絡的的發點開開始，按按順序計計算出每每個工序序的最早早開始時時間（ES)和最最早結束束時間（（EF)，設設一個工工序所需需的時間間為t，，這對于于同一個工序來來說，有有EF=ES+t。。工序a的的最早開始時間間工序a的的最早完成時間間11a[0，，60]60圖12-918§2統統籌方法法圖12-10其次,從從網絡的的收點開開始計算算出在不不影響整整個工程程最早結結束時間間的情況下各個個工序的的最晚開開始時間間(縮寫寫為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統統籌方法法運用此法法則，可可以從首首點開始始計算出出每個工工序的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統統籌方法法最后將各各工序的的時差，，以及其其他信息息構成工工序時間間表如表表12-11所所示。這樣就找找到了一一條由關關鍵工序序a,d,g,i和j依次連連接成的的從發點點到收點點的關鍵路線線。21三、完成成工序所所需時間間與關鍵鍵路線當完成工工序所需需時間不不確定的的情況下下如何求求網絡時時間和關關鍵路線線？例6.長長征征研究院院培訓中中心負責責明年春春天的各各干部的的工商管管理培訓訓，培訓訓中心列列出有關關培訓組組織的各各項活動動的信息息如表12-12所示示，要求求繪制出出統籌方方法的網網絡圖，，設法求求出網絡絡時間和和關鍵路路線，并并確定開開始這個個組織工工作的時時間以保保證培訓訓工作如如期舉行行。解：由表表12-12，，繪出統統籌方法法的網絡絡圖如圖圖12-12所所示。12356487abecdfghi圖12-12§2統統籌方法法22§2統統籌方法法

活動（工序）活動（工序）內容緊前活動（工序）abcdefghi制定培訓計劃選聘培訓教師列出一些可供選擇的培訓地點確定培訓地點確定培訓的日程安排落實教學設備，器材，資料發培訓通知并確定學員名單訂旅館房間處理最后的一些事務-a-cb,deb,dgf,g23§2統統籌方法法由于是第第一次搞搞培訓，，缺乏統統計來確確定完成成每個活活動所需需時間，，但對所需需時間做做了三種種估計：：1.樂觀觀時間。。指所需需最少時時間，用用a表示示。2.最可可能時間間。指正正常時間間，用m表示。。3.悲觀觀時間。。指不順順利情況況下，最最多時間間，用b表示。。如表12-13所示示：表12-13單單位位：周活動樂觀時間最可能時間悲觀時間abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.524§2統統籌方法法顯然這三三種完成成活動所所需時間間都具有有一定概概率，由由經驗，，我們可可以可以假定定這些時時間的概概率分布布近似服服從分分布布。我們們可以用用如下公公式計算出完成成活動所所需的平平均時間間：以及方差差例如：完完成工作作g所需需平均時時間：同時求出出方差為為25§2統統籌方法法同樣可以以求出每每個活動動的完成成所需平平均時間間及方差差，如表表12-14：：表12-14活動T（平均時間）方差活動T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02826§2統統籌方法法下面就用用平均時時間代替替完成活活動所需需時間，，并在網網絡圖上上標上每每個活動最早開開始時間間和最早早結束時時間，如如圖12-14所示。。12345876同樣也可以以標上最晚晚開始時間間和最晚完完成時間等等。a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]32221424212345876a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]2[1,3]1[10,11]4[5,9]4[9,13]2[3,5]2[0,2]3[2,5]2[13,15]2[11,13]圖12-14圖12-1527§2統籌籌方法從表12-15上我我們找到了了一條從發發點到收點點由關鍵工工序a,b,g,h,i組成成的關鍵路線，，用雙線標標出來。則則完成培訓訓工作所需需的平均時時間為各關關鍵路線的時間之和和：=2+3+4+4+2=15（周）同時完成時時間近似服服從一定的的概率分布布正態分布布，則均值值為關鍵路路線上各關鍵活活動之均值值之和15，方差也也為關鍵路路線上各關關鍵活動方方差之和1.05。。由此我們可可以計算出出此項培訓訓組織工作作不同完工工時間的概概率，如16周內完工的概概率。為求此概率率，可以先先求u值。。式中的T為為預定完工工時間16，E（T）=15，算得u=0.976。查正態態分布函數數表可知概概率為0.8355。即16周內完工工的概率為83.55%.28§2統籌籌方法其正態分布布圖如圖12-16所示：16圖12-1629§2統籌籌方法四、網絡優優化得到初始的的計劃方案案，但通常常要對初始始方案進行行調整與完完善。根據據計劃目標，綜綜合考慮資資源和降低低成本等目目標，進行行網絡優化化，確定最最優的計劃方案。1.時間-資源優化化做法：1）優先安安排關鍵工工序所需的的資源。2）利用非非關鍵工序序的時差，，錯開各工工序的開始始時間。3）統籌兼兼顧工程進進度的要求求和現有資資源的限制制，多次綜綜合平衡。。下面列舉一一個拉平資資源需要量量最高峰的的實例。在在例5中，，若加工工工人為65人，，并假定這這些工人可可完成這5個工序任任一個，下下面來尋求求一個時間間-資源最優方方案。如表表12-16所示：：30§2統籌籌方法表12-16工序需要人數最早開始時間所需時間時差d5860200f22701847g428030h391001520i26110250若上述工序序都按最早早開始時間間安排，那那么從第60天至第第135天天的75天天里，所需需的機械加加工工人人人數如圖12-17所示。31§2統籌籌方法在圖的上半半部中，工工序代號后后的數字是是人數，線線下面的數數字是非關關鍵工序時差長長度。圖的的下半部表表示從第60天至135天內內的75天天里，所需需機械加工工人數數，這樣的的圖稱為資資源負荷圖圖。274635f(22人人）18h(39人人)1558人64人80人81人42人26人65人6080100120130d(58人人）i(26人人）g(42人人）302025圖12-1732§2統籌籌方法同時我們應應優先安排排關鍵工序序所需的工工人，再利利用非關鍵鍵工序的時時差，錯開各各工序的開開始時間，，從而拉平平工人需要要量的高峰峰。經過調調整，我們讓非關鍵鍵工序f從從第80天天開始，工工序h從第第110天天開始。找找到了時間間-資源優化的方案案，如圖12-18所示，在在不增加工工人的情況況下保證了了工程按期期完成。246753f(22人人）h(39人人）d(58人人）i(26人人）g(42人人）工人數65人608010012013058人42人64人26人65人圖12-1833§2統籌籌方法2.時間-費用優化化需要考慮時時間與費用用的問題：：在既定的的時間前工工程完工的的前提下，，使得所需的費費用最少，，或者在不不超工程預預算的條件件下使工程程最早完工工。這些是時間-費費用優化要要研究和解解決的問題題。直接費用：：為了加快快工程進度度，需要增增加人力、、設備和工工作班次，，這需要增加一一筆費用，，成為直接接費用。間接費用：：由于工程程早日完工工，減少了了管理人員員的工資辦辦公費等費費用稱為間接費費用。一般般說工序越越短，直接接費用越多多，間接費費用越少。。34§2統籌籌方法工序的最快快完成時間間：指完成成時間的最最高限度。。我們設完成成工序j的的正常所需需時間為Tj;直接費用用為cj;完成工序序j的最快快完成時間為T`j,直接費用用為c`j。這樣我們們可以計算算出縮短工工序j的一一天工期所所增加的直直接費用，用kj表示，稱為為直接費用用變動率。。有時間--費費用優化問問題可建立立兩個線性性規劃模型型。模型一，在在既定的時時間T完工工的前提下下，問各工工序的完成成時間為多多少才使因因縮短工期而而增加的直直接費用最最少。設工序（i,j)的提前完完工時間為為Yij,我們用Tij,T`ij分別表示正正常完工時時間與最快快完工的時間間，則有工工序（i,j)的的實際完工工時間為：：Tij-Yij。我們用Cij,C`ij表示用正常完工時間間和最快完完成時間完完成工序所所需要的費費用，Kij為工序（i,j)的直接費費用變動率。得得到這個問問題的線性性規劃模型型如下：minf=（Kij*Yij)（i,j)j-XiTij-Y`ij,對一切弧弧（i,j)YijTij-T`ij,對對一切弧?。╥,j)Xn-X1T,Xi0，Yij0。35§2統籌籌方法例7.例例5所所提供的信信息都作為為本例的信信息，另外外還給出了了在裝配過過程中各道道工序所需需正常完工工時間與最最快完工時時間，以及及對應正常常完工時間間與最快完完工時間的的所需的直直接費用和和每縮短一一天工期所所需增加的的直接費用用，如表12-17所示。表12-17工序Tij正常完工Cij直接費用T`ij最快完工C`ij直接費用直接費用變動率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-36§2統籌籌方法該工程要求求在150天內完工工，問每個個工序應比比正常完工工時間提前前多少天完成，才能能使整個工工程因縮短短工期而增增加的直接接費用為最最少。如果果工期要求在140天完工呢呢？12345678abfechgijd圖12-1937§2統籌籌方法解：繪出如如圖12-19所示示，根據此此網絡圖建建立數學模模型。設此網絡圖圖上第i點點發生的時時間為xi，工序提前前完工的時時間為yij。目標函數minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.2-x160-y12,x7-x24