第10章作業(yè)排序與生產(chǎn)作業(yè)計劃

27十二月2023第10章作業(yè)排序與生產(chǎn)作業(yè)計劃引言

在確定了各車間的零部件投入、出產(chǎn)計劃、將全廠的生產(chǎn)計劃變成了各車間的生產(chǎn)任務(wù)后,各車間還應(yīng)將零部件的投入、出產(chǎn)計劃變成車間的作業(yè)計劃，即將車間的生產(chǎn)任務(wù)變成各工段、班組、各工作地的生產(chǎn)任務(wù)。編制車間生產(chǎn)作業(yè)計劃，應(yīng)該解決工件加工順序問題。這就是我們要討論的作業(yè)排序問題。采用排序理論與方法，可以得出工件加工的最優(yōu)或令人滿意的順序。第一節(jié)作業(yè)排序的基本概念12/27/20232一、編制生產(chǎn)作業(yè)計劃與排序的關(guān)系編制生產(chǎn)作業(yè)計劃與作業(yè)排序不同，排序只是確定工件在機(jī)器上的加工順序，可以用一組工件的代號的排列來表示這組工件的加工順序，而編制生產(chǎn)作業(yè)計劃不僅包括確定工件的加工順序，而且包括確定機(jī)器加工每個工件的開始時間和完成時間。所以，只有生產(chǎn)作業(yè)計劃才能指導(dǎo)工人的生產(chǎn)活動。在編制生產(chǎn)作業(yè)計劃時常常出現(xiàn)一個工件在某道工序加工完之后，加工它的下一道工序的機(jī)器還在加工前一個工件，這時該工件不得不等待一段時間才能開始在下一道工序的機(jī)器上加工。這種情況稱為“工件等待”。當(dāng)某臺機(jī)器已加工完一個工件，而下一個工件尚未到達(dá)。這種情況稱為“機(jī)器空閑”。第一節(jié)作業(yè)排序的基本概念12/27/20233由于編制生產(chǎn)作業(yè)計劃的主要問題是確定各臺機(jī)器上工件的加工順序，并且一般都是按最早可能開工時間或最早可能完工時間來編制生產(chǎn)作業(yè)計劃。所以，當(dāng)工件的加工按一定的時間確定了加工順序后，作業(yè)計劃也就確定了。這就造成了人們通常不加區(qū)別的使用“排序”與“編制作業(yè)計劃”兩個術(shù)語。第一節(jié)作業(yè)排序的基本概念12/27/20234幾個名詞術(shù)語排序——工件在機(jī)器上的加工順序派工——將生產(chǎn)任務(wù)安排到具體機(jī)床上加工—調(diào)度范圍；趕工——實(shí)際進(jìn)度落后于計劃進(jìn)度時采取的行動—調(diào)度范圍；調(diào)度——發(fā)現(xiàn)實(shí)際進(jìn)度落后于計劃進(jìn)度時而采取的調(diào)配資源的行動。機(jī)器——服務(wù)者工件——服務(wù)對象加工路線——工件加工的工藝過程工序——加工路線上的每一個具體工作地（機(jī)器）。12/27/202351.一個工件不能同時在幾臺不同的機(jī)器上被加工。2.采取平行移動方式移送被加工的工件。3.不允許中斷。當(dāng)一個工件一旦開始加工,必須一直進(jìn)行到完工,不得中途停止插入其它工件。4.工件在每道工序的加工只在一臺機(jī)器上進(jìn)行。5.工件數(shù)（或批量）、機(jī)器數(shù)已知，單件加工時間已知,完成加工的時間與加工順序無關(guān)。6.每臺機(jī)器同時只能加工一個工件。第一節(jié)作業(yè)排序的基本概念二、假設(shè)條件與符號說明為了便于采用數(shù)學(xué)模型來分析研究排序問題，做下列假設(shè)：12/27/20236第一節(jié)作業(yè)排序的基本概念符號說明Wi=∑mj=1WijJi——第i工件，i=1,2,…,n；Mj——第j臺機(jī)器，j=1,2,…,m；(i,j,k)——Ji的第j道工序在Mk上進(jìn)行；Pi=∑mj=1PijPij——Ji在Mj上的加工時間，

Ji加工完的總加工時間；ri——Ji到達(dá)工序時間，即可以開始加工的最早時間；di——Ji的完工期限；ai——Ji在車間允許停留的時間（Ji進(jìn)入車間到完工時刻之間的時間間隔：ai=di－ri）；Wij——Ji在第j道工序前的等待時間，Ji總的等待時間：12/27/20237Ci=ri+∑(Pij+Wij)=ri+Pi+WiLi=Ci－di=ri+Pi+Wi－di=(Pi+Wi)－(di－ri)=Fi－ai

Fi=Ci－ri=Pi+Wi;第一節(jié)作業(yè)排序的基本概念Ci——Ji的完工時間Cmax——最長完工時間,Cmax=max{Ci},即一批工件中的最長完工時間;Fi——Ji的流程時間,即工件在車間的實(shí)際停留時間,Fmax——最長流程時間,Fmax=max{Fi},即一批工件中的最長流程時間;Li——Ji工件的延遲時間，12/27/20238第一節(jié)作業(yè)排序的基本概念當(dāng)Li>0時為正延遲,即Ji的實(shí)際完工時間超過了完工期限;當(dāng)Li<0

時為負(fù)延遲,即Ji提前完工;當(dāng)Li=0時為零延遲,即Ji按期完工。Lmax——最長延遲時間,Lmax=max{Li}.即在一批工件中找出的最大延遲時間.12/27/20239三、排序問題的分類和表示法

