作業(yè)排序與生產(chǎn)作業(yè)計劃培訓課件

第十章作業(yè)排序與生產(chǎn)作業(yè)計劃第一節(jié)作業(yè)排序的基本概念第二節(jié)流水作業(yè)排序問題第三節(jié)單件作業(yè)排序問題第四節(jié)多臺設(shè)備作業(yè)排序1/5/20231引言

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

Ji加工完的總加工時間；ri——Ji到達工序時間，即可以開始加工的最早時間；di——Ji的完工期限；ai——Ji在車間允許停留的時間（Ji進入車間到完工時刻之間的時間間隔：ai=di－ri）；Wij——Ji在第j道工序前的等待時間，Ji總的等待時間：1/5/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的流程時間,即工件在車間的實際停留時間,Fmax——最長流程時間,Fmax=max{Fi},即一批工件中的最長流程時間;Li——Ji工件的延遲時間，1/5/20238第一節(jié)作業(yè)排序的基本概念當Li>0時為正延遲,即Ji的實際完工時間超過了完工期限;當Li<0

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

排序問題常見的分類方法有按機器、工件、目標函數(shù)的特征分類。1.按機器的種類和數(shù)量不同,可以分成單臺機器的排序問題多臺機器的排序問題對于多臺機器的排序問題,按工件加工路線的特征,單件作業(yè)排序問題——加工路線不同流水作業(yè)排序問題——加工路線相同可以分成第一節(jié)作業(yè)排序的基本概念1/5/2023102.按工件到達車車間的情況不不同,可以分分成靜態(tài)的排序問問題——排排序時所有有工件都已到到達,可以一一次對它們進進行排序.動態(tài)的排序問問題——排排序時工件件陸續(xù)到達,要隨時安排排它們的加工工順序3.按目標函數(shù)的的性質(zhì)不同,也可劃分不不同的排序問問題單臺機器的排排序使平均流程時間最短使誤期完工工件數(shù)最少……多臺機器的排排序：不同目目標排序問題題單目標排序問問題：以往研研究的對象多目標排序問問題：很少有有人研究第一節(jié)作作業(yè)排序的基基本概念12/28/2022114.另外，按參參數(shù)的性質(zhì)質(zhì)，可以劃劃分為確定型排序序問題———指加加工時間和和有關(guān)參數(shù)數(shù)是已知確定的量隨機型排序序問題———加工時時間和有關(guān)關(guān)參數(shù)為隨隨機變量這兩種排序序問題的解解法本質(zhì)上上不同?，F(xiàn)只討論幾幾種有代表表性的排序序問題。第一節(jié)作作業(yè)排序序的基本概概念12/28/202212通常常采采用用Conway等等人人提提出出的的排排序序方方法法。。這這個個方方法法主主要要涉涉及及到到4個個參參數(shù)數(shù)，，只只用用4個個參參數(shù)數(shù)就就可可以以表表示示大大多多數(shù)數(shù)不不同同的的排排序序問問題題。。這這4個個參參數(shù)數(shù)通通常常表表示示為為：：n/m/A/B。。n為工工件件數(shù)數(shù)；；m為機機器器數(shù)數(shù)B為目目標標函函數(shù)數(shù),通通常常是是使使其其值值最最小小A為車車間間類類型型，，通通常常有有以以下下幾幾種種情情況況，，在在A的的位位置置：：(1)若標標以以"F",則則代代表表流流水水作作業(yè)業(yè)排排序序問問題題(2)若標標以以““P”,則則表表示示流流水水作作業(yè)業(yè)排排列列排排序序問問題題，，也也常被被稱稱為為““同同順順序序””排排序序問問題題(3)若標標以以““G”,則則表表示示一一般般單單件件作作業(yè)業(yè)排排序序問問題題。。第一一節(jié)節(jié)作作業(yè)業(yè)排排序序的的基基本本概概念念12/28/202213當m=1時時，，A處處為為空空白白。。因因為為對對于于單單臺臺機機器器的的排排序序問問題題來來說說，，不不存存在在所所謂謂的的加加工工路路線線問問題題，，當當然然也也就就談?wù)劜徊坏降绞鞘橇髁魉髯鳂I(yè)業(yè)排排序序問問題題還還是是單單件件作作業(yè)業(yè)的的排排序序問問題題了了。。通過過n/m/A/B這4個個符符號號，，就就可可以以簡簡捷捷的的表表述述一一般般的的排排序序問問題題了了。。例例如如，，n/3/P/Cmax表示示n個工工件件經(jīng)經(jīng)3臺臺機機器器加加工工的的流流水水作作業(yè)業(yè)排排列列排排序序問問題題，，目目標標函函數(shù)數(shù)是是使使最最長長完完工工時時間間最最短短。。第一一節(jié)節(jié)作作業(yè)業(yè)排排序序的的基基本本概概念念12/28/202214第十章作作業(yè)排序序與生產(chǎn)作業(yè)業(yè)計劃回顧排序問題常見見的分類方法法有按機器、工件、目標函數(shù)的特征分類。。排序問題由4個參數(shù)表示示：n/m/A/B。n為工件數(shù)；m為機器數(shù)B為目標函數(shù),通常是使其其值最小A為車間類型，，通常有以下下幾種情況，，在A的位置置：(1)若標以“F”,則代表流流水作業(yè)排序序問題。(2)若標以“P”,則表示流流水作業(yè)排列列排序問題，，也常被稱為為“同順序””排序問題。。(3)若標以“G”,則表示一一般單件作業(yè)業(yè)排序問題。。Cmax——最長完完工時間；Fmax——最長流流程時間；Lmax——最長延延遲時間。Lmax=max{Li}.即在在一批工件中中找出的最大大延遲時間。。當Li>0時為正延遲,即Ji的實際完工時時間超過了完完工期限;當Li<0時為負延遲,即Ji提前完工;當Li=0時為零延遲,即Ji按期完工。例如：n/3/P/Cmax表示n個工件經(jīng)3臺臺機器加工的的流水作業(yè)排排列排序問題題，目標函數(shù)數(shù)是使最長完完工時間最短短。12/28/202215流水作業(yè)排序序問題的基本本特征是每個個工件的加工工路線都一致致。在流水生生產(chǎn)線上制造造不同的零件件,遇到的的就是流水作作業(yè)排序問題題。我們說加加工路線一致致,是指工件件的流向一致致,并不要求求每個工件必必須經(jīng)過加工工路線上每臺臺機器加工。。如果某些工工件不經(jīng)某些些機器加工,則設(shè)相應(yīng)的的加工時間為為零。一般說來,對對于流水作業(yè)業(yè)排序問題,工件在不不同機器上的的加工順序不不盡一致。但但本節(jié)要討論論的是一種特特殊情況,即即所有工件在在各臺機器上上的加工順序序都相同的情情況。這就是是排列排序問問題。流水作作業(yè)排列排序序問題常被稱稱作"同順序序"排序問題題。對于一般般情形,排列列排序問題的的最優(yōu)解不一一定是相應(yīng)的的流水作業(yè)排排序問題的最最優(yōu)解,但一一般是比較好好的解;對于于僅有2臺和和3臺機器的的特殊情況,可以證明,排列排序問問題下的最優(yōu)優(yōu)解一定是相相應(yīng)流水作業(yè)業(yè)排序問題的的最優(yōu)解。本節(jié)只討論排排列排序問題題。但對于2臺機器的排排序問題,實實際上不只是是排列排序問問題，因為兩兩者的最優(yōu)解解及其解法是是相同的。第二節(jié)流水水作業(yè)排序問問題12/28/202216一、最最長流流程時時間Fmax的計算算最長流流程時時間就就是工工件在在車間間實際際停留留的最最長時時間。。本節(jié)所所討論論的是是n/m/ρρ/Fmax問題,目標標函數(shù)數(shù)是使使最長長流程程時間間最短短。最最長流流程時時間又又稱作作加工工周期期,它它是從從第一一個工工件在在第一一臺機機器開開始加加工時時算起起,到到最后后一個個工件件在最最后一一臺機機器上上完成成加工工時為為止所所經(jīng)過過的時時間。。由于于假設(shè)設(shè)所有有工件件的到到達時時間都都為零零(r=0，i=1,2,……,n),所所以Fmax等于排排在末末位加加工的的工件件在車車間的的停留留時間間,也也等于于一批批工件件的最最長完完工時時間Cmax。第二節(jié)節(jié)流流水作作業(yè)排排序問問題12/28/202217設(shè)n個工件件的加加工順順序為為S=(S1,S2,…,Sn),其其中Si為排第第i位加工工的工工件的的代號號。以以Ck(si)表示示工件件Si在機器器Mk上的完完工時時間,Psik表示工工件Si在Mk上的加加工時時間間,k=1,2,…,m；i=1,2,…,n則Ck(si)可按按以下下公式式計算算:C1(si)=C1(si-1)+Psi1Ck(si)=max{Ck-1(si),Ck(si-1)}+Psik(11——1)第二節(jié)節(jié)流流水作作業(yè)排排序問問題顯然，，當ri=0時時，F(xiàn)max=Cm(sn)在知道道了上上述計計算Fmax公式后后，便便可直直接在在工件件加工工的時時間矩矩陣上上從左左向右右計算算完工工時間間。12/28/202218第二節(jié)流流水作業(yè)排排序問題例11.1有一個6/4/p/Fmax問題,其加加工時間如如下表所示示。當按順序S=(6,1,5,2,4,3)加工工時,求Fmax表11-1加工時時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi442433112/28/202219i615243Pi1244213Pi2544576Pi3555857Pi4143234表11-2順順序序S下的的加工時時間矩陣陣261012131671115202733121722303542132125323846Fmax=4612/28/202220Johnson算法:(1)從從加工工時間矩矩陣中找找出最短短的加工工時間。。(2)若若最短短的加工工時間出出現(xiàn)在M1上,則對對應(yīng)的工工件盡可可能往前前排；若若最短加加工時間間出現(xiàn)在在M2上，則對對應(yīng)工件件盡可能能往后排排。然后后,從從加工時時間矩陣陣中劃去去已排序序工件的的加工時時間。若若最短加加工時間間有多個個,則則任挑一一個往前前排。(3)若若所有有工件都都已排序序,停停止.否否則,轉(zhuǎn)轉(zhuǎn)步驟驟(1).第二節(jié)流流水水作業(yè)排排序問題題二、n/2/F/Fmax問題的最最優(yōu)算法法12/28/202221第二節(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/28/202222i１２３４５６ai５１８５３４bi８２２４７４表11-4改改進算法法見教材303頁Johnson改進算法：１.將所有ai≤bi的工件件按ai值不減的的順序排成一一個列Ａ；２.將所有ai＞bi的工件件按bi值不增的順序序排成一個列列Ｂ；３.將Ａ放到到Ｂ之前，就就構(gòu)成了最優(yō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/28/202223當我們從應(yīng)用用Johnson法則求求得的最優(yōu)順順序中任意去去掉一些工件件時,余下的的工件仍構(gòu)成成最優(yōu)順序。。如對例11.2的最優(yōu)優(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)順序。但是是,工件的加加工順序不能能顛倒,否則則不一定是最最優(yōu)順序。同同時,我們還要指出出,Johnson法則只是一個個充分條件,不是必要要條件。不符符合這個法則則的加工順序序,也可能是是最優(yōu)順序。。對例11.2順序(2,5,6,4,1,3)不符合Johnson法則,但但它也是一一個最優(yōu)順序序。第二節(jié)流水水作業(yè)排序問問題12/28/202224例11.2順序序(2,5,6,4,1,3)i２５６４１３ai１３４５５８bi２７４４８２31481318261115192729Fmax*(2,5,6,4,1,3)=2912/28/202225第二二節(jié)節(jié)流流水水作作業(yè)業(yè)排排序序問問題題三、、一一般般n/m/P/Fmax問問題題的的啟啟發(fā)發(fā)式式算算法法對于于3臺臺機機器器的的流流水水車車間間排排序序問問題題,只只有有幾幾種種特特殊殊類類型型的的問問題題找找到到了了有有效效算算法法。。對對于于一一般般的的流流水水車車間間排排列列排排序序問問題題,可可以以用用分分支支定定界界法法。。用用分分支支定定界界法法可可以以保保證證得得到到一一般般n/m/P/Fmax問問題題的的最最優(yōu)優(yōu)解解。。但但對對于于實實際際生生產(chǎn)產(chǎn)中中規(guī)規(guī)模模較較大大的的問問題題,計計算算量量相相當當大大,以以至至連連電電子子計計算算機機也也無無法法求求解解。。同同時時,還還需需考考慮慮經(jīng)經(jīng)濟濟性性。。如如果果為為了了求求最最優(yōu)優(yōu)解解付付出出的的代代價價超超過過了了這這個個最最優(yōu)優(yōu)解解所所帶帶來來的的好好處處,也也是是不不值值得得的的。。為了了解解決決生生產(chǎn)產(chǎn)實實際際中中的的排排序序問問題題,人人們們提提出出了了各各種種啟啟發(fā)發(fā)式式算算法法。。啟啟發(fā)發(fā)式式算算法法以以小小的的計計算算量量得得到到足足夠夠好好的的結(jié)結(jié)果果,因因而而十十分分適適用用。。下下面面介介紹紹求求一一般般n/m/p/Fmax問問題題近近優(yōu)優(yōu)解解(Nearoptimalsolution)的的啟啟發(fā)發(fā)式式算算法法。。12/28/202226第二二節(jié)節(jié)流流水水作作業(yè)業(yè)排排序序問問題題(一一)帕帕爾爾姆姆(Palmer)法法1965年年,D.S.Palmer提提出出按按工工件件斜斜度度指指標標排排序序的的啟啟發(fā)發(fā)式式算算法法。。設(shè)設(shè)：：工工件件的的斜斜度度指指標標為為i，，k為笫笫k臺設(shè)設(shè)備備，，m為設(shè)設(shè)備備數(shù)數(shù)，，Pik為i工工件件在在Mk上上加加工工時時間間，，k為為設(shè)設(shè)備備的的任任意意序序數(shù)數(shù)，，（（k=1,2,3,…………,m））i=∑mk=1［k－（m+1）/2］Pik從該該式式中中求求出出各各工工件件的的i，，再按按著著不不使使i增加加的原原則則排排列列各各個個工工件件的的加加工工順順序序，，就就可可以以得得出出令令人人滿滿意意的的結(jié)結(jié)果果。。12/28/20222713912915132413261828工件i設(shè)備工時1234Pi11263Pi28429Pi34582表11-5加加工工時間矩矩陣例11.3有有一個4/3/F/Fmax排序問問題（即即4個工工件3臺臺設(shè)備，，流水作作業(yè)排序序問題，，目標是是使最長長流程時時間最短短），各各個工件件在每臺臺設(shè)備上上的加工工時間如如下面的的加工時時間矩陣陣表所示示，試采采用Palmer法法求解。。Fmax=2812/28/202228按照排序序為：S=（2，1，3，，4）工件i設(shè)備工時2134Pi12163Pi24829Pi3548223912614162511182628Fmax=2812/28/202229第二節(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/28/202230P322習習題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求解過過程：：排序為為：S=(1,4,3,2)12/28/202231按照S=(1,4,3,2)計計算最最長流流程時時間：：i1432Pik1459Pik5367Pik4536Pik67321510192669161015193216232634Fmax=3412/28/202232(二)關(guān)鍵鍵工件件法關(guān)鍵工工件法法是1983年年提出出的一一個啟啟發(fā)式式算法法。其其步驟驟如下下:(1)計算算每個個工件件的總總加工工時間間Pi=∑Pij,找找出總總加工工時間間最長長的工工件C(j=1.2.3.………m),將將其作作為關(guān)關(guān)鍵工工件。。(2)對于于余下下的工工件,若若Pi1≦Pim,則按Pi1不減的的順序序排成成一個個序列列Sa；若若Pi1＞Pim，則按Pim不增的的順序序排列列成一一個序序列Sb。(3)順序序(sa,C,Sb)即為所所求順順序（（近優(yōu)優(yōu)解））。第二節(jié)節(jié)流流水水作業(yè)業(yè)排序序問題題12/28/202233表11-6工工件在每臺臺設(shè)備上的的單件工時時與總工時時(見教材305頁)第二節(jié)流流水作業(yè)業(yè)排序問題題例：有4個個工件，在在3臺設(shè)備備上加工，，每個工件件在每臺設(shè)設(shè)備上加工工的單件工工時消耗如如表11-6所示。。試采用關(guān)關(guān)鍵工件法法求近優(yōu)解解（近優(yōu)排排序）。i=1,2,3,4；m=1,2,3工件i1234Pi11263Pi28429Pi34582Pi13111614312412/28/202234解：（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)優(yōu)解的順序序（Sa,C,Sb））為（工工件1,2,3,4）第二節(jié)流流水作業(yè)業(yè)排序問題題12/28/202235表11-6工工件件在在每每臺臺設(shè)設(shè)備備上上的的單單件件工工時時與與總總工工時時工件i1234Pi11263Pi28429Pi3458213912913152413182628Fmax計計算算過過程程12/28/202236P322習習題題2：：請請用用關(guān)關(guān)鍵鍵工工件件法法排排序序并并計計算算最最長長流流程程時時間間i1234Pi11954Pi25763Pi34635Pi46237時間求和16241719排序序為為：：S=（（1，，4，，2，，3））關(guān)鍵鍵工工件件法法求求解解過過程程如如下下：：12/28/202237按照S=（1，4，2，，3）計算最最長流程時間間i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=3312/28/202238(三)CDS法(Campbell,Dudek,Smith三人提提出)(見見教材305頁)第二節(jié)流流水作業(yè)排序序問題工件i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+Pi31291011表11-7用用CDS法法求解L=1時：按按照Johnson法得到加加工順序為：：1，2，3，4L=2時：按按照Johnson法得到加加工順序為：：2，3，1，412/28/2022398912618102711231929Fmax計算如如下表所示Fmax=29若加工順序為為（2，3，，1，4）時，按Johnson算法Fmax=29，所以取加加工順序（1，2，3，，4）Fmax=28為最優(yōu)解。。工件i設(shè)備工時2314Pi12613Pi24289Pi35842第二節(jié)流流水作業(yè)排序序問題212/28/202240P322習題題2：請用CDS法排序序并計算最長長流程時間i1234Pi11954Pi25763Pi34635Pi46237關(guān)鍵工件法求求解過程如下下：12/28/202241排序為為：S1=（1，4，，3，，2）i1234L=1Pi11954Pi46237i1234Pi11954Pi25763Pi34635Pi462371、L=1時：：12/28/202242排序為為：S1=（1，4，，3，，2）i1432Pi11459Pi25367Pi34536Pi467321510196916261015193216232634Fmax=3412/28/202243排序為：：S1=（1，，4，，2，，3））i1234L=2Pi1616117Pi4108612i1234Pi11954Pi25763Pi34635Pi462372、L=2時：：12/28/202244排序為：：S1=（1，4，2，3）i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=3312/28/202245排序為：：S1=（1，，4，，2，，3））i1234L=3Pi110221412Pi415151215i1234Pi11954Pi25763Pi34635Pi462373、L=3時：：12/28/202246排序為：：S1=（1，4，2，3）i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=33所以最最終排排序為為：S1=（1，，4，2，，3））滿意意解。。12/28/202247三、采采用Johnson法則則解決決多個個工件件在三三臺設(shè)設(shè)備上上的作作業(yè)排排序若存在在一個個n/3/P/Fmax問題題，且且mint1i≥maxt2i或或mint3i≥mint2i(i=1，2，………，，n)，則則可采采用Johnson法排排序。。求解步步驟為為：（1））先找找出mint1i≥maxt2i或或mint3i≥mint2i關(guān)關(guān)系（2））將3臺設(shè)設(shè)備變變換成成2臺臺假想想設(shè)備備MA和MB，，并令令tAi=t1i+t2i；；tBi=t2i+t3i（3））依據(jù)據(jù)tAi和和tBi，，采用用Johnson法法則進進行作作業(yè)排排序試采用用Johnson法法則進進行作作業(yè)排排序工件設(shè)備J1J2J3

J4M1158612M23156M341057表11-17加加工工時間間表例：有有一個個4/3/P/Fmax問問題，，其加加工時時間如如表11-17所示示12/28/202248解：①∵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法進進行作作業(yè)排排序。。排序序結(jié)果果與Fmax如表11-18及圖圖11-4所示示。Fmax=4812/28/202249J2J4J3J181261516538920263141448202641107549192633384448M1M2M3時間間圖11-4排排序結(jié)果果甘特圖12/28/202250單件作業(yè)排排序是最一一般的排序序問題，也也是最復(fù)雜雜的一種排排序問題。。該問題本本身容易表表達，也能能看出該問問題所需要要求解的是是什么，但但是朝著求求解方向作作任何推進進都是極為為困難的。。許多人在在此問題上上都進行了了探索，但但一無所獲獲者大有人人在。第三節(jié)單單件作業(yè)業(yè)排序問題題12/28/202251第三節(jié)單單件作業(yè)業(yè)排序問題題一、問題的的描述對一般的單單件作業(yè)排排序問題，，每個工件件都有其獨獨特的加工工路線，工工件沒有一一定的流向向。但是，，對于流水水作業(yè)的排排序問題，，第k道道工序永遠遠在MK上進行，沒有有必要將工工序號與機機器號分開開。而對于于一般的單單件作業(yè)排排序問題，，要描述一一道工序需需要i、、j、k三三個參數(shù)，，即i、、j、k表表示第i個個工件的的第j道工工序在Mk(第k臺機機器上)上上進行的。。所以，可可以用加工工描述矩陣陣的形式來來描述所有有工件的加加工。加工工描述矩陣陣的形式如如加工描述述矩陣D所所示。加工描述矩矩陣的每一一行描述一一個工件的的加工過程程(第1行行描述第一一個工件的的加工過程程，第二行行描述第2個工件的的加工過程程)。D的的每一組數(shù)數(shù)中的第1列數(shù)表示示工件序號號；D的每每組數(shù)中的的第2列數(shù)數(shù)碼相同，，說明第2列表示工工序號；D的每一組組數(shù)中的第第3列數(shù)表表示設(shè)備序序號。12/28/202252第三節(jié)單單件件作業(yè)排排序問題題二、一般般n/m/G/Fmax問題的啟啟發(fā)式算算法n/m/G/Fmax為n個工工件，m臺機器器，一般般單件作作業(yè)排序序問題，，使最大大流程時時間最短短。對這這類作業(yè)業(yè)排序問問題，可可以用分分支定界界法或整整數(shù)規(guī)劃劃法求最最優(yōu)解。。但是，，都是無無效的方方法。為為此，在在實際工工作中，，多采用用啟發(fā)式式算法。。為了對對研究啟啟發(fā)式算算法有所所幫助，，先介紹紹兩種十十分重要要的作業(yè)業(yè)計劃及及其構(gòu)成成方法。。12/28/202253(一)兩兩種種作業(yè)計計劃的構(gòu)構(gòu)成一般說來來，在可可行的加加工順序序下，可可以擬定定出無數(shù)數(shù)種作業(yè)業(yè)計劃。。其中，，各工序序都按最最早可能能開始工工作的時時間安排排作業(yè)計計劃，稱稱為半能能動作業(yè)業(yè)計劃。。任何一一臺機器器的每段段空閑時時間都不不足以加加工一道道可加工工工序的的半能動動作業(yè)計計劃，又又稱為能能動作業(yè)業(yè)計劃。。無延遲作作業(yè)計劃劃是指沒沒有任何何延遲出出現(xiàn)的能能動作業(yè)業(yè)計劃。。所謂“延延遲”是是指工件件等待加加工時，，機器出出現(xiàn)空閑閑(即即使這這段空閑閑時間不不足以完完成一道道工序的的加工)。能動作業(yè)業(yè)計劃和和無延遲遲作業(yè)計計劃在研研究一般般單件作作業(yè)排序序問題時時有重要要作用。。二、一般般n/m/G/Fmax問題的啟啟發(fā)式算算法12/28/202254△能動作業(yè)業(yè)計劃與與無延遲遲作業(yè)計計劃構(gòu)成成過程中中涉及到到的4個個符號：：若將每安安排一道道工序稱稱為“一一步”。。設(shè)：St}—為第第t步步之前前已排序序工序構(gòu)構(gòu)成的部部分作業(yè)業(yè)計劃；；Ot}—為為第t步步可以排排序的工工序集合合；Tk——為為Ot}中工序Ok的的最早早可能開開工時間間；Tk——為Ot}中中工序Ok的的最早可能完完工時間。顯然：Ok工序的作業(yè)業(yè)時間=Tk-Tk12/28/202255設(shè)t=1,S1}為空集，O1}為各工件第一一道工序的集集合。求T*=min|T’k|,并求出T*出現(xiàn)的機器器M*。如果果M*有多臺臺，則任選一一臺。從Ot}中挑出滿足以以下兩個條件件的工序Oj，需要機器M*加工，且且Tj<T*。將確定的工序序Oj放入St}，從Ot}中消去Oj，并將Oj的緊后工序放放入Ot}，使t=t+1。若還有未安排排的工序，轉(zhuǎn)轉(zhuǎn)步驟（2））；否則，停停止。二、一般n/m/G/Fmax問題的啟發(fā)式式算法(一)兩兩種作業(yè)計劃劃的構(gòu)成P3101、能動作業(yè)業(yè)計劃的構(gòu)成成步驟12/28/202256例11.5：：有一個2/3/G/Fmax問題題，其加工描描述矩陣D和和加工時間矩矩陣T分別為為：試構(gòu)成一一個能動作業(yè)業(yè)計劃。P310按表11~9所示的能能動作業(yè)計劃劃構(gòu)成過程，，可繪出圖11~4能動動作業(yè)計劃時時間安排(排排序)圖—能動作業(yè)計劃劃。12/28/202257表11—9能能動作作業(yè)計計劃的的構(gòu)成成T*＝min{Tk}tOt}TkTTkT*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/28/202258能動作作業(yè)計計劃的的甘特特圖；；最大大流程程：Fmax=13012345678901234M1——M2——M3——1,1,12,2,12372,1,31,2,3731,3,22,3,2781312/28/202259對表表11~9所所示示的的能能動動作作業(yè)業(yè)計計劃劃（（作作業(yè)業(yè)時時間間排排序序））構(gòu)構(gòu)成成過過程程可可描描述述為為下下列列過過程程：：（1））當當t=1時時O1}為為：：2個工件件、、可可以以在在第第1道道工工序序上上、、進進行行第第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*=minTk}=2。。可見見，，T*=2出出現(xiàn)現(xiàn)的的機機器器M*=M1。。在這這一一步步中中M1上僅僅有有一一道道工工序序（（1,1,1））可可以以排排序序。。所所以以，，首首先先安安排排（（1,1,1））在在M1上加加工工。。（2））、、（（3））………（略略））（4））當當t=4時時，，O4}=（1,3,2））；；（（2,2,1））}，，T4=7或或3，，T′′4=8或或7。。T*=7，，出出現(xiàn)現(xiàn)在在M1上，，將（2,2,1））安安排排在在M1上加加工工。。（5））………（略略））（6））當當t=6時時，，O6}=（2,3,2））}，，T6=8，，T′′6=13。。此此時時只只剩剩下下（2,3,2）），，將（2,3,2））安安排排在在M2上加加工工。。該排排序序問問題題最最后后完完工工時時間間為為13。。1、、能能動動作作業(yè)業(yè)計計劃劃的的構(gòu)構(gòu)成成步步驟驟(一一)兩兩種種作作業(yè)業(yè)計計劃劃的的構(gòu)構(gòu)成成12/28/202260在作作業(yè)業(yè)計計劃劃中中，，““延延遲遲””是是指指工工件件等等待待加加工工，，而而機機器器出出現(xiàn)現(xiàn)空空閑閑（（空空閑閑時時間間不不能能完完成成一一道道工工序序的的加加工工作作業(yè)業(yè)））。。所所以以，，無無延延遲遲作作業(yè)業(yè)計計劃劃是是指指沒沒有有任任何何延延遲遲出出現(xiàn)現(xiàn)的的能能動動作作業(yè)業(yè)計計劃劃。。無延延遲遲作作業(yè)業(yè)計計劃劃的的構(gòu)構(gòu)成成步步驟驟設(shè)t=1,S1}為空空集集，，O1}為各各工工件件第第一一道道工工序序的的集集合合。。求T*=min|T’’k|,并并求求出出T*出出現(xiàn)現(xiàn)的的機機器器M*。。如如果果M*有有多多臺臺，，則則任任選選一一臺臺。。從Ot}中挑挑出出滿滿足足以以下下兩兩個個條條件件的的工工序序Oj，需需要要機機器器M*加加工工，，且且Tj=T*。。將確確定定的的工工序序Oj放入入St}，從從Ot}中消消去去Oj，并并將將Oj的緊緊后后工工序序放放入入Ot}，使使t=t+1。。若還還有有未未安安排排的的工工序序，，轉(zhuǎn)轉(zhuǎn)步步驟驟（（2））；；否否則則，，停停止止。。2、、無無延延遲遲作作業(yè)業(yè)計計劃劃的的構(gòu)構(gòu)成成(排排序序)步步驟驟P31112/28/202261例：：對對例11.5：：有有一一個個2/3/G/Fmax問問題題，，其其加加工工描描述述矩矩陣陣D和和加加工工時時間間矩矩陣陣T分分別別為為：：試試構(gòu)構(gòu)成成一一個個無無延延遲遲作作業(yè)業(yè)計計劃劃。。P312解：：表表11——10無無延延遲遲作作業(yè)業(yè)計計劃劃的的構(gòu)構(gòu)成成tOt}TkTTkT*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/28/202262無延遲作業(yè)計計劃的甘特圖圖；最大流程程：Fmax=13012345678901234M1—M2—M3—1,1,12,2,12372,1,31,2,3731,3,22,3,27121312/28/202263(二)作業(yè)業(yè)排序的三類類啟發(fā)式算法法1、優(yōu)先調(diào)度度法(見教材311~314頁)對應(yīng)用優(yōu)先調(diào)度法則則的說明2.隨機抽樣樣法3.概率調(diào)度度法8個主要的優(yōu)優(yōu)先調(diào)度法則則：P312二、一般n/m/G/Fmax問題題的啟發(fā)式算算法12/28/2022641、SPT法法則(最短加加工時間規(guī)則則)例題SPT法則就就是優(yōu)先選擇擇加工時間最最短的工序。。即排序時將將各個工件的的加工時間由由短到長進行行排隊，排在在前面的加工工時間最短的的工序優(yōu)先按按排加工。其其優(yōu)點是，使使平均流程時時間F最短，，使在制品的的占用量減少少，其缺點是是沒有考慮交交貨期，有可可能會使部分分工件延誤了了交貨期。例：現(xiàn)有一個個6/1/F問題，其加加工時間與交交貨期如表11-10所所示，試采用用SPT法則則進行作業(yè)排排序。(三)優(yōu)先先調(diào)度法則例例題(此為單單臺設(shè)備排序序問題例題)表11-10加工工時間與交貨貨期表工序號J1J2J3J4J5J6加工時間482593交貨期242386321312/28/2022651、SPT法則(最最短加工時時間規(guī)則)例題。解解：25914223123458916F=(2+5+9+14+22+31)=13.8工件號J3J6J1J4J2J5交貨期di8132462332流程時間Fi=Ci259142231延期交貨Li-6-8-158-1-1由求解過程程可知，按按SPT法法則排序順順序為：J3，J6，J1，J4，J2，J5；流程時間分分別為：2，5，，9，，14，22，31；F=13.8；工件件J4延期交貨8個時間單單位。其余余提前完成成(4)統(tǒng)統(tǒng)計延期交交貨狀況：：(3)計算算平均流程程時間(2)計算算各工件加加工流程時時間，標在在加工時間間的右上角角：(1)將各各個工件加加工時間由由短到長排排隊為：J32，，J63，J14，J45，J28，，J59表11-11延延期交交貨統(tǒng)計表表轉(zhuǎn)后例12/28/2022662、EDD規(guī)則(最最早預(yù)定交交貨規(guī)則)例題EDD規(guī)則則就是優(yōu)先先選擇完工工期限緊的的工件。即即，在進行行工件作業(yè)業(yè)排序時，，按工件完完工期限由由緊到松進進行排序，，排在前面面的完工期期限最緊的的工件優(yōu)先先按排加工工。EDD法則的的優(yōu)點是考考慮了交貨貨期，有利利于做到按按期交貨，，使工件中中的最大延延遲時間最最小。其缺缺點是使平平均流程時時間F增加加，增大了了在制品占占用量。(三)優(yōu)優(yōu)先調(diào)度法法則例題(此為單臺臺設(shè)備排序序問題例題題)工序號J1J2J3J4J5J6加工時間482593交貨期2423863213試進行作業(yè)業(yè)排序(使使Lmax最小)。。表11-10加加工時間間與交貨期期例：(仍采采用上例)有一個6/1/Lmax問問題(即6個工件，，1臺機器器，使最大大延遲時間間最小)，，其加工時時間與交貨貨期如表11-10所示。12/28/202267由表11-12計算算可知，該該例采用EDD法則則排序為：：J4、、J3、、J6、、J2、、J1、、J5，，且各工件件延遲時間間均為0。。平均流程程時間F=15.5(三)優(yōu)優(yōu)先調(diào)度法法則例題(此為單臺臺設(shè)備排序序問題例題題)2、EDD規(guī)則(最最早預(yù)定交交貨規(guī)則)例題解：根據(jù)EDD法則則是將完工工期限最緊緊的工序優(yōu)優(yōu)先按排，，為此采用表11-12把交交貨期短短的工件先先按排，再再求出流程程時間與交交貨期相比比較，檢查查是否存在在有延遲時時間的工件件，延遲時時間是多少少，是否可可以在排序序上再進行行調(diào)整。工件號J4J3J6J2J1J5交貨期6813232432加工與流程時間523849延遲時間5710182231表11-12延延遲遲時間分析析表000000轉(zhuǎn)前例12/28/2022683、SPT與EDD混合(結(jié)結(jié)合)法則則例題這是將SPT規(guī)則(最短加工工時間規(guī)則則)與EDD規(guī)則(最早預(yù)定定交貨規(guī)則則)結(jié)合起起來的在單單臺設(shè)備上上的排序方方法。這種種排序方法法克服了SPT與EDD兩個個單一規(guī)則則只能達到到一個目標標的缺點，，可以獲得得較為理想想的結(jié)果。。為了說明明問題方便便，仍以表表11-10所示的的排序問題題為例。(三)優(yōu)優(yōu)先調(diào)度法法則例題(此為單臺臺設(shè)備排序序問題例題題)表11-10加加工時間間與交貨期期表工序號J1J2J3J4J5J6加工時間482593交貨期242386321312/28/202269(三三)優(yōu)優(yōu)先先調(diào)調(diào)度度法法則則例例題題(此此為為單單臺臺設(shè)設(shè)備備排排序序問問題題例例題題)3、、SPT與與EDD混混合合(結(jié)結(jié)合合)法法則則例例題題按SPT與與EDD結(jié)結(jié)合合的的規(guī)規(guī)則則排排序序步步驟驟如如下下：：（1））首首先先根根據(jù)據(jù)EDD規(guī)規(guī)則則排排序序，，即即安安排排一一個個使使Lmaxmin(使使最最長長延延遲遲時時間間最最短短)的的初初步步方方案案。。［［若若該該初初步步方方案案出出現(xiàn)現(xiàn)Lmax=0，，說說明明該該初初步步方方案案已已滿滿足足要要求求。。例例如如表表11-10的的例例子子，，可可按按交交貨貨期期最最短短的的先先安安排排加加工工(即即根根據(jù)據(jù)交交貨貨期期排排序序)。。所所以以，，其其排排序序為為：：J4—J3—J6—J2—J1—J5按此此排排序序可可以以求求得得：：Lmax=max{Li}=-1，，滿滿足足要要求求。］（2））計計算算全全部部生生產(chǎn)產(chǎn)任任務(wù)務(wù)的的總總流流程程時時間間F總=Fmax=max{Fi}=F5=Pi=P4+P3+P6+P2+P1+P5=31（3））找找出出初初步步方方案案中中預(yù)預(yù)定定交交貨貨期期大大于于Fmax的工工件件(可可能能有有多多件件)，，并并按按SPT規(guī)規(guī)則則，，把把其其中中加加工工時時間間最最長長的的工工件件排排在在最最后后加加工工。。在在本本例例中中，，預(yù)預(yù)定定交交貨貨期期大大于于Fmax=31的工工件件只只有有J5，，當然然應(yīng)應(yīng)該該將將J5排在在最最后后加加工工。。12/28/202270（4））舍舍棄棄第第（（3））步步中中已已排排在在最最后后的的J5，余余下下J4—J3—J6—J2—J1重復(fù)復(fù)第第（（2））步步。。此此時時出出現(xiàn)現(xiàn)情情況況如如表表11-13所所示示。。(三三)優(yōu)優(yōu)先先調(diào)調(diào)度度法法則則例例題題(此此為為單單臺臺設(shè)設(shè)備備排排序序問問題題例例題題)3、、SPT與與EDD混混合合(結(jié)結(jié)合合)法法則則例例題題工件排序J4

