第八章流水作業(yè)的排序問題

一、排序問題的基本概念排序是確定工件（零部件）在一臺或一組設備上加工的先后順序。在一定約束條件下，尋找總加工時間最短的安排產品加工順序的方法，就是生產作業(yè)排序。例如，考慮32項任務（工件），有32！2.61035種方案,假定計算機每秒鐘可以檢查1billion個順序,全部檢驗完畢需要8.41015個世紀。如果只有16個工件,同樣按每秒鐘可以檢查1billion個順序計算,也需要2/3年。以上問題還沒有考慮其他的約束條件,如機器、人力資源、廠房場地等，如果加上這些約束條件，所需要的時間就無法想象了。所以，很有必要去尋找一些有效算法，解決管理中的實際問題。排序困難性假設條件1.一個工件不能同時在幾臺不同的機器上加工。2.工件在加工過程中采取平行移動方式，即當上一道工序完工后，立即送下道工序加工。3.不允許中斷。當一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其它工件。4.每道工序只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關。6.每臺機器同時只能加工一個工件。排序常用的符號

Ji----工件i，i=1,2,..n。Mj----

機器j，j＝1，2，…，m.di----工件Ji的完工期限。

pij----工件Ji在機器Mj上的加工時間,j=1,…,m

Pi----工件Ji的加工時間,wij----工件Ji在機器Mj前的等待時間,j=1,…,m

Wi----工件Ji在加工過程中總的等待時間,Ci----工件Ji的完成時間,

Fi----工件Ji的流程時間，即工件在車間的實際停留時間，在工件都已到達的情況下,Fi=Pi+WiLi----工件Ji的延誤時間,Li=Ci-di,Li<=0按期或完成提前；Li>0延誤

Fmax----最長流程時間，F(xiàn)max＝max{Fi}二、排序問題的分類和表示法1、排序問題的分類：根據機器數(shù)的多少單臺機器的排序問題多臺機器的排序問題根據加工路線的特征單件作業(yè)排序(JobShop)

流水作業(yè)排序(FlowShop)根據工件到達系統(tǒng)的情況靜態(tài)排序動態(tài)排序根據參數(shù)的性質確定型排序隨機型排序根據要實現(xiàn)的目標單目標排序多目標排序2、排序問題的表示法排序問題常用四個符號來描述:

n/m/A/B其中,n-----工件數(shù)；

m-----機器數(shù)；

A----車間類型；F=流水型排序，P=排列排序

G=一般類型,即單件型排序

B-----目標函數(shù)三、流水作業(yè)排序問題1、最長流程時間Fmax的計算舉例：有一個6/4/p/Fmax問題，其加工時間如下表所示。當按順序S＝（6，1，5，2，4，3）加工時，求Fmax。i123456Pi1Pi2Pi3pi4423142456745587555424331i615243Pi1Pi2Pi3pi424421354457655

5857143234最長流程時間的計算271213610121316111520273317223035422125323846最長流程時間的計算舉例2i

146352Pi1453486Pi2391375Pi3768259Pi45639244912162430714191819223136243234394830354446522、兩臺機器排序問題兩臺機器排序的目標是使最大完成時間（總加工周期）Fmax最短。實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標，一優(yōu)化算法就是著名的約翰遜法(Johnson’sLaw)。其具體求解過程如下例所示。約翰遜－貝爾曼法則約翰遜法解決這種問題分為4個步驟：(1)列出所有工件在兩臺設備上的作業(yè)時間。(2)找出作業(yè)時間最小者。(3)如果該最小值是在設備1上，將對應的工件排在前面，如果該最小值是在設備2上，則將對應的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重復步驟(2)和(3)，直到所有工件都安排完畢。

舉例AB兩臺設備完成5個零件的加工任務，每個工件在設備上的加工時間如下表所示。求總加工周期最短的作業(yè)順序。

設備\工件編號J1J2J3J4J5設備A36715設備B28643求解過程由約翰遜法可知，表5-8中最小加工時間值是1個時間單位，它又是出現(xiàn)在設備1上，根據約翰遜法的規(guī)則，應將對應的工件4排在第一位，即得：

J4-*-*-*-*

去掉J4，在剩余的工件中再找最小值，不難看出，最小值是2個時間單位，它是出現(xiàn)在設備2上的，所以應將對應的工件J1排在最后一位，即：

J4-*-*-*-J1

再去掉J1，在剩余的J2、J3、J5中重復上述步驟，求解過程為：