排序問題常見的分類方法有按機(jī)器、工件、目標(biāo)函數(shù)的特征分類。1.按機(jī)器的種類和數(shù)量不同,可以分成單臺機(jī)器的排序問題多臺機(jī)器的排序問題對于多臺機(jī)器的排序問題,按工件加工路線的特征,單件作業(yè)排序問題——加工路線不同流水作業(yè)排序問題——加工路線相同可以分成第一節(jié)作業(yè)排序的基本概念12/27/2023102.按工件到達(dá)車間的情況不同,可以分成靜態(tài)的排序問題——排序時所有工件都已到達(dá),可以一次對它們進(jìn)行排序.動態(tài)的排序問題——排序時工件陸續(xù)到達(dá),要隨時安排它們的加工順序3.按目標(biāo)函數(shù)的性質(zhì)不同,也可劃分不同的排序問題單臺機(jī)器的排序使平均流程時間最短使誤期完工工件數(shù)最少……多臺機(jī)器的排序：不同目標(biāo)排序問題單目標(biāo)排序問題：以往研究的對象多目標(biāo)排序問題：很少有人研究第一節(jié)作業(yè)排序的基本概念12/27/2023114.另外，按參數(shù)的性質(zhì)，可以劃分為確定型排序問題——指加工時間和有關(guān)參數(shù)是已知確定的量隨機(jī)型排序問題——加工時間和有關(guān)參數(shù)為隨機(jī)變量這兩種排序問題的解法本質(zhì)上不同?，F(xiàn)只討論幾種有代表性的排序問題。第一節(jié)作業(yè)排序的基本概念12/27/202312通常采用Conway等人提出的排序方法。這個方法主要涉及到4個參數(shù)，只用4個參數(shù)就可以表示大多數(shù)不同的排序問題。這4個參數(shù)通常表示為：n/m/A/B。n為工件數(shù)；m為機(jī)器數(shù)B為目標(biāo)函數(shù),通常是使其值最小A為車間類型，通常有以下幾種情況，在A的位置：(1)若標(biāo)以"F",則代表流水作業(yè)排序問題(2)若標(biāo)以“P”,則表示流水作業(yè)排列排序問題，也常被稱為“同順序”排序問題(3)若標(biāo)以“G”,則表示一般單件作業(yè)排序問題。第一節(jié)作業(yè)排序的基本概念12/27/202313當(dāng)m=1時，A處為空白。因?yàn)閷τ趩闻_機(jī)器的排序問題來說，不存在所謂的加工路線問題，當(dāng)然也就談不到是流水作業(yè)排序問題還是單件作業(yè)的排序問題了。

通過n/m/A/B這4個符號，就可以簡捷的表述一般的排序問題了。例如，n/3/P/Cmax表示n個工件經(jīng)3臺機(jī)器加工的流水作業(yè)排列排序問題，目標(biāo)函數(shù)是使最長完工時間最短。第一節(jié)作業(yè)排序的基本概念12/27/202314第十章作業(yè)排序與生產(chǎn)作業(yè)計劃回顧排序問題常見的分類方法有按機(jī)器、工件、目標(biāo)函數(shù)的特征分類。排序問題由4個參數(shù)表示：n/m/A/B。n為工件數(shù)；m為機(jī)器數(shù)B為目標(biāo)函數(shù),通常是使其值最小A為車間類型，通常有以下幾種情況，在A的位置：(1)若標(biāo)以“F”,則代表流水作業(yè)排序問題。(2)若標(biāo)以“P”,則表示流水作業(yè)排列排序問題，也常被稱為“同順序”排序問題。(3)若標(biāo)以“G”,則表示一般單件作業(yè)排序問題。Cmax——最長完工時間；Fmax——最長流程時間；Lmax——最長延遲時間。Lmax=max{Li}.即在一批工件中找出的最大延遲時間。當(dāng)Li>0時為正延遲,即Ji的實(shí)際完工時間超過了完工期限;當(dāng)Li<0

時為負(fù)延遲,即Ji提前完工;當(dāng)Li=0時為零延遲,即Ji按期完工。例如：n/3/P/Cmax表示n個工件經(jīng)3臺機(jī)器加工的流水作業(yè)排列排序問題，目標(biāo)函數(shù)是使最長完工時間最短。12/27/202315流水作業(yè)排序問題的基本特征是每個工件的加工路線都一致。在流水生產(chǎn)線上制造不同的零件,遇到的就是流水作業(yè)排序問題。我們說加工路線一致,是指工件的流向一致,并不要求每個工件必須經(jīng)過加工路線上每臺機(jī)器加工。如果某些工件不經(jīng)某些機(jī)器加工,則設(shè)相應(yīng)的加工時間為零。一般說來,對于流水作業(yè)排序問題,工件在不同機(jī)器上的加工順序不盡一致。但本節(jié)要討論的是一種特殊情況,即所有工件在各臺機(jī)器上的加工順序都相同的情況。這就是排列排序問題。流水作業(yè)排列排序問題常被稱作"同順序"排序問題。對于一般情形,排列排序問題的最優(yōu)解不一定是相應(yīng)的流水作業(yè)排序問題的最優(yōu)解,但一般是比較好的解;對于僅有2臺和3臺機(jī)器的特殊情況,可以證明,排列排序問題下的最優(yōu)解一定是相應(yīng)流水作業(yè)排序問題的最優(yōu)解。本節(jié)只討論排列排序問題。但對于2臺機(jī)器的排序問題,實(shí)際上不只是排列排序問題，因?yàn)閮烧叩淖顑?yōu)解及其解法是相同的。第二節(jié)流水作業(yè)排序問題12/27/202316一、最長流程時間Fmax的計算最長流程時間就是工件在車間實(shí)際停留的最長時間。本節(jié)所討論的是n/m/ρ/Fmax問題,目標(biāo)函數(shù)是使最長流程時間最短。最長流程時間又稱作加工周期,它是從第一個工件在第一臺機(jī)器開始加工時算起,到最后一個工件在最后一臺機(jī)器上完成加工時為止所經(jīng)過的時間。由于假設(shè)所有工件的到達(dá)時間都為零(r=0，i=1,2,…,n),所以Fmax等于排在末位加工的工件在車間的停留時間,也等于一批工件的最長完工時間Cmax。第二節(jié)流水作業(yè)排序問題12/27/202317設(shè)n個工件的加工順序?yàn)镾=(S1,S2,…,Sn),其中Si為排第i位加工的工件的代號。以Ck(si)表示工件Si在機(jī)器Mk上的完工時間,

Psik表示工件Si在Mk上的加工時間,k=1,2,…,m；i=1,2,…,n則Ck(si)可按以下公式計算:

C1(si)=C1(si-1)+Psi1