J3

J6J2J1加工時間與F52384預(yù)定交貨期68132324由表表11-13可可知知，，余余下下5個個工工件件中中J1的F最最大大，，F(xiàn)max=22。。預(yù)預(yù)定定交交貨貨期期大大于于Fmax=22的的有有J1和J2，其其中中J2的加加工工時時間間P2=8為較較大大者者(P2=8>P1=4)，，故按按SPT規(guī)規(guī)則則將將J2排在在第第5順順序序(倒倒數(shù)數(shù)第第2位位)加加工工，，即即將將J2排在在次次后后順順序序上上加加工工。。表11-13余余下下工工件件的的F與與預(yù)預(yù)訂訂交交貨貨期期5710182212/28/202271反復(fù)復(fù)進進行行（（2））、、（（3））步步，，直直到到實實現(xiàn)現(xiàn)既既使使Lmax≦0，，又又使使F(平平均均流流程程時時間間)為為Fmin的排排序序方方案案為為止止。。5710142231表11-14排排序序方方案案及及各各參參數(shù)數(shù)結(jié)結(jié)果果表表(三三)優(yōu)優(yōu)先先調(diào)調(diào)度度法法則則例例題題(此此為為單單臺臺設(shè)設(shè)備備排排序序問問題題例例題題)按SPT與與EDD結(jié)結(jié)合合規(guī)規(guī)則則排排序序，，可可得得出出表表11-10的的排排序序問問題題的的排排序序為為：：J4—J3—J6—J1—J2—J5表11-10排序問題的的結(jié)論如表11-14所所示。3、SPT與與EDD混合合(結(jié)合)法法則例題工件排序J4J3J6J1J2J5加工時間與F523489預(yù)定交貨期68

13242332計劃完成時刻5

710142231交貨延期000000平均流程