生產(chǎn)運作管理制造業(yè)作業(yè)計劃與控制ppt課件

1、第十一章 制造業(yè)作業(yè)方案與控制引言經(jīng)過MRP確定各車間的零部件投入出產(chǎn)方案，從而將全廠性的產(chǎn)品出產(chǎn)方案變成了各車間消費作業(yè)方案，將車間的消費義務(wù)變成各個班組、各個任務(wù)地和各個工人的義務(wù)。只需將方案安排到任務(wù)地和工人，義務(wù)才算真正落到實處。將義務(wù)安排到任務(wù)地，牽涉到義務(wù)分配和作業(yè)排序問題，這正是本章要討論的。 11.1 作業(yè)方案問題的根本概念11.2 流水作業(yè)排序問題11.3 單件作業(yè)的排序問題11.4 消費作業(yè)控制 11 收入、費用和利潤要求掌握：最長流程時間的計算2.約翰遜算法 3.普通流水作業(yè)排序問題的3種啟發(fā)式算法4. 一樣零件的3種挪動方式下機器加工周期的計算方法學(xué)習(xí)目的與要求 重點

2、最長流程時間的計算 約翰遜算法 一樣零件的3種挪動方式下機器加工周期的計算方法 難點 普通流水作業(yè)排序問題的啟發(fā)式算法教學(xué)重點與難點消費義務(wù)的最終落實MRP確定各車間的零部件投入出產(chǎn)方案，將全廠性的產(chǎn)品出產(chǎn)方案變成了各車間的消費義務(wù)。各車間要將車間的消費義務(wù)變成各個班組、各個任務(wù)地和各個工人的義務(wù)。將義務(wù)安排到任務(wù)地，牽涉到作業(yè)方案。編制造業(yè)方案要處理的問題由于每臺機器都能夠被分配了多項義務(wù)，就帶來了零件在機器上加工的順序問題。編制造業(yè)方案要處理先加工哪個工件、后加工哪個工件的加工順序問題確定機器加工每個工件的開場時間和完成時間例如;醫(yī)院要安排病人手術(shù)，為此要安排手術(shù)室，配備手術(shù)器械、手術(shù)醫(yī)師

3、和護士。第一節(jié) 排序問題的根本概念一、名詞術(shù)語排序：確定工件在機器上的加工順序。作業(yè)方案：不僅要確定工件的加工順序，而且還要確定機器加工每個工件的開場時間和完成時間。通常情況下都是按最早能夠開完工時間來編制造業(yè)方案。派工：按作業(yè)方案的要求，將詳細消費義務(wù)安排到詳細的機床上加工。趕工：實踐進度已落后于方案進度時采取的行動?！皺C器，可以是工廠里的各種機床，也可以是維修工人，表示“效力者“零件代表“效力對象。零件可以是單個零件，也可以是一批一樣的零件“加工順序那么表示每臺機器加工n個零件的先后順序，是排序和編制造業(yè)方案要處理的問題二、假設(shè)條件和符號闡明假設(shè)條件：1.一個工件不能同時在幾臺不同的機器上

4、加工。2.工件在加工過程中采取平行挪動方式，即當(dāng)上一道工序完工后，立刻送下道工序加工。3.不允許中斷。一個工件一旦開場加工，必需不斷進展到完工，不得中途停頓插入其他工件。4.每道工序只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間知，加工時間與加工順序無關(guān)。6.每臺機器同時只能加工一個工件有關(guān)符號Ji：工件i，i=1，2，nMj：機器j，j=1，2，npij為Ji在Mj上的加工時間ri為Ji的到達時間，指Ji從外部進入車間，可以加工的最早時間di為Ji的完工期限Ci為Ji的完工時間Cmax為最長完工時間Fi為Ji的流程時間，即工件在車間的實踐停留時間Fmax為最長流程時間Li為工件的延遲時間L