Ck(si)=max{Ck-1(si),Ck(si-1)}+Psik(11—1)第二節(jié)流水作業(yè)排序問題顯然，當(dāng)ri=0時，F(xiàn)max=Cm(sn)在知道了上述計算Fmax公式后，便可直接在工件加工的時間矩陣上從左向右計算完工時間。12/27/202318第二節(jié)流水作業(yè)排序問題例11.1有一個6/4/p/Fmax問題,其加工時間如下表所示。當(dāng)按順序S=(6,1,5,2,4,3)加工時,求Fmax表11-1加工時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi442433112/27/202319i615243Pi1244213Pi2544576Pi3555857Pi4143234表11-2順序S下的加工時間矩陣261012131671115202733121722303542132125323846Fmax=4612/27/202320Johnson算法:(1)從加工時間矩陣中找出最短的加工時間。(2)若最短的加工時間出現(xiàn)在M1上,則對應(yīng)的工件盡可能往前排；若最短加工時間出現(xiàn)在M2上，則對應(yīng)工件盡可能往后排。然后,從加工時間矩陣中劃去已排序工件的加工時間。若最短加工時間有多個,則任挑一個往前排。(3)若所有工件都已排序,停止.否則,轉(zhuǎn)步驟(1).第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最優(yōu)算法12/27/202321第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最優(yōu)算法例11.2求表1１-３所示的6/２/Ｆ/Fmax問題的最優(yōu)解。i１２３４５６ai５１８５３４bi８２２４７４表11-3加工時間矩陣5614192226131517233034Fmax0(1,2,3,4,5,6)=3412/27/202322i１２３４５６ai５１８５３４bi８２２４７４表11-4改進(jìn)算法見教材303頁Johnson改進(jìn)算法：１.將所有ai≤bi的工件按ai值不減的順序排成一個列Ａ；２.將所有ai＞bi的工件按bi值不增的順序排成一個列Ｂ；３.將Ａ放到Ｂ之前，就構(gòu)成了最優(yōu)加工順序．(1)(2)(3)(4)A=(2,5,6,1)(5)(6)B=(4,3)S=(2,5,6,1,4,3)i２５６１４３ai１３４５５８bi２７４８４２14813182631115232729Fmax*(2,5,6,1,4,3)=2912/27/202323當(dāng)我們從應(yīng)用Johnson法則求得的最優(yōu)順序中任意去掉一些工件時,余下的工件仍構(gòu)成最優(yōu)順序。如對例11.2的最優(yōu)順序(2,5,6,1,4,3),若去掉一些工件,得到的順序(5,6,1,4,3)、(2,6,4,3)、(2,6,1,4)等仍為余下工件的最優(yōu)順序。但是,工件的加工順序不能顛倒,否則不一定是最優(yōu)順序。同時,我們還要指出,Johnson法則只是一個充分條件,不是必要條件。不符合這個法則的加工順序,也可能是最優(yōu)順序。對例11.2順序(2,5,6,4,1,3)不符合Johnson法則,但它也是一個最優(yōu)順序。第二節(jié)流水作業(yè)排序問題12/27/202324例11.2順序(2,5,6,4,1,3)i２５６４１３ai１３４５５８bi２７４４８２31481318261115192729Fmax*(2,5,6,4,1,3)=2912/27/202325第二節(jié)流水作業(yè)排序問題三、一般n/m/P/Fmax問題的啟發(fā)式算法對于3臺機(jī)器的流水車間排序問題,只有幾種特殊類型的問題找到了有效算法。對于一般的流水車間排列排序問題,可以用分支定界法。用分支定界法可以保證得到一般n/m/P/Fmax問題的最優(yōu)解。但對于實(shí)際生產(chǎn)中規(guī)模較大的問題,計算量相當(dāng)大,以至連電子計算機(jī)也無法求解。同時,還需考慮經(jīng)濟(jì)性。如果為了求最優(yōu)解付出的代價超過了這個最優(yōu)解所帶來的好處,也是不值得的。為了解決生產(chǎn)實(shí)際中的排序問題,人們提出了各種啟發(fā)式算法。啟發(fā)式算法以小的計算量得到足夠好的結(jié)果,因而十分適用。下面介紹求一般n/m/p/Fmax問題近優(yōu)解(Nearoptimalsolution)的啟發(fā)式算法。12/27/202326第二節(jié)流水作業(yè)排序問題(一)帕爾姆(Palmer)法1965年,D.S.Palmer提出按工件斜度指標(biāo)排序的啟發(fā)式算法。設(shè)：工件的斜度指標(biāo)為i，k為笫k臺設(shè)備，m為設(shè)備數(shù)，Pik為i工件在Mk上加工時間，k為設(shè)備的任意序數(shù)，（k=1,2,3,……,m）

i=∑mk=1［k－（m+1）/2］Pik從該式中求出各工件的i，再按著不使i增加的原則排列各個工件的加工順序，就可以得出令人滿意的結(jié)果。12/27/20232713912915132413261828工件i設(shè)備工時1234Pi11263Pi28429Pi34582表11-5加工時間矩陣?yán)?1.3有一個4/3/F/Fmax排序問題（即4個工件3臺設(shè)備，流水作業(yè)排序問題，目標(biāo)是使最長流程時間最短），各個工件在每臺設(shè)備上的加工時間如下面的加工時間矩陣表所示，試采用Palmer法求解。Fmax=2812/27/202328按照排序?yàn)椋篠=（2，1，3，4）工件i設(shè)備工時2134Pi12163Pi24829Pi3548223912614162511182628Fmax=2812/27/202329第二節(jié)流水作業(yè)排序問題解：由

i=∑mk=1［k－（m+1）/2］Pik可知(見教材304頁)按照i從大到小的順序排列就是最優(yōu)排列順序。最優(yōu)排列順序S=（1，2，3，4）或：S=（2，1，3，4）12/27/202330P322習(xí)題2：請用帕爾瑪法排序并計算最長流程時間iK1234K-(m+1)/2(K-(m+1)/2)*P1k(K-(m+1)/2)*P2k(K-(m+1)/2)*P3k(K-(m+1)/2)*P4kPik11954-1.5-1.5-13.5-7.5-6Pik25763-0.5-2.5-3.5-3-1.5Pik346350.5231.52.5Pik462371.5934.510.5m=4Ai=(K-(m+1)/2)*P1k7-11-4.55.5求解過程：排序?yàn)椋篠=(1,4,3,2)12/27/202331按照S=(1,4,3,2)計算最長流程時間：i1432Pik1459Pik5367Pik4536Pik67321510192669161015193216232634Fmax=3412/27/202332(二)關(guān)鍵工件法關(guān)鍵工件法是1983年提出的一個啟發(fā)式算法。其步驟如下:(1)計算每個工件的總加工時間Pi=∑Pij,找出總加工時間最長的工件C(j=1.2.3.……m),將其作為關(guān)鍵工件。(2)對于余下的工件,若Pi1≦Pim,

