1、第二節(jié) 流水作業(yè)排序問題,流水作業(yè)排序問題的基本特征是每個零件的加工路線都一致。即工件流向一致. 只要加工路線一致：M1， M2, M3，.，Mm,不要求每個零件都經(jīng)過每臺機(jī)器加工,一、最長流程時間Fmax的計(jì)算,最長流程時間又稱作加工周期 例題：6/4/p/ Fmax問題，當(dāng)按順序S( 6,1,5,2,4,3)加工時，求Fmax.,加工周期為46,表2順序S下的加工時間矩陣,i,6 1 5 2 4 3,i1,P,2,2,4,6,4,10,2,12,1,13,3,16,i2,5,7,4,11,4,15,5,20,7,27,6,33,5,12,5,17,5,22,8,30,5,35,7,42,1

2、,13,4,21,3,25,2,32,3,38,4,46,P,一、最長流程時間Fmax的計(jì)算,加工周期為37,表3順序S下的加工時間矩陣,i,1 2 3 4 5 6,i1,P,3,3,3,6,4,10,2,12,1,13,3,16,i2,2,5,5,11,4,15,3,18,7,25,6,31,5,10,4,15,5,20,7,27,5,32,4,36,1,11,2,17,3,23,2,29,3,35,1,37,P,課堂作業(yè)：求Fmax.,二、n/2/F/Fmax問題的最優(yōu)算法,（一）Johnson算法：從加工時間矩陣中找出最短的加工時間。若最短的加工時間出現(xiàn)在M1上，則對應(yīng)的零件盡可能往前排

3、；若最短加工時間出現(xiàn)在M2上，則對應(yīng)零件盡可能往后排。然后，從加工時間矩陣中劃去已排序零件的加工時間。若最短加工時間有多個，則任挑一個若所有零件都已排序，停止。否則，轉(zhuǎn)步驟。,例題：求表11-3所示的6/2/F/Fmax問題的最優(yōu)解。,最優(yōu)加工順序?yàn)镾=（2，5，6，1，4，3）。,課堂作業(yè)： Johnson法則，最優(yōu)排序！ 以及計(jì)算Fmax,（二）算法步驟的改進(jìn),把Johnson算法作些改變，改變后的算法按以下步驟進(jìn)行： 將所有aibi的零件按ai值不減的順序排成一個序列A。 將所有aibi的零件按bi值不增的順序排成一個序列B。 將A放到B之前，就構(gòu)成了最優(yōu)加工順序,序列A為 (2， 5，

4、6，1)，序列B為(4，3)，構(gòu)成最優(yōu)順序?yàn)?(2，5，6，1， 4，3)，與Johnson算法結(jié)果一致。,表,11,-,4,改進(jìn)算法,i,1,2,3,4,5,6,ai,5,1,8,5,3,4,bi,7,2,2,4,7,4,i,1,3,ai,5,8,bi,7,2,4,aibi， bi值不增,aibi， ai值不減,Johnson法則只是一個充分條件，不是必要條件。不符合這個法則的加工順序，也可能是最優(yōu)順序。如對例11-2順序(2，5，6，4，1，3)不符合Johnson法則，但它也是一個最優(yōu)順序 對于3臺機(jī)器的流水車間排序問題，只有幾種特殊類型的問題找到了有效算法。 對于一般的流水車間排列排序

5、問題，可以用分支定界法。,三、求一般n/m/P/ Fmax問題近優(yōu)解 (Near optimal solution)的啟發(fā)式算法,1、Palmer法：按斜度指標(biāo)排列工件的啟發(fā)式算法 工件的斜度指標(biāo)按下式計(jì)算：,m為機(jī)器數(shù)；Pik 為工件i在Mk 上的加工時間，k是機(jī)器編號，按照各工件i不增的順序排列工件,可得出滿意順序,例：有一個4/3/P/ Fmax 問題，其加工時間如下表所示，用Palmer法求解。,=(1-2) Pi1+(2-2) Pi2+(3-2) Pi3 =- P i1 + P i3,解,K=1,1 = - P 11 + P 13= -1+4 = 3 2 = -P21 + P23=