5、max為最長延遲時間三、排序問題的分類根據(jù)機器數(shù)的多少單臺機器的排序問題多臺機器的排序問題對于多臺機器排序問題，根據(jù)加工道路的特征，分成單件作業(yè)排序(Job - Shop)問題流水作業(yè)排序(Flow - Shop)問題工件的加工道路不同，是單件作業(yè)排序問題的根本特征；一切工件的加工道路完全一樣，是流水作業(yè)排序問題的根本特征。也就是說，每個零件都順序地經(jīng)過線上不同機器加工，它們的加工道路一致。根據(jù)工件到達系統(tǒng)的情況靜態(tài)排序動態(tài)排序根據(jù)參數(shù)的性質(zhì)確定型排序隨機型排序4參數(shù)法n/m/A/B其中，n為工件數(shù)m為機器數(shù)A車間類型。在A的位置假設(shè)標以標以“P，那么表示流水作業(yè)陳列排序問題；假設(shè)標以“G，那

6、么表示普通單件作業(yè)排序問題。當(dāng)m=1，那么A處為空白。B為目的函數(shù)，通常是使其值最小例如：n/3/P/Cmax四、作業(yè)排序方案的評價規(guī)范1.任務(wù)流程時間從工件可以開場加工至完工的時間，包括在各個機器之間的挪動時間、等待時間、加工時間以及由于機器缺點、部件無法得到等問題引起的延誤時間等。2. 加工周期完成一組任務(wù)所需的全部時間。它是從第一個工件在第一臺機器上開場加工時算起，到最后一個工件在最后一臺機器上完工時為止所經(jīng)過的時間。3.在制品庫存WIP在制品是對介于原資料和廢品之間的消費過程中的產(chǎn)品的稱謂。一個工件正從一個任務(wù)地移向另一個，由于一些緣由被拖延加工，正在被加工或放置于零件庫中，都可以看作

7、在制品庫存。4.利用率用一臺機器或一個工人的有效消費時間占總?cè)蝿?wù)時間的百分比來表示。五、優(yōu)先調(diào)度規(guī)那么調(diào)度方法：所謂調(diào)度方法，就是運用假設(shè)干涉先規(guī)定的優(yōu)先順序規(guī)那么，依次決議下一個應(yīng)被加工的工件的排序方法。一個任務(wù)地可選擇的下一個工件會有很多種，因此，按什么樣的準那么來選擇，對排序方案的優(yōu)劣有很大影響。常用的優(yōu)先順序規(guī)那么：FCFS規(guī)那么 優(yōu)先選擇最早進入可排序集合的工件。EDD規(guī)那么 優(yōu)先選擇完工期限最緊的任務(wù)。SPT規(guī)那么 優(yōu)先選擇加工時間最短的工件。SCR規(guī)那么 優(yōu)先選擇臨界比最小的工件。臨界比為任務(wù)允許停留時間和工件余下加工時間之比。MWKR規(guī)那么 優(yōu)先選擇余下加工時間最長的工件。LW

8、KR規(guī)那么 優(yōu)先選擇余下加工時間最短的工件。MOPNR規(guī)那么 優(yōu)先選擇余下工序數(shù)最多的工件。RANDOM規(guī)那么 隨機地挑選下一個工件。普通作業(yè)排序的目的滿足顧客或下一道工序的交貨期要求流程時間最短預(yù)備時間最短或本錢最小化在制品庫存最低機器設(shè)備或勞動力利用最大化例 一個加工車間擔(dān)任加工發(fā)動機機殼，如今共有5個機殼等待加工。只需一名技工在崗，做此項任務(wù)。如今曾經(jīng)估算出各個機殼的規(guī)范加工時間，顧客也曾經(jīng)明確提出了他們所希望的完工時間。下表顯示了周一上午的情況，顧客的取貨時間用從周一上午開場，還有多少任務(wù)小時來計算。發(fā)動機機殼所需標準加工時間（包括機器調(diào)整）預(yù)計顧客取貨時間（從現(xiàn)在開始算起的所需工作時