則按Pi1不減的順序排成一個序列Sa；若Pi1＞Pim，

則按Pim不增的順序排列成一個序列Sb。(3)順序(sa,C,Sb)即為所求順序（近優(yōu)解）。第二節(jié)流水作業(yè)排序問題12/27/202333表11-6工件在每臺設(shè)備上的單件工時與總工時(見教材305頁)第二節(jié)流水作業(yè)排序問題例：有4個工件，在3臺設(shè)備上加工，每個工件在每臺設(shè)備上加工的單件工時消耗如表11-6所示。試采用關(guān)鍵工件法求近優(yōu)解（近優(yōu)排序）。i=1,2,3,4；m=1,2,3工件i1234Pi11263Pi28429Pi34582Pi13111614312412/27/202334解：（1）計算每個工件的總加工時間，填寫在表11-6上，分別為（13,11,16,14），可見總加工時間最長的工件為3號工件，總加工時間P3=16。（2）余下的工件為1,2,4號工件，Pi1≦Pi3的工件為1,2號；按Pi1不減（相等或增加）(P11=1,P21=2)的順序排成一個序列Sa=（1,2）；Pi1＞Pim的工件為4號工件，按Pim不增（相等或減少）順序排成一個序列Sb=(4)（∵只有一個工件）。（3）近優(yōu)解的順序（Sa,C,Sb）為（工件1,2,3,4）第二節(jié)流水作業(yè)排序問題12/27/202335表11-6工件在每臺設(shè)備上的單件工時與總工時工件i1234Pi11263Pi28429Pi3458213912913152413182628Fmax計算過程12/27/202336P322習(xí)題2：請用關(guān)鍵工件法排序并計算最長流程時間i1234Pi11954Pi25763Pi34635Pi46237時間求和16241719排序?yàn)椋篠=（1，4，2，3）關(guān)鍵工件法求解過程如下：12/27/202337按照S=（1，4，2，3）計算最長流程時間i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=3312/27/202338(三)CDS法(Campbell,Dudek,Smith三人提出)(見教材305頁)第二節(jié)流水作業(yè)排序問題工件i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+Pi31291011表11-7用CDS法求解L=1時：按照J(rèn)ohnson法得到加工順序?yàn)椋?，2，3，4L=2時：按照J(rèn)ohnson法得到加工順序?yàn)椋?，3，1，412/27/2023398912618102711231929Fmax計算如下表所示Fmax=29若加工順序?yàn)椋?，3，1，4）時，按Johnson算法Fmax=29，所以取加工順序（1，2，3，4）Fmax=28為最優(yōu)解。工件i設(shè)備工時2314Pi12613Pi24289Pi35842第二節(jié)流水作業(yè)排序問題212/27/202340P322習(xí)題2：請用CDS法排序并計算最長流程時間i1234Pi11954Pi25763Pi34635Pi46237關(guān)鍵工件法求解過程如下：12/27/202341排序?yàn)椋篠1=（1，4，3，2）i1234L=1Pi11954Pi46237i1234Pi11954Pi25763Pi34635Pi462371、L=1時：12/27/202342排序?yàn)椋篠1=（1，4，3，2）i1432Pi11459Pi25367Pi34536Pi467321510196916261015193216232634Fmax=3412/27/202343排序?yàn)椋篠1=（1，4，2，3）i1234L=2Pi1616117Pi4108612i1234Pi11954Pi25763Pi34635Pi462372、L=2時：12/27/202344排序?yàn)椋篠1=（1，4，2，3）i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=3312/27/202345排序?yàn)椋篠1=（1，4，2，3）i1234L=3Pi110221412Pi415151215i1234Pi11954Pi25763Pi34635Pi462373、L=3時：12/27/202346排序?yàn)椋篠1=（1，4，2，3）i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=33所以最終排序?yàn)椋篠1=（1，4，2，3）滿意解。12/27/202347三、采用Johnson法則解決多個工件在三臺設(shè)備上的作業(yè)排序若存在一個n/3/P/Fmax問題，且mint1i≥maxt2i或mint3i≥mint2i(i=1，2，……，n)，則可采用Johnson法排序。求解步驟為：（1）先找出mint1i≥maxt2i或mint3i≥mint2i關(guān)系（2）將3臺設(shè)備變換成2臺假想設(shè)備MA和MB，并令tAi=t1i+t2i；tBi=t2i+t3i（3）依據(jù)tAi和tBi，采用Johnson法則進(jìn)行作業(yè)排序試采用Johnson法則進(jìn)行作業(yè)排序工件設(shè)備J1J2J3

J4M1158612M23156M341057表11-17加工時間表例：有一個4/3/P/Fmax問題，其加工時間如表11-17所示12/27/202348解：①∵mint1i=6maxt2i=6存在mint1i≥maxt2imint3i=4mint2i=1存在mint3i≥mint2i

∴可采用Johnson法求解該作業(yè)排序問題(具備其一即可)。

②

計算tAi和tBi，列于表11-18中表11-18tAi、tBi與排序結(jié)果工件設(shè)備J1J2J3

J4(MA)tAi1891118(MB)tBi，7111013排序結(jié)果J2J4J3J1t1i812615t2i1653t3i107548202641926314419333848③依據(jù)11-18中的tAi和tBi，采用Johnson法進(jìn)行作業(yè)排序。排序結(jié)果與Fmax如表11-18及圖11-4所示。Fmax=4812/27/202349J2J4J3J18

126151

65389

20263141448

20264110

7549