6、-2 + 5= 3 3 =- P31 + P33 = -6 + 8 = 2 4 =-P 41+P43 = -3 + 2 = -1,按i不增的順序排列，得到加工順序 （1，2，3，4）和（2，1，3，4）， 兩者均為最優(yōu)順序，F(xiàn)max=28。,i =- P i1 + P i3,作業(yè)：用Palmer法求解,2、關(guān)鍵工件法 （1）計(jì)算每個工件的總加工時間，找出加工時間最長的工件C，將其作為關(guān)鍵工件； （2）對于余下的工件若Pi1Pim，則按Pi1不減的順序排成一個序列Sa，若Pi1Pim，則按Pim不增的順序排列成一個序列Sb。 （3）順序（ Sa，C，Sb）即為所求順序。,關(guān)鍵工件法求近優(yōu)解舉例,

7、表11-6用關(guān)鍵零件法求解,i2,P,i3,p,i,1、找出最長時間 2、 Pi1Pim，則按Pi1不減 3、若Pi1Pim，則按Pim不增 4、組成（ Sa，C，Sb）,1，2,3,4,作業(yè)：用關(guān)鍵工件法求解,3、CDS法,Campbell-Dudek-Smith 三人提出了一個啟發(fā)式算法,簡稱CDS法。他們把Johnson算法用于一般的n/m/P/Fmax問題，得到(1)個加工順序，取其中優(yōu)者。,CDS法可以總結(jié)為： L=1時，求第1道和最后一道工序的加工時間矩陣 L=2時，求前2道和后2道工序的加工時間和的矩陣 L=3時，求前3道和后3道工序的加工時間和的矩陣 L=4時，求前4道和后4道

8、工序的加工時間和的矩陣 L=m-1，求前m-1道和后m-1道工序的加工時間和的矩陣,如：用CDS求機(jī)器數(shù)M為3時的加工順序。首先，計(jì)算L=1時的加工時間，,再計(jì)算L=2時的加工時間，,和,當(dāng)L1時，按Johnson算法得到加工順序(1，2，3，4)，相應(yīng)的Fmax28。 當(dāng)L2時，得到加工順序(2，3，1，4)。對于順序(2，3，1， 4)，相應(yīng)的Fmax29。 所以，取順序(1，2，3，4)。我們已經(jīng)知道，這就是最優(yōu)順序。,表,11-7,用,CDS,法求解,i,1 2 3 4,P,i1,1 2 6 3,L=1,P,i3,4 5 8 2,P,i1,+P,i2,9 6 8 12,L=2,P,i2

9、,+P,i3,12 9 10 11,作業(yè)： 用CDS法求解,四、相同零件、不同移動方式下加工周期的計(jì)算,零件在加工過程中可以采用三種典型的移動方式： 順序移動 平行移動 平行順序移動,例：一批制品，批量n =4件，須經(jīng)四道工序加工，各工序時間分別為：t1=10, t2=5, t3=15, t4=10。,n加工批量； m工序數(shù)目； ti工件在第i工序的單件工時；,四、相同零件、不同移動方式下加工周期的計(jì)算,一批零件在上道工序全部加工完畢后,才整批轉(zhuǎn)移 到下道工序加工。,n加工批量； m工序數(shù)目； ti工件在第i工序的單件工時；,工序,M1,M2,M3,M4,T順序,t2,t1,t3,t4,時間,

10、1、順序移動方式:,順序移動方式下的加工周期計(jì)算,順序移動方式下的加工周期計(jì)算,每個零件在前道工序加工完畢后，立即轉(zhuǎn)移到后 道工序去繼續(xù)加工，形成前后工序交叉作業(yè)。,工序,T平行,時間,M1,M2,M3,M4,2、平行移動方式,t1,t2,t4,平行移動方式下的加工周期計(jì)算,要求每道工序連續(xù)進(jìn)行，但又要求各道工序盡可能 平行地加工。,工序,M1,M2,M3,M4,T平順,t2,t1,t3,t4,時間,3、平行順序移動方式,工序,M1,M2,M3,M4,T平順,t2,t1,t3,t4,時間,第1種情況：ti ti+1 考慮平行性，實(shí)現(xiàn)交叉作業(yè),按平行移動方式的原則加工，即工件加工完成后立刻轉(zhuǎn)移到