9、間）機殼1810機殼2612機殼31520機殼4318機殼51222機殼加工次序開始工作加工時間結(jié)束工作流程時間預(yù)計顧客取貨時間顧客實際取貨時間提前小時數(shù)拖延小時數(shù)機殼40333181815機殼2369912123機殼198171710177機殼51712292922297機殼329154444204424總數(shù)1021201838平均數(shù)20.43.67.6平均在制品庫存=102/44=2.32個 平均總庫存=120/44=2.73個SPT規(guī)那么排序結(jié)果 顧客實踐取貨時間基于以下假設(shè)：顧客不會在預(yù)定取貨時間之前來取貨；假設(shè)有拖延發(fā)生，他們將在加工終了時馬上取走。流程時間=等待時間+加工時間平均在

10、制品庫存=各工件流程時間之和加工周期平均總庫存=各工件實踐取貨時間之和加工周期機殼加工次序開始工作加工時間結(jié)束工作流程時間預(yù)計顧客取貨時間顧客實際取貨時間提前小時數(shù)拖延小時數(shù)機殼1088810102機殼286141412142機殼4143171718181機殼317153232203212機殼532124444224422總數(shù)115118336平均數(shù)23.00.67.2平均在制品庫存=115/44=2.61個 平均總庫存=118/44=2.68個EDD規(guī)那么排序結(jié)果 顧客實踐取貨時間基于以下假設(shè)：顧客不會在預(yù)定取貨時間之前來取貨；假設(shè)有拖延發(fā)生，他們將在加工終了時馬上取走。 比較SPT規(guī)那么和

11、EDD規(guī)那么的排序結(jié)果，用SPT規(guī)那么排序，其平均流程時間更短，在制品庫存更少。用EDD規(guī)那么，可以給顧客提供更好的效力平均延遲時間較少，它也提供了更低的總庫存程度。優(yōu)先調(diào)度法那么按SPT法那么可使工件的平均流程時間最短，從而減少在制品量。FCFS法那么來自排隊論，它對工件較公平。EDD法那么可使工件延誤時間最小。MWKR法那么使不同任務(wù)量的工件的完工時間盡量接近。LWKR法那么，使任務(wù)量小的工件盡快完成。第二節(jié) 流水作業(yè)排序問題流水作業(yè)排序問題的根本特征是每個工件的加工道路都一致。加工道路一致，是指工件的流向一致，并不要求每個工件必需經(jīng)過加工道路上每臺機器加工。對于流水作業(yè)排序問題，工件在不

12、同機器上的加工順序不盡一致。陳列排序問題：一切工件在各臺機器上的加工順序都一樣的情況。一、最長流程時間Fmax的計算n/m/P/Fmax問題，n個零件要按一樣的加工道路經(jīng)過m臺機器加工，目的是使這批零件的最長流程時間最短。最長流程時間又稱加工周期，它是從第一個零件在第一臺機器開場加工時算起，到最后一個零件在最后一臺機器上完成加工時為止所經(jīng)過的時間。例 有一個6/4/P/Fmax問題，其加工時間如下表所示。當(dāng)按順序S=6，1，5，2，4，3加工時，求Fmax。i123456423142456745587555424331ipi1pi2pi3pi46152432551445444532582175

13、33674261012131671115202733121722303542132125323846二、兩臺機器排序問題兩個或更多的作業(yè)必需在兩臺機器上以一樣的工序進展加工，要使加工周期最短，約翰遜于1954年提出了一個有效算法，那就是著名的Johnson算法。約翰遜算法包括以下幾個步驟：1列出每個作業(yè)在兩臺機器上的加工時間。2選擇最短的加工時間，假設(shè)有兩個一樣的值，那么任選一個。3假設(shè)最短的加工時間來自第一臺機器，那么先完成這個作業(yè)；假設(shè)來自第二臺機器，那么這個作業(yè)就放在最后完成。然后從加工時間矩陣中劃去已排序工件的加工時間。4對于剩余的作業(yè)反復(fù)第二步和第三步，直到整個排序完成。 【例】求如