192633384448M1M2M3時間圖11-4排序結(jié)果甘特圖12/27/202350單件作業(yè)排序是最一般的排序問題，也是最復(fù)雜的一種排序問題。該問題本身容易表達(dá)，也能看出該問題所需要求解的是什么，但是朝著求解方向作任何推進(jìn)都是極為困難的。許多人在此問題上都進(jìn)行了探索，但一無所獲者大有人在。第三節(jié)單件作業(yè)排序問題12/27/202351第三節(jié)單件作業(yè)排序問題一、問題的描述

對一般的單件作業(yè)排序問題，每個工件都有其獨(dú)特的加工路線，工件沒有一定的流向。但是，對于流水作業(yè)的排序問題，第k道工序永遠(yuǎn)在MK上進(jìn)行，沒有必要將工序號與機(jī)器號分開。而對于一般的單件作業(yè)排序問題，要描述一道工序需要i、j、k三個參數(shù)，即i、j、k表示第i個工件的第j道工序在Mk(第k臺機(jī)器上)上進(jìn)行的。所以，可以用加工描述矩陣的形式來描述所有工件的加工。加工描述矩陣的形式如加工描述矩陣D所示。加工描述矩陣的每一行描述一個工件的加工過程(第1行描述第一個工件的加工過程，第二行描述第2個工件的加工過程)。D的每一組數(shù)中的第1列數(shù)表示工件序號；D的每組數(shù)中的第2列數(shù)碼相同，說明第2列表示工序號；D的每一組數(shù)中的第3列數(shù)表示設(shè)備序號。12/27/202352第三節(jié)單件作業(yè)排序問題

二、一般n/m/G/Fmax問題的啟發(fā)式算法n/m/G/Fmax為n個工件，m臺機(jī)器，一般單件作業(yè)排序問題，使最大流程時間最短。對這類作業(yè)排序問題，可以用分支定界法或整數(shù)規(guī)劃法求最優(yōu)解。但是，都是無效的方法。為此，在實(shí)際工作中，多采用啟發(fā)式算法。為了對研究啟發(fā)式算法有所幫助，先介紹兩種十分重要的作業(yè)計劃及其構(gòu)成方法。12/27/202353(一)兩種作業(yè)計劃的構(gòu)成一般說來，在可行的加工順序下，可以擬定出無數(shù)種作業(yè)計劃。其中，各工序都按最早可能開始工作的時間安排作業(yè)計劃，稱為半能動作業(yè)計劃。任何一臺機(jī)器的每段空閑時間都不足以加工一道可加工工序的半能動作業(yè)計劃，又稱為能動作業(yè)計劃。無延遲作業(yè)計劃是指沒有任何延遲出現(xiàn)的能動作業(yè)計劃。所謂“延遲”是指工件等待加工時，機(jī)器出現(xiàn)空閑(即使這段空閑時間不足以完成一道工序的加工)。能動作業(yè)計劃和無延遲作業(yè)計劃在研究一般單件作業(yè)排序問題時有重要作用。二、一般n/m/G/Fmax問題的啟發(fā)式算法12/27/202354△能動作業(yè)計劃與無延遲作業(yè)計劃構(gòu)成過程中涉及到的4個符號：若將每安排一道工序稱為“一步”。設(shè)：

St}

—為第t步之前已排序工序構(gòu)成的部分作業(yè)計劃；

Ot}—為第t步可以排序的工序集合；Tk—為

Ot}中工序Ok的最早可能開工時間；T

k—為

Ot}中工序Ok的最早可能完工時間。顯然：Ok工序的作業(yè)時間=T

k-Tk12/27/202355設(shè)t=1,

S1}為空集，

O1}為各工件第一道工序的集合。求T*=min|T’k|,并求出T*出現(xiàn)的機(jī)器M*。如果M*有多臺，則任選一臺。從

Ot}中挑出滿足以下兩個條件的工序Oj，需要機(jī)器M*加工，且Tj<T*。將確定的工序Oj放入

St}，從

Ot}中消去Oj，并將Oj的緊后工序放入

Ot}，使t=t+1。若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。

二、一般n/m/G/Fmax問題的啟發(fā)式算法(一)兩種作業(yè)計劃的構(gòu)成P3101、能動作業(yè)計劃的構(gòu)成步驟12/27/202356例11.5：有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩陣T分別為：試構(gòu)成一個能動作業(yè)計劃。P310按表11~9所示的能動作業(yè)計劃構(gòu)成過程，可繪出圖11~4能動作業(yè)計劃時間安排(排序)圖—能動作業(yè)計劃。12/27/202357表11—9能動作業(yè)計劃的構(gòu)成T*＝min{T

k}t

Ot}TkTT

kT*M*Oj123456下期工序最早可能開工時間：1,1,12,1,31,2,32,2，11,3，22,3，21,1,12,1,31,2,32,1,31,2,32,2，11,3，22,2，11,3，22,3，22,3，2002033737782343441415523637787812132377813M1M3M3M1M1M2M22,4,13,4,5T=D=1,1,11,2,31,322,1,32,2,12,3,2或：一個2/3/G/Fmax問題12/27/202358能動作業(yè)計劃的甘特圖；最大流程：Fmax=13012345678901234M1—M2—M3—1,1,12,2,12372,1,31,2,3731,3,22,3,2781312/27/202359對表11~9所示的能動作業(yè)計劃（作業(yè)時間排序）構(gòu)成過程可描述為下列過程：（1）當(dāng)t=1時

O1}為：2個工件、可以在第1道工序上、進(jìn)行第1步排序的集合，即

O1}=

（1,1,1）；（2,1,3）}。它們的最早可能開工時間Tk=T1=0。工序（1,1,1）的最早可能完工時間T′k=T′1=2；工序（2,1,3）的T′k=T′1=3，

T*=min

T

k}=2。可見，T*=2出現(xiàn)的機(jī)器M*=M1。在這一步中M1上僅有一道工序（1,1,1）可以排序。所以，首先安排（1,1,1）在M1上加工。（2）、（3）……（略）（4）當(dāng)t=4時，

O4}=

（1,3,2）；（2,2,1）}，T4=7或3，T′4=8或7。

T*=7，出現(xiàn)在M1上，

將（2,2,1）安排在M1上加工。（5）……（略）