11、下一個工序，此處，第2個工序的第1個工件加工完成后立刻轉(zhuǎn)移到第3個工序進(jìn)行加工。,3、平行順序移動方式,工序,M1,M2,M3,M4,T平順,t2,t1,t3,時間,第2種情況：ti ti+1 考慮設(shè)備加工的連續(xù)性,第1個工序的所有工件加工完成的時刻為基準(zhǔn)，向前推（n-1）個t2時間，作為第2個工序的開始時間。即從紅線開始向前推3個作為第2個工序的開始時間。,3、平行順序移動方式,x,T=nt1+t2+x+t4,X=nt3-(n-1)t2,T=n(t1+t2+t3+t4)-(n-1)(t2+t2+t4),Min(tj,tj+1)前后相鄰兩工序中單件工時之較小者,T=4(10+5+15+10)-

12、(4-1) (5+5+10)=100分鐘,工序,M1,M2,M3,M4,M5,T平順,t2,t1,t3,時間,加工周期的計(jì)算,Min(tj,tj+1)前后相鄰兩工序中單件工時之較小者,3、平行順序移動方式,第三節(jié) 單件作業(yè)排序問題,1、問題描述,用（i，j，k）表示工件i 的第j道工序在機(jī)器k上進(jìn)行。其中i表示工件代號，j表示工序號，k表示完成任務(wù)的機(jī)器代號。如加工描述矩陣D。,二、一般n/m/G/Fmax問題的算法,1、符號說明 Stt步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃； Ot 第t步可以排序的工序的集合； Tk Ot 中工序Ok的最早可能開工時間； Tk Ot 中工序Ok的最早可能完工時間

13、。,作業(yè)計(jì)劃構(gòu)成分類,能動作業(yè)計(jì)劃：各工序按最早可能完工時間安排的作業(yè)計(jì)劃。 無延遲作業(yè)計(jì)劃：各工序按最早可能開工時間安排的作業(yè)計(jì)劃。,2、能動作業(yè)計(jì)劃的構(gòu)成步驟:,設(shè)t1，S1為空集，O1為各工件第一道工序的集合。 求T*minTk，并求出T*出現(xiàn)的機(jī)器M*。如果M*有多臺，則任選一臺。Tk最早完成時間. 從Ot中挑出滿足以下兩個條件的工序Oj：需要機(jī)器M*加工，且TkT*。 Tk最早開工時間. 將確定的工序Oj放入St，從 Ot 中消去Oj，并將Oj的緊后工序放入 Ot ，使tt1。 若還有未安排的工序，轉(zhuǎn)步驟；否則，停止。,例題：,有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時

14、間矩陣T分別為：,試構(gòu)成一個能動作業(yè)計(jì)劃。,2,3,2,M2,13,13,8,2,3,2,6,1,3,2,M2,8,8 12,7 7,1,3,2 2,3,2,5,2,2,1,M1,7,8 7,7 3,1,3,2 2,2,1,4,1,2,3,M3 M1,7,7 7,3 3,1,2,3 2,2,1,3,2,1,3,M3,3,6 3,2 0,1,2,3 2,1,3,2,1,1,1,M1,2,2 3,0 0,1,1,1 2.1.3,1,Qj,M*,T*,Tk,Tk,Qt,t,解：Tk最早開工時間；Tk=最早完成時間；T*=最早完工時間中的最小者,1,1,1 1,2,3 1,3,2,D,2,1,3 2,