14、表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474.5將零件2排第1位 2將零件3排第6位 2 3將零件5排第2位 2 5 3將零件6排第3位 2 5 6 3將零件4排第5位 2 5 6 4 3將零件1排第4位 2 5 6 1 4 3【例 題】有5件義務(wù)都需求兩步操作先1后2來完成，下表給出了相應(yīng)的時間：1根據(jù)Johnson算法安排任務(wù)順序；2計算加工周期。任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.0

15、1.6D3.03.0E3.51.5A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2iCBDEA操作1操作2【例 題】根據(jù)Johnson算法求以下8/2/F/Fmax問題的最優(yōu)解。任務(wù)aibiA96B72C103D81EFGH215458741. 將一切ai bi的工件按ai值不減的順序排成一個序列A；2. 將aibi的

16、工件按bi值不增的順序排成一個序列B；3. 將A放到B之前，就構(gòu)成了一個最優(yōu)加工順序。改良算法工件號 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4工件最優(yōu)順序：2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 2 4 8 13 18 263 11 15 22 26 28 ai bi 最優(yōu)順序下的加工周期為28練 習(xí)某公司要消費4種產(chǎn)品，需求兩臺機器1和2。其中，有3種產(chǎn)品需求先在機器1上加工。下表給出了兩臺機器上加工各產(chǎn)品所需的時間。1安排消費順序，使得在最短時間內(nèi)完成消費。2機器1共需任務(wù)多長時間？3機器2應(yīng)該在機器1開場任務(wù)后多長時間

17、開場運轉(zhuǎn)？任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.10任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.109.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65機器1機器2三、普通n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法是一個基于直觀或閱歷構(gòu)造的算法，在可接受的破費(時間、占用空間等)下給出待處理組合優(yōu)化問題的可行解 。啟發(fā)式方法因其易于實現(xiàn)、計算復(fù)雜度低等緣由，目前運用得最為

18、廣泛。 一Palmer法1965年，DSPalmer提出按斜度目的陳列工件的啟發(fā)式算法，稱之為 Palmer法。 工件的斜度目的可按下式計算： k=l，2，m 式中，m為機器數(shù)；pik為工件i在Mk上的加工時間。按照各工件i不增的順序陳列工件，可得出令人稱心的順序。例 有一個4/3/F/Fmax問題，其加工時間如下表所示，試用帕爾默法求最優(yōu)順序。i1234Pi11263Pi28429Pi34582解：對于本例， i =Pi1Pi3于是，1 = P11P13=14=3 2 = P21P23=25=3 3 = P31P33=68=2 4 = P41P43=32=1 按i 不增的順序陳列工件，得到加

19、工順序(1，2，3，4)和(2，1，3，4)，恰好這兩個順序都是最優(yōu)順序。如不是這樣，那么從中挑選較優(yōu)者。在最優(yōu)順序下， F max =28。二關(guān)鍵零件法步驟如下：1計算每個零件的總加工時間，找出加工時間最長的零件C，將其作為關(guān)鍵零件。2對于余下的零件，假設(shè)pi1pim，那么按pi1不減的順序排成一個序列Sa；假設(shè)pi1pim，那么按pim不增的順序排成一個序列Sb。3順序Sa，C，Sb即為所求順序。i1234pi11263pi28429pi34582pi13111614例 有一個4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。解：總加工時間最長的為3號零件， pi1