（6）當(dāng)t=6時，

O6}=

（2,3,2）}，T6=8，T′6=13。此時只剩下（2,3,2），

將（2,3,2）安排在M2上加工。

該排序問題最后完工時間為13。

1、能動作業(yè)計劃的構(gòu)成步驟(一)兩種作業(yè)計劃的構(gòu)成12/27/202360在作業(yè)計劃中，“延遲”是指工件等待加工，而機(jī)器出現(xiàn)空閑（空閑時間不能完成一道工序的加工作業(yè)）。所以，無延遲作業(yè)計劃是指沒有任何延遲出現(xiàn)的能動作業(yè)計劃。無延遲作業(yè)計劃的構(gòu)成步驟設(shè)t=1,

S1}為空集，

O1}為各工件第一道工序的集合。求T*=min|T’k|,并求出T*出現(xiàn)的機(jī)器M*。如果M*有多臺，則任選一臺。從

Ot}中挑出滿足以下兩個條件的工序Oj，需要機(jī)器M*加工，且Tj=T*。將確定的工序Oj放入

St}，從

Ot}中消去Oj，并將Oj的緊后工序放入

Ot}，使t=t+1。若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。2、無延遲作業(yè)計劃的構(gòu)成(排序)步驟P31112/27/202361例：對例11.5：有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩陣T分別為：試構(gòu)成一個無延遲作業(yè)計劃。P312解：表11—10無延遲作業(yè)計劃的構(gòu)成

t

Ot}TkTT

kT*M*Oj11,1,12,1,300232300M11,1,121,2,32,1,32043630M32,1,331,2,32,2，133447733M31,2,341,3，22,2，17314873M12,2，151,3，22,3，2771581277M22,3，261,3，21211312M21,3，2最大流程：Fmax=1312/27/202362無延遲作業(yè)計劃的甘特圖；最大流程：Fmax=13012345678901234M1—M2—M3—1,1,12,2,12372,1,31,2,3731,3,22,3,27121312/27/202363(二)作業(yè)排序的三類啟發(fā)式算法

1、優(yōu)先調(diào)度法(見教材311~314頁)對應(yīng)用優(yōu)先調(diào)度法則的說明2.隨機(jī)抽樣法3.概率調(diào)度法8個主要的優(yōu)先調(diào)度法則：P312二、一般n/m/G/Fmax問題的啟發(fā)式算法12/27/2023641、SPT法則(最短加工時間規(guī)則)例題SPT法則就是優(yōu)先選擇加工時間最短的工序。即排序時將各個工件的加工時間由短到長進(jìn)行排隊(duì)，排在前面的加工時間最短的工序優(yōu)先按排加工。其優(yōu)點(diǎn)是，使平均流程時間F最短，使在制品的占用量減少，其缺點(diǎn)是沒有考慮交貨期，有可能會使部分工件延誤了交貨期。例：現(xiàn)有一個6/1/F問題，其加工時間與交貨期如表11-10所示，試采用SPT法則進(jìn)行作業(yè)排序。(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)表11-10加工時間與交貨期表工序號J1J2J3J4J5J6加工時間482593交貨期242386321312/27/2023651、SPT法則(最短加工時間規(guī)則)例題。解：25914223123458916F=

(2+5+9+14+22+31)=13.8工件號J3J6J1J4J2J5交貨期di8132462332流程時間Fi=Ci259142231延期交貨Li-6-8-158-1-1由求解過程可知，按SPT法則排序順序?yàn)椋篔3，

J6，J1，J4，J2，J5；流程時間分別為：2，5，9，14，22，31；F=13.8；工件J4延期交貨8個時間單位。其余提前完成(4)統(tǒng)計延期交貨狀況：(3)計算平均流程時間(2)計算各工件加工流程時間，標(biāo)在加工時間的右上角：(1)將各個工件加工時間由短到長排隊(duì)為：J32，J63，J14，J45，J28，J59表11-11延期交貨統(tǒng)計表轉(zhuǎn)后例12/27/202366

2、EDD規(guī)則(最早預(yù)定交貨規(guī)則)例題

EDD規(guī)則就是優(yōu)先選擇完工期限緊的工件。即，在進(jìn)行工件作業(yè)排序時，按工件完工期限由緊到松進(jìn)行排序，排在前面的完工期限最緊的工件優(yōu)先按排加工。EDD法則的優(yōu)點(diǎn)是考慮了交貨期，有利于做到按期交貨，使工件中的最大延遲時間最小。其缺點(diǎn)是使平均流程時間F增加，增大了在制品占用量。(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)工序號J1J2J3J4J5J6加工時間482593交貨期2423863213試進(jìn)行作業(yè)排序(使Lmax最小)。表11-10加工時間與交貨期例：(仍采用上例)有一個6/1/Lmax問題(即6個工件，1臺機(jī)器，使最大延遲時間最小)，其加工時間與交貨期如表11-10所示。12/27/202367由表11-12計算可知，該例采用EDD法則排序?yàn)椋篔4、J3、J6、J2、J1、J5，且各工件延遲時間均為0。平均流程時間F=15.5(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)2、EDD規(guī)則(最早預(yù)定交貨規(guī)則)例題

解：根據(jù)EDD法則是將完工期限最緊的工序優(yōu)先按排，為此

采用

表11-12把交貨期短的工件先按排，再求出流程時間與交貨期相比較，檢查是否存在有延遲時間的工件，延遲時間是多少，是否可以在排序上再進(jìn)行調(diào)整。工件號J4J3J6J2J1J5交貨期6813232432加工與流程時間523849延遲時間5710182231表11-12延遲時間分析表000000轉(zhuǎn)前例12/27/2023683、SPT與EDD混合(結(jié)合)法則例題這是將SPT規(guī)則(最短加工時間規(guī)則)與EDD規(guī)則(最早預(yù)定交貨規(guī)則)結(jié)合起來的在單臺設(shè)備上的排序方法。這種排序方法克服了SPT與EDD兩個單一規(guī)則只能達(dá)到一個目標(biāo)的缺點(diǎn)，可以獲得較為理想的結(jié)果。為了說明問題方便，仍以表11-10所示的排序問題為例。(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)表11-10加工時間與交貨期表工序號J1J2J3J4J5J6加工時間482593交貨期242386321312/27/202369(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)3、SPT與EDD混合(結(jié)合)法則例題按SPT與EDD結(jié)合的規(guī)則排序步驟如下：（1）首先根據(jù)EDD規(guī)則排序，即安排一個使Lmaxmin(使最長延遲時間最短)的初步方案。［若該初步方案出現(xiàn)Lmax=0，說明該初步方案已滿足要求。例如表11-10的例子，可按交貨期最短的先安排加工(即根據(jù)交貨期排序)。所以，其排序?yàn)椋篔4—