15、2,1 2,3,2,最優(yōu)作業(yè)計(jì)劃為： 1,1,1 2,1,3 1,2,3 2,2,1 1,3,2 2,3,2,3、無延遲作業(yè)計(jì)劃的構(gòu)成步驟:,設(shè)t1，S1為空集，O1為各工件第一道工序的集合。 求T*minTk，并求出T*出現(xiàn)的機(jī)器M*。如果M*有多臺，則任選一臺。Tk最早開始時間. 從Ot中挑出滿足以下兩個條件的工序Oj：需要機(jī)器M*加工，且TkT*。 將確定的工序Oj放入St，從 Ot 中消去Oj，并將Oj的緊后工序放入 Ot ，使tt1。 若還有未安排的工序，轉(zhuǎn)步驟；否則，停止。,1,3,2,M2,12,13,12,1,3,2,6,2,3,2,M2 M2,7 7,8 12,7 7,1,3

16、,2 2,3,2,5,2,2,1,M1,3,8 7,7 3,1,3,2 2,2,1,4,1,2,3,M3 M1,3 3,7 7,3 3,1,2,3 2,2,1,3,2,1,3,M3,0,6 3,2 0,1,2,3 2,1,3,2,1,1,1,M1 M3,0 0,2 3,0 0,1,1,1 2.1.3,1,Qj,M*,T*,Tk,Tk,Qt,t,解：,Tk最早開工時間；Tk=最早完成時間；T*=最早開工時間中的最小者,最優(yōu)作業(yè)計(jì)劃為： 1,1,1 2,1,3 1,2,3 2,2,1 2,3,2 1,3,2,三類啟發(fā)式算法1、優(yōu)先派工法則,按優(yōu)先調(diào)度法則挑選工序比隨意挑選一道工序的方法更能符合計(jì)劃

17、編制者的要求，同時又不必列出所有可能的作業(yè)計(jì)劃，從而計(jì)算量小。 迄今，人們已提出了100多個優(yōu)先調(diào)度法則，其中主要的有下8個： SPT(Shortest Processing Time)法則優(yōu)先選擇加工時間最短的工序。 FCFS(First Come First Served)法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件。,優(yōu)先派工法則(續(xù)),EDD(Earliest Due Date)法則優(yōu)先選擇完工期限緊的工件。 MWKR(Most Work Remaining)法則優(yōu)先選擇余下加工時間最長的工件。 LWKR(Least Work Remaining)法則優(yōu)先選擇余下加工時間最短的工件。 MOP

18、NR(Most Operations Remaining)法則優(yōu)先選擇余下工序數(shù)最多的工件。 SCR(Smallest Critical Ratio)法則優(yōu)先選擇臨界比最小的工件。臨界比為工件允許停留時間與工件余下加工時間之比。 RANDOM法則隨機(jī)地挑一個工件,2、隨機(jī)抽樣法,用窮舉法或分支定界法求一般單件車間排序問題的最優(yōu)解時，實(shí)際上比較了全部能動作業(yè)計(jì)劃；采用優(yōu)先調(diào)度法則求近優(yōu)解時，只選擇了一種作業(yè)計(jì)劃。 隨機(jī)抽樣法介于這兩個極端之間。 它從全部無延遲作業(yè)計(jì)劃之中抽樣，得出多個作業(yè)計(jì)劃，從中選優(yōu)。 應(yīng)用隨機(jī)抽樣法時，實(shí)際上是對同一個問題多次運(yùn)用隨機(jī)法則來決定要挑選的工序，從而得到多個作業(yè)計(jì)劃。,3、概率調(diào)度法,隨機(jī)抽樣法是從k個可供選擇的工序以等概率方式挑選，每個工序被挑選的概率為1k，這種方法沒有考慮不同工序的特點(diǎn)，有一定盲目性。 例如，在構(gòu)在無延遲作業(yè)計(jì)劃的第步有3道工序，A、B和C可挑選，這3道工序所需的時間分別為3，4和7。如果按RANDOM法則，每道工序挑選上的概率都是13；如果按SPT法則，則只能挑選工序A。現(xiàn)按目標(biāo)函數(shù)的要求，選擇了SPT法則。按概率調(diào)度法，將這3道工序按加工時間從小到大排列，然后給每