20、pi3的零件為1和2，按pi1不減的順序排成Sa=1，2； pi1pi3的零件為4號零件，Sb=4,這樣得到的加工順序為1，2，3，4。例 題用關(guān)鍵工件法求解下表的最優(yōu)排序。解：總加工時間最長的為2號零件，pi1pi4的零件為1和3，按pi1不減的順序排成sa=1，4；pi1pi4的零件為4號零件，sb=3，這樣得到的順序為1，4，2，3。i1234pi11954pi25763pi34635pi46237i1234pi11954pi25763pi34635pi46237pi16241719三CDS法康坎貝爾-杜德克-史密斯三人提出了一個啟發(fā)式算法，簡稱CDS法。詳細做法是，對加工時間用John

21、son算法求m-1次加工順序，取其中最好的結(jié)果。m=2時，l=1,加工時間分別為pi1和pi2；m=3時，l=1,2,加工時間分別為：1l=1，pi1和pi32l=2,pi1+pi2和pi2+pi3m=4時，l=1，2，3，加工時間分別為：1l=1,pi1和pi42l=2，pi1+pi2和pi3+pi43l=3，pi1+pi2+pi3和pi2+pi3+pi4lA加工時間B加工時間1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tmi1234Pi11263Pi28429Pi34582i1234l=1pi11263pi3458

22、2l=2pi1+pi296812pi2+pi31291011i1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi31291011當(dāng)l=1時，按Johnson算法得到加工順序1，2，3，4；當(dāng)l=2時，得到加工順序2，3，1，4。對于2，3，1，4，相應(yīng)的Fmax=29。所以，取順序1，2，3，4。用Palmer法、關(guān)鍵工件法和CDS法求以下4/4/P/Fmax問題的最優(yōu)解，并比較三種方法的結(jié)果。i1234pi11954pi25763pi34635pi46237四、一樣零件、不同挪動方式下加工周期的計算排序問題針對的是不同零件，假設(shè)n個零件一樣，那么沒有排序問題

23、。但零件在加工過程中采取的挪動方式不同，會導(dǎo)致一批零件的加工周期不同。三種典型的挪動方式順序挪動方式(串行工程)平行挪動方式平行工程平行順序挪動方式一順序挪動方式加工周期時間工序 1 2 3 4順序挪動方式 一批零件在上道工序全部加工終了后才整批地轉(zhuǎn)移到下道工序繼續(xù)加工。 設(shè)零件批量為n件，工序數(shù)目為m，一批零件不計算工序間運輸時間，只思索加工時間，設(shè)其加工的周期為T分鐘，零件在i道工序的單件工時為 ti 分鐘/件，i=1.2n。 那么該批零件的加工周期為： 知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘，那么T順=410+5+15+10=160分鐘二平行挪動方式工序

24、1 2 34時間 加工周期 每個零件在前道工序加工終了后，立刻轉(zhuǎn)移到后道工序去繼續(xù)加工，構(gòu)成前后工序交叉作業(yè)。零件平行挪動的加工周期 為：知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘，那么T平=10+5+15+10+4-115=85分鐘三平行順序挪動方式既要求每道工序延續(xù)進展加工，又要求各道工序盡能夠平行地加工。 時間工序1234 加工 周期1當(dāng)titi+1時，零件按平行挪動方式轉(zhuǎn)移；2當(dāng)titi+1時，以i工序最后一個零件的完工時間為基準，往前推移n-1ti+1作為零件在i+1工序的開場時間。詳細做法1當(dāng)titi+1時，零件按平行挪動方式轉(zhuǎn)移；2當(dāng)titi+1時，以

25、i工序最后一個零件的完工時間為基準，往前推移n-1ti+1作為零件在i+1工序的開場時間。平行順序挪動加工周期計算知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘，那么T平順=410+5+15+10-4-15+5+10=100分鐘例知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘。求三種挪動方式下的加工周期。解：T順=410+5+15+10=160分鐘T平=10+5+15+10+4-115=85分鐘T平順=410+5+15+10-4-15+5+10=100分鐘比較項目平行移動平行順序移動順序移動生產(chǎn)周期短中長運輸次數(shù)多中少設(shè)備利用差好好組織管理中復(fù)雜