J3—J6

—J2—J1

—J5按此排序可以求得：Lmax=max{Li}=-1，滿足要求。］（2）計算全部生產(chǎn)任務(wù)的總流程時間F總=Fmax=

max{Fi}=F5=Pi

=P4+P3+P6+P2+P1+P5=31（3）找出初步方案中預(yù)定交貨期大于Fmax的工件(可能有多件)，并按SPT規(guī)則，把其中加工時間最長的工件排在最后加工。在本例中，預(yù)定交貨期大于Fmax=31的工件只有J5，當(dāng)然應(yīng)該將J5排在最后加工。12/27/202370（4）舍棄第（3）步中已排在最后的J5，余下J4—

J3—J6

—J2—J1

重復(fù)第（2）步。此時出現(xiàn)情況如表11-13所示。(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)3、SPT與EDD混合(結(jié)合)法則例題

工件排序J4

J3

J6J2J1加工時間與F52384預(yù)定交貨期68132324由表11-13可知，余下5個工件中J1

的F最大，F(xiàn)max=22。預(yù)定交貨期大于Fmax=22的有J1

和J2，其中J2的加工時間P2=8為較大者(P2=8>P1=4)，故按SPT規(guī)則將J2排在第5順序(倒數(shù)第2位)加工，即將J2排在次后順序上加工。表11-13余下工件的F與預(yù)訂交貨期5710182212/27/202371反復(fù)進(jìn)行（2）、（3）步，直到實(shí)現(xiàn)既使Lmax

≦0，又使F(平均流程時間)為Fmin的排序方案為止。

5710142231

表11-14排序方案及各參數(shù)結(jié)果表(三)優(yōu)先調(diào)度法則例題(此為單臺設(shè)備排序問題例題)按SPT與EDD結(jié)合規(guī)則排序，可得出表11-10的排序問題的排序?yàn)椋篔4—

J3—J6

—J1—J2

—J5表11-10排序問題的結(jié)論如表11-14所示。3、SPT與EDD混合(結(jié)合)法則例題工件排序J4J3J6J1J2J5加工時間與F523489預(yù)定交貨期68

13242332計劃完成時刻5

710142231交貨延期000000平均流程時間F=14.812/27/202372現(xiàn)有一個n/2/F/Fmax(n個工件，2臺設(shè)備，流水作業(yè)排序問題，使最長流程時間最短)問題。此問題可采用S.M.Johnson算。工件JiJ1J2J3J4J5J6J7加工時間M16812371124M21195326182解：按照J(rèn)ohnson法則：（1）如果最短的加工時間出現(xiàn)在M1上，則對應(yīng)工件排在最前面(第一個)加工，如果最短的加工時間出現(xiàn)在M2上，則對應(yīng)工件排在最后面(倒數(shù)第一個)加工，如果最短的加工時間同時出現(xiàn)在M1、M2上，則該工件排在最前或最后加工均可。（2）劃去已排序工件，在余下來的未排序工件中仍然按上述方法進(jìn)行作業(yè)排序，直到全部工件安排完為止。(自己練習(xí))表11-15加工時間例：有一個7/2/F/Fmax問題，其加工時間如表11-15所示，試進(jìn)行作業(yè)排序。第四節(jié)多臺設(shè)備作業(yè)排序流水作業(yè)排序（4—1—5—2—6—3—7）一、多個工件在兩臺設(shè)備上的作業(yè)排序12/27/2023733112691852表11-16加工時間與排序結(jié)果表3916243547716204655737880（3）運(yùn)用Johnson法則對此問題求解如表11-16和圖11-3所示。J4J1J5J2J6

J3J73678111224391624354771369204655737880M1M2時間Fmax=80圖11-3作業(yè)排序甘特圖工件JiJ1J2J3J4J5J6J7加工時間M168

12371124M21195326182工件排序結(jié)果J4J1

J5J2

J6

J3

J7加工時間23112691852J4J1J5J2J6

J3J712/27/202374若存在一個n/3/P/Fmax問題，且mint1i≥maxt2i或mint3i≥mint2i(i=1，2，……，n)，則可采用Johnson法排序。求解步驟為：（1）先找出mint1i≥maxt2i或mint3i≥mint2i關(guān)系（2）將3臺設(shè)備變換成2臺假想設(shè)備MA和MB，并令

tAi=t1i+

t2i；tBi=t2i+

t3i（3）依據(jù)

tAi和tBi，采用Johnson法則進(jìn)行作業(yè)排序

二、多個工件在三臺設(shè)備上的作業(yè)排序(采用Johnson法則)試采用Johnson法則進(jìn)行作業(yè)排序工件設(shè)備J1J2J3

J4M1158612M23156M341057表11-17加工時間表例：有一個4/3/P/Fmax問題，其加工時間如表11-17所示12/27/202375解：①∵mint1i=6maxt2i=6存在mint1i≥maxt2imint3i=4mint2i=1存在mint3i≥mint2i

∴可采用Johnson法求解該作業(yè)排序問題(具備其一即可)。

②

計算tAi和tBi，列于表11-18中表11-18tAi、tBi與排序結(jié)果學(xué)生自己練習(xí)繪制排序結(jié)果甘特圖工件設(shè)備J1J2J3

J4(MA)tAi1891118(MB)tBi，7111013排序結(jié)果J2J4J3J1t1i812615t2i1653t3i107548202641926314419333848③依據(jù)11-18中的tAi和tBi，采用Johnson法進(jìn)行作業(yè)排序。排序結(jié)果與Fmax如表11-18及圖11-4所示。Fmax=4812/27/202376J2J4J3J18

126151

65389

20263141448

20264110

7549