J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1

當同時出現(xiàn)多個最小值時，可從中任選一個。最后得J4-J2-J3-J5-J1

(a)J1-J2-J3-J4-J5

30AB(b)J4-J2-J3-J5-J126AB比較可以看出，初始作業(yè)順序的總加工周期是30，用約翰遜法排出的作業(yè)順序總加工周期是26，顯然后者的結果優(yōu)于前者。

將工件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最優(yōu)加工順序為S=(2,5,6,1,4,3),Fmax=28I123456Ai518534Bi722474兩臺機器排序問題的算法（續(xù)）Johnson算法的改進1.將所有ai≤

bi的工件按ai值不減的順序排成一個序列A；2.將ai＞bi的工件按bi值不增的順序排成一個序列B；3.將A放到B之前，就構成了一個最優(yōu)加工順序。改進算法舉例工件號123456

ai518534

bi722474最優(yōu)順序：256143

134558274742

ai

bi最優(yōu)順序下的加工周期為28148131826311152226283、m(m≥

3)臺機器排序問題的算法一般采用啟發(fā)式算法解決這類問題。關鍵工件法斜度指標法CDS法

（1）關鍵工件法

1、計算

Pi=,找出其中最大者，定義為關鍵工件Jc。2、除Jc外，將滿足Pi1<Pim的工件，按Pi1值的大小，從小到大排在Jc的前面。3、除Jc外，將滿足pi1>pim的工件，按Pim值的大小，從大到小排在Jc的后面。4、除Jc外，將滿足Pi1=Pim的工件，排在Jc的前面或者后面步驟5如有多個方案，可再加比較，從中選優(yōu)。舉例J1J2J3J4J5J6機器1pi15541210機器2pi25553610機器3pi3833474機器4pi4282156機器5pi55212810總和252315112840具體過程找出關鍵工件：工作負荷最大的40，對應的是工件6，所以Jc=J6

確定排在關鍵工件前面的工件：滿足步驟2條件的有J4,J5,所以有J4–J5–J6

確定排在關鍵工件后面的工件：滿足步驟3條件的有J2,J3,所以有–J6–J2–J3滿足步驟4條件的有J1,所以有–J6–J1，或者–J1–J6最后有：J4–J5–J6–J1–J2–J3，或J4–J5–J1–J6–J2–J3關鍵工件法（續(xù)）工件i1234Pi12163Pi24829Pi3548211131614JCSa(2,1)Sb(4)所求順序：（2,1,3,4）練習J1J2J3J4J5J6機器1pi1835424機器2pi2282156機器3pi35212810機器4pi45541710總和20181282230練習J5J2J6J1J3J4機器1pi1234854機器2pi2586221機器3pi38210512機器4pi4751054125917222671522152123252717313637392741465051練習J1J2J3J4J5J6機器1pi1835424機器2pi2282156機器3pi35212810機器4pi4554171081116202226101520192122273321222435452630314255(2)Palmer（斜度指標法）λi=工件的斜度指標計算公式k＝1，2，……m式中，m機器數(shù)；Pik為工件i在Mk上的加工時間。舉例有一個4/3/P/Fmax問題，其加工時間如下表所示，用Palmer法求解。i1234Pi1Pi2Pi3126384294582求解過程

求解過程

λi＝＝-Pi1+Pi3λ1＝-P11+P13=-1＋4＝3λ2＝-P21+P23=-2+5=3λ3＝-P31+P33=-6+8=2λ4＝-P41+P43=-3+2=-1按λi不增的順序排列工件，得到加工順序（1，2，3，4）和（2，1，3，4），F(xiàn)max=28k=1，2，3計算Fmaxi1234Pi1Pi2Pi312638429458213912913152413182628（3）CDS法Campbell,Dudek,Smith三人于1970年共同提出了一個啟發(fā)式算法，簡稱CDS法。他們把Johnson算法用于一般的n/m/P/Fmax問題，得到（m一1)個加工順序，取其中優(yōu)者。具體做法是，對加工時間和

（l=1，2，…，m-1），用Johnson算法求（m-1)次加工順序，取其中最好的結果。舉例有一個4/3/P/Fmax問題，其加工時間如下表所示，用Palmer法求解。i1234Pi1Pi2Pi3126384294582i1234l=1Pi11263Pi34582l=2Pi1+Pi296812Pi2+Pi31291011舉例

當l＝1時，按Johnson算法得到加工順序（1，2，3，4）；當l