26、簡單零件三種挪動方式的比較知m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分別求在順序挪動、平行挪動和平行順序挪動方式下，這批零件的加工周期。第三節(jié) 單件作業(yè)排序問題11.3.1 指派問題11.3.2 單件作業(yè)排序問題的描畫11.3.3 兩種作業(yè)方案的構(gòu)成11.3.4 求解普通n/m/G/Fmax問題的啟發(fā)式方法1、指派問題的方式表述給定了一系列所要完成的義務(wù)tasks以及一系列完成義務(wù)的被指派者assignees，所需求處理的問題就是要確定出哪一個人被指派進展哪一項義務(wù) 2、指派問題的假設(shè)被指派者的數(shù)量和義務(wù)的數(shù)量是一樣的每一個被指派者只完成一項義務(wù) 每一項義務(wù)只能由

27、一個被指派者來完成 每個被指派者和每項義務(wù)的組合有一個相關(guān)本錢 目的是要確定怎樣進展指派才干使得總本錢最小 11.3.1 指派問題設(shè)n 個人被分配去做n 件任務(wù)，每人只能完成一項義務(wù)，每項義務(wù)只能由一人完成。知第i 個人去做第j 件任務(wù)的的效率為Cij(i=1.2n;j=1.2n)并假設(shè)Cij 0。問應(yīng)如何分配才干使總效率 時間或費用最高？3、指派問題模型The Model for Assignment Problem典型問題 例1：有一份闡明書，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個人去完成，因各人專長不同，他們完成翻譯不同文字所需求的時間小時如表所示。規(guī)定每項任務(wù)只能交與

28、其中的一個人完成，每個人只能完成其中的一項任務(wù)。 問：如何分配，能使所需的總時間最少？甲 乙 丙 丁任務(wù)人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16 114 15 13 9 建立模型設(shè) xij=10假設(shè)第i項任務(wù)交與第j個人完成假設(shè)第i項任務(wù)不交與第j個人完成譯英文：x11+ x12 + x13 + x14 =1譯日文：x21+ x22 + x23 + x24 =1譯德文：x31+ x32 + x33 + x34 =1譯俄文：x41+ x42 + x43 + x44 =1甲：x11+ x21 + x31 + x41 =1乙：x12+ x22 + x32 + x4

29、2 =1丙：x13+ x23 + x33 + x43 =1?。簒14+ x24 + x34 + x44 =1xij =0或1 (i=1,2,3,4; j=1,2,3,4)甲 乙 丙 丁任務(wù)人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16 114 15 13 9 4、指派問題的匈牙利解法2497第1步：變換指派問題的系數(shù)矩陣cij，使各行各列中都出現(xiàn)0元素(1) 從cij的每行元素都減去該行的最小元素；(2)再從所得新系數(shù)矩陣無零元素的列中減去該列的最小元素。42在變化后的效率矩陣中找盡能夠多的獨立0元素，假設(shè)能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xi

30、j)中的元素為1，其他為0，這就得到最優(yōu)解。第2步：進展試指派，即確定獨立零元素1從有獨一的零元素的行或列開場確定獨立零元素，并用 表示，并劃掉其所在行或列的其他零。直到盡能夠多的零元素都被圈出和劃掉為止。02假設(shè)獨立零元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。假設(shè)m n, 那么轉(zhuǎn)入下一步。例2 有甲、乙、丙、丁四個工人，要分別派他們完成四項不同的義務(wù)，分別記作A、B、C、D。他們完成各項義務(wù)所需時間如下表所示，問如何分派義務(wù)，可使總時間最少？ 義務(wù)人員ABCD甲67112乙4598丙31104丁5982第1步，變換系數(shù)矩陣：-5第2步，確定獨立零元素 找到 3 個獨立零元素