192633384448M1M2M3時間圖11-4排序結(jié)果甘特圖12/27/202377n個工件在m臺設(shè)備上排序是比較困難的。但是，對于2個工件在m臺設(shè)備上排序問題，運(yùn)用圖解法雖然不一定求到最佳解，卻可以求到比較令人滿意的解。例：2個工件在4臺機(jī)器上加工，每個工件的加工順序不同。J1的加工順序是M1，M2，M3，M4；J2的加工順序是M4，M2，M1，M3，其加工時間如表11-19所示。顯然，這是一個非流水作業(yè)排序問題，是一個一般的排序問題，故可用2/4/G/Fmax表示，也可用2/4/G/Cmax表示。三、兩個工件在m臺設(shè)備上的作業(yè)排序該問題亦可用加工描述矩陣D與加工時間矩陣T表示為：表11-19加工時間表（一）用圖解法求解設(shè)備工件M1M2M3M4J12

541J225

3612/27/202378第四節(jié)多臺設(shè)備作業(yè)排序（1）畫平面直角坐標(biāo)，橫、縱軸分別為J1、J2的加工時間，對應(yīng)橫軸下部的甘特圖與對應(yīng)縱軸左側(cè)的甘特圖分別表示J1、J2加工順序及其所對應(yīng)的加工時間，原點(diǎn)O為時間起點(diǎn)。找出表示J1、J2總加工時間的坐標(biāo)點(diǎn)D(12，16)。（2）劃去不可能同時加工兩個工件的時間。開始時，J1在M1上加工，M1便不能加工J2，故劃去方格Ⅰ的區(qū)域，同理劃去方格Ⅱ、Ⅲ、Ⅳ的區(qū)域。（3）從原點(diǎn)開始，在未劃去的區(qū)域中，連線到終點(diǎn)D。連線若為45°角，表示2個工件同時在被加工。例如A點(diǎn)(6,6)，表示J1在M1上加工早已完畢，正在M2上加工；J2在M4上加工剛好完畢，正準(zhǔn)備進(jìn)入M2上加工，但由于M2正在加工J1，所以，又等了1個單位時間到B點(diǎn)(7,6)，此時，M2剛好加工完J1。從B點(diǎn)開始，M2加工J2，M3加工J1；接著M1加工J2，M4加工J1。到了C點(diǎn)(12,11)，M4剛好加工完J1，M2剛好加工完J2。C點(diǎn)到D點(diǎn)是豎直線，此段時間J1已加工完畢，M1和M3只加工J2。三、兩個工件在m臺設(shè)備上的作業(yè)排序例，解：該問題可采用圖解法求作業(yè)排序的解。12/27/202379例，解：（3）由原點(diǎn)向D點(diǎn)引連線時，盡量按45°角方向引線，并使等待時間最小。在實(shí)際操作上，這種排序方法常常通過目視、徒手畫的方法完成的，所以，不能保證求得最佳的排序結(jié)果，只能求得較令人滿意的結(jié)果。從作圖求解過程可知：J1工件沒有等待時間，F(xiàn)1max=12；J2加工等待時間為1，所以，F(xiàn)2max=17。當(dāng)然此問題也可寫成C1max=12；C2max=17。該圖解法求解2/4/G/Cmax問題的過程如圖11-5所示。12/27/202380圖11-5圖解法求解2/4/G/Cmax過程圖J1J2M1M227M311M412M4M2611M113M316IIIIIIIVA(6,6)B(7,6)C(12,11)D(12,16)12/27/202381例，解：上述作業(yè)排序問題2/4/G/Fmax,三、兩個工件在m臺設(shè)備上的作業(yè)排序的排序結(jié)果如圖11-6所示。2,2,2(1,4,4)（2）212（2）142（5）7（5）127（4）1114（3）17

（6）61112

（1）Fmax=Cmax

=17J1J2J2J2J2J1J1J1M1M2M3M4o時間圖11-6作業(yè)排序甘特圖1,1,12,3,11,2,21,3,32,2,22,4,32,1,412/27/202382三、兩個工件在m臺設(shè)備上的作業(yè)排序（二）用啟發(fā)式算法求解1、請同學(xué)們按能動作業(yè)計劃構(gòu)成步驟求解。前述的2/4/G/Fmax,可采用按能動作業(yè)計劃構(gòu)成步驟求解，其求解(排序)過程及結(jié)果如表11-20與圖11-7所示。12/27/202383表11—20能動作業(yè)計劃構(gòu)成表t

Ot}TkT

kT*M*Oj11,1,12,1,400262M11,1,121,2,22,1,420766M42,1,431,2,22,2,2277127M21,2,241,3,32,2,277111211M31,3,351,4,42,2,2117121212M22,2,261,4,42,3,11112121412M41,4,472,3,12,4,31214141714M12,3,182,4,3141717M32,4,312/27/202384（二）用啟發(fā)式算法求解1、按能動作業(yè)計劃構(gòu)成步驟求解根據(jù)11-20可繪出如圖11-7所示的該問題作業(yè)排序甘特圖。由圖11-7可見，采用啟發(fā)式算法，按能動作業(yè)計劃構(gòu)成步驟進(jìn)行求解，作業(yè)排序結(jié)果甘特圖與圖解法得出的圖11-6所示的甘特圖相同，說明兩種方法求解結(jié)果相同。1,1,12,3,11,2,22,2,21,3,32,4,32,1,4(1,4,4)（2）212（2）142（5）7（5）127（4）1114（3）17

（6）61112

（1）Fmax

=Cmax

=17J1J2J2J2J2J1J1J1M1M2M3M4o時間圖11-7作業(yè)排序甘特圖12/27/202385（二）用啟發(fā)式算法求解2、按無延遲作業(yè)計劃構(gòu)成步驟求解其求解(排序)過程及結(jié)果如表11-21與圖11-7所示。(見下一頁)由表11-2中的欄與欄可看出，構(gòu)成作業(yè)計劃(排序)中所選中的設(shè)備與工件及其安排次序均與表11-20相同，說明排序結(jié)果相同，繪出的表示作業(yè)排序結(jié)果的甘特圖肯定也與圖11-7相同，這里不再另外繪出。前述的2/4/G/Fmax,M*Oj可采用按無延