31、， 但 m = 3 n = 4求解過程如下 第3步，作最少的直線覆蓋一切零元素： (5)對沒有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋一切零元素的最少直線數(shù)(1)對沒有獨立零元素的行打號；(2)對已打號的行中一切含劃掉零元素的列打號；(3)再對打有號的列中含獨立零元素的行打號；(4)反復(fù)(2)，(3)直到得不出新的打號的行、列為止；第4步：在沒有被直線覆蓋的一切元素中找出最小元素，然后將所在行或列都減去這最小元素；在出現(xiàn)負數(shù)的列或行都加上這最小元素以保證系數(shù)矩陣中不出現(xiàn)負元素。新系數(shù)矩陣的最優(yōu)解和原問題仍一樣。轉(zhuǎn)回第2步。 -511.3.2 問題的描畫加工描畫矩陣D為D=1,1,1 1,

32、2,3 1,3,22,1,3 2,2,1 2,3,2 對于普通單件作業(yè)排序問題，每個工件都有其獨特的加工道路，工件沒有一定的流向。要描畫一道工序，需求用三個參數(shù)：3個參數(shù)：i，j和k。i表示工件代號，j表示工序號，k表示完成工序i的第j道工序的機器代號。i，j，k表示工件i的第j道工序在機器k上進展。11.3.3 兩種作業(yè)方案的構(gòu)成各工序都按最早能夠完工時間安排的作業(yè)方案稱為能動作業(yè)方案。各工序都按最早能夠開場時間安排的作業(yè)方案稱為無延遲作業(yè)方案。無延遲作業(yè)方案是沒有任何延遲出現(xiàn)的能動作業(yè)方案。符號闡明每安排一道工序稱為一“步St:t步之前已排序工序構(gòu)成的部分作業(yè)方案；Ot:t步可排序工序的集

33、合；Tk為Ot中工序Ok的最早能夠開場時間；Tk為Ot中工序Ok的最早能夠完成時間。一能動作業(yè)方案的構(gòu)成步驟1設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。2求T* = minTk,并求出T*所出現(xiàn)的機器M*。假設(shè)M*有多臺，那么任選一臺。3從Ot中選出滿足以下兩個條件的工序Oj：需求M*加工，且Tj T* 。4將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1.5假設(shè)還有未安排的工序，轉(zhuǎn)步驟2；否那么，停頓。例 有一個2/3/G/Fmax問題，其加工描畫矩陣D和加工時間矩陣T分別為：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3

34、,2T=2 4 13 4 5試構(gòu)成一個能動作業(yè)方案。能動作業(yè)方案的構(gòu)成2,3,2M2131382,3,261,3,2M28812771,3,22,3,252,2,1M1787731,3,22,2,141,2,3M3777331,2,32,2,132,1,3M3363201,2,32,1,321,1,1M1223001,1,12,1,31OjM*T*TkTkOtt能動作業(yè)方案的甘特圖2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70時間機器 M1M2M3二無延遲作業(yè)方案構(gòu)成步驟1設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。2求T* = m

35、inTk,并求出T*所出現(xiàn)的機器M*。假設(shè)M*有多臺，那么任選一臺。3從Ot中選出滿足以下兩個條件的工序Oj：需求M*加工，且Tj=T* 。4將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1。5假設(shè)還有未安排的工序，轉(zhuǎn)步驟2；否那么，停頓。無延遲作業(yè)方案的構(gòu)成1,3,2M21213121,3,262,3,2M2M277812771,3,22,3,252,2,1M1387731,3,22,2,141,2,3M3M13377331,2,32,2,132,1,3M3063201,2,32,1,321,1,1M1M30023001,1,12,1,31OjM*T*T

36、kTkOtt無延遲作業(yè)方案的甘特圖2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 13 2 3 70時間機器 M1M2M31,3,2能動作業(yè)方案和無延遲作業(yè)方案雖然不一定是最優(yōu)作業(yè)方案，但普通是較好的作業(yè)方案，特別是無延遲作業(yè)方案能提供令人稱心的解。普通能動作業(yè)方案和無延遲作業(yè)方案都有多個。普通來說，以構(gòu)成無延遲作業(yè)方案的步驟為根底的啟發(fā)式算法比以構(gòu)成能動作業(yè)方案的步驟為根底的啟發(fā)算法的效果要好。練 習(xí)1.南希汽車座椅罩和噴漆工廠正在競標一份為愛得舊車買賣所提供全部客戶效力的合同。獲得合同的主要要求是快速交貨。愛得說，假設(shè)南希廠可以在24小時內(nèi)將愛得收到的5輛車全部整

37、修并且重新噴漆，合同就歸該廠。下面是這5輛車在整修和噴漆車間各自需求的時間。假定車子在重新噴漆前要經(jīng)過重新整修的步驟，南希廠可以滿足時間要求并且得到合同嗎？汽車整修時間（小時）重新噴漆時間（小時）A63B04C52D86E212.有一個2/3/G/Fmax問題，其加工描畫矩陣D和加工時間矩陣T分別為：試構(gòu)成一個能動作業(yè)方案和無延遲作業(yè)方案。D=1,1,1 1,2,3 1,3,22,1,3 2,2,2 2,3,1T=3 5 22 4 34，1，2M20604，1，20403，1，11182，2，11251，2，230604，1，20403，1，11182，2，11，1，1M10501，1，120

38、604，1，20403，1，12，1，3M30802，1，30501，1，11OjM*T*T kTkOtt1694，3，11393，2，41292，2，11，2，2M261361，2，264，2，4M46864，2，41393，2，41292，2，161361，2，25864，2，43，1，1M15953，1，11182，2，11361，2，24OjM*T*T kTkOtt4，3，1M11219124，3，118133，3，317132，3，419131，3，3919124，3，13，2，4M491393，2，416122，3，419131，3，3891694，3，191393，2，42，2，

39、1M191292，2，119131，3，37OjM*T*T kTkOtt22194，4，31819183，4，21827182，4，31，3，3M31824181，3，31222194，4，33，3，3M31318133，3，326172，4，31319131，3，31122194，4，31318133，3，32，3，4M41317132，3，41319131，3，310OjM*T*T kTkOtt2，4，3M32736272，4，34，4，3M32427244，4，32433242，4，32427244，4，32433242，4，31，4，4M42426241，4，41427244，4，33

40、，4，2M21819183，4，233242，4，326241，4，413OjM*T*T kTkOtt151611.3.3 求解普通n/m/G/Fmax問題的啟發(fā)式方法三類啟發(fā)式算法：優(yōu)先調(diào)度法那么隨機抽樣法概率調(diào)度法1.優(yōu)先調(diào)度法那么SPTShortest processing time法那么優(yōu)先選擇加工時間最短的工序可使工件的平均流程時間最短，從而減少在制品量FCFSFirst come first served法那么優(yōu)先選擇最早進入可排工序集合的工件來自排隊論，對工件較公平EDDEarliest due date法那么優(yōu)先選擇完工期限緊的工件可使工件最大延誤時間最小MWKRMost wo

41、rk remaining法那么優(yōu)先選擇余下加工時間最長的工件不同任務(wù)量的工件的完工時間盡量接近1.優(yōu)先調(diào)度法那么續(xù)LWKRLeast work remaining法那么優(yōu)先選擇余下加工時間最短的工件使任務(wù)量小的工件盡快完成MOPNRMost operations remaining法那么優(yōu)先選擇余下工序數(shù)最多的工件與MWKR法那么類似，只不過思索工件在不同機器上的轉(zhuǎn)運排隊時間是主要的SCRSmallest critical ratio法那么優(yōu)先選擇臨界比最小的工件臨界比：工件允許停留時間與工件余下加工時間之比保證工件延誤最少RANDOM法那么隨機地挑一個工件2.隨機抽樣法隨機抽樣法實踐上是對同一個問題多次運用RANDOM法那么來決議要挑選的工序