加工調(diào)度問(wèn)題的計(jì)算機(jī)仿真模型

.10/11編號(hào)：第六屆計(jì)算機(jī)仿真大賽參賽作品題號(hào):4組別：高年級(jí)作者：XXX學(xué)院：XXX：XXX有關(guān)加工調(diào)度問(wèn)題的計(jì)算機(jī)仿真模型摘要本文討論在工業(yè)生產(chǎn)中,利用建立模型,優(yōu)化多個(gè)零件在多臺(tái)機(jī)器上進(jìn)行加工的順序安排,以提高設(shè)備利用率和生產(chǎn)效率的調(diào)度問(wèn)題。主要建立的模型如下：流水線調(diào)度優(yōu)化模型：通過(guò)利用約翰遜貝爾曼法則找出最優(yōu)結(jié)果排序。首先寫(xiě)出約翰遜貝爾曼法則在多個(gè)機(jī)器〔m>2的算法,根據(jù)算法利用Matlab軟件進(jìn)行計(jì)算機(jī)仿真,得出最優(yōu)加工順序的結(jié)果〔見(jiàn)正文第9頁(yè)。為了形象描述問(wèn)題并得到本系統(tǒng)的流程圖和核心程序的流程圖,利用甘特圖模型進(jìn)行仿真,最終形象的表示機(jī)器設(shè)備的生產(chǎn)進(jìn)度。關(guān)鍵字：加工順序最優(yōu)Matlab甘特圖約翰遜貝爾曼算法目錄一、問(wèn)題重述與分析21.1問(wèn)題的重述21.2問(wèn)題的分析2二、符號(hào)說(shuō)明2三、調(diào)度問(wèn)題模型的建立33.1兩個(gè)工作條件的給出33.3算法的描述43.4問(wèn)題的求解和結(jié)果5四、參考文獻(xiàn)9五、附錄9問(wèn)題重述與分析1.1問(wèn)題的重述工廠中,有n個(gè)不同的配件需要生產(chǎn),每個(gè)配件都必須由m臺(tái)不同的機(jī)器進(jìn)行順序加工處理,配件i在機(jī)器j上所需的處理時(shí)間為t<i,j>。現(xiàn)約定未完工前不允許中斷處理,配件不能拆分成更小配件。要求給出一種配件調(diào)度方案,使所給的n個(gè)配件在盡可能短的時(shí)間內(nèi)處理完成。1.2問(wèn)題的分析此問(wèn)題的求解主要依靠運(yùn)用運(yùn)籌學(xué)相關(guān)理論學(xué)科,解決加工順序的最優(yōu)安排以達(dá)到零件生產(chǎn)效率提高的工業(yè)要求,可以利用約翰遜貝爾曼法則找出最優(yōu)結(jié)果排序,利用matlab軟件進(jìn)行計(jì)算機(jī)仿真,并畫(huà)出形象表達(dá)生產(chǎn)進(jìn)度的甘特圖。符號(hào)說(shuō)明變量含義D1表示第D1種分組No<n,1>表示編號(hào)t2<n,2>t2用來(lái)存放2臺(tái)虛擬機(jī)器存放的時(shí)間t2<:,1>表示第一臺(tái)A<n,m-1>用來(lái)存放m-1種分組方式下,按大小排序后的t2<:,1>B<n,m-1>用來(lái)存放m-1種分組方式下,按大小排序后的t2<:,2>index1<n,m-1>用來(lái)存放m-1種分組方式下,按大小排序后的t2<:,1>零件序號(hào)index2<n,m-1>用來(lái)存放m-1種分組方式下,按大小排序后的t2<:,2>零件序號(hào)newsort<n,m-1>用來(lái)存放m-1種分組方式下,按大小排序后的零件序號(hào),即加工順序T1<n,m,m-1>T1<:,:,i>表示根據(jù)J&B法則第i中分法下的加工順序后的加工時(shí)間表T1<n,m,m-1>T2<:,:,i>表示根據(jù)J&B法則第i中分法下的加工順序后的完工時(shí)間表T<1,m-1>表示m-1種分組方式下的最短工期數(shù)組No_sort<1,n>m-1中分法下的T中元素最小最優(yōu)解加工零件的排序Tmin<n,m>m-1中分法下的T中元素最小最優(yōu)解加工順序后的完工時(shí)間表t1<n,m>對(duì)應(yīng)最優(yōu)排序后的加工時(shí)間矩陣j0表示靠前加工零件的個(gè)數(shù)j1表示靠后加工零件的個(gè)數(shù)i1i1,i2分別表示每輪最小值A(chǔ)<:,D1>、B<:D1>下標(biāo)〔共n次,確定newsort<:,D1>的零件排序i2resultresult=[No,No_sort,Tmin]輸出結(jié)果說(shuō)明第一列元素表示加工順序,第二列表示加工零件編號(hào),第三列到以后為：每個(gè)零件在不同機(jī)器上的完工時(shí)間矩陣調(diào)度問(wèn)題模型的建立3.1兩個(gè)工作條件的給出：n個(gè)工件在m臺(tái)機(jī)器上的加工順序相同。工件在機(jī)器上的加工時(shí)間是給定的<時(shí)間矩陣t<n,m>,t<i,j>表示i零件在機(jī)器j上加工時(shí)間>。問(wèn)題的目標(biāo)是求n個(gè)工件在每合機(jī)器上的最大完工時(shí)間等于最大流程時(shí)間。這種流水線調(diào)度問(wèn)題要在滿足以下兩個(gè)約束條件的前提下,使得加工完所有的工件所花的時(shí)間盡可能地少：1、工件約束每個(gè)工件在每臺(tái)機(jī)器上恰好加工一次,每個(gè)工件在各機(jī)器上加工順序相同。不失一般性,假設(shè)各工件按機(jī)器1至m的順序進(jìn)行加工。各工件在各機(jī)器上的加工時(shí)間已知。2、機(jī)器約束每臺(tái)機(jī)器在任何時(shí)刻至多加工一個(gè)工件,每臺(tái)機(jī)器加工的各工件的順序相同。3.2工件加工順序的原則：置換流水線調(diào)度問(wèn)題實(shí)質(zhì)是如何調(diào)整加工工件的序列,提高機(jī)器的利用率的問(wèn)題,即在同一時(shí)刻正在加工的機(jī)器數(shù)越多,機(jī)器利用率越大口根據(jù)該原則,我們根據(jù)下面規(guī)則安排：1、在前面機(jī)器加工時(shí)間較短、后面機(jī)器加工時(shí)間較長(zhǎng)的工件,安排在序列前。這樣可以使得后面的機(jī)器盡快參加工作,并且后面的機(jī)器不需要作空等待,2、機(jī)器加工時(shí)間較為平均且加工時(shí)間較長(zhǎng)的工件,安排在序列的中部。這樣可以使得各個(gè)機(jī)器在中期的時(shí)候都能得到運(yùn)作。3、前面加工時(shí)間較長(zhǎng),后面加工時(shí)間較短的工件按排在序列尾部。這樣使得前面的機(jī)器能"延遲"完工,后面的機(jī)器盡快完工。3.3算法的描述[1][2]：我們采用約翰遜-貝爾曼法則〔Johnson-Bellmanrule,一下簡(jiǎn)稱J&B1、N種零件在兩臺(tái)機(jī)器上加工〔M1,M2,根據(jù)J&B法則,最短工期加工順序,方法如下：檢索t<:,1>,t<:,2>〔表示各零件分別在M1,M2上加工時(shí)間的各種數(shù)據(jù),找出其中最小值上述最小值如果屬于第一列,則該零件應(yīng)靠前加工,相反,若在第二列則靠后加工2、將J&B法則推廣到m臺(tái)機(jī)器情況,把m臺(tái)機(jī)器分成第1、第2兩組,每組看成一個(gè)機(jī)器,分法如下〔該步為2臺(tái)虛擬機(jī)器假設(shè)過(guò)程組號(hào)〔D1第一組〔加工時(shí)間t2<:,1>第二組〔加工時(shí)間t2<:,2>1M1M2+M3+…+Mm2M1+M2M3+M4+…+Mm………………m-1M1+M2+…+Mm-1Mmm臺(tái)機(jī)器共有m-1種分法,每種分法均按照J(rèn)&B法則找出最短加工期的加工順序。Newsort<:,D1>表示第D1種分組方式下的零件序號(hào)排序〔此部分用子程序I完成3、在D1中分組方式下生成的加工時(shí)間矩陣T1<:,:,D1>和完工時(shí)間矩陣T2<:,:,D1>T2<i,:,D1>,T1<i,:,D1>中i等于newsort<i,D1>T2<n,m,D1>表示第D1種分組方式下的最短工期T表示第m-1種分組方式下的最短工期數(shù)組4、算出T2后,就可以找出m-1種分組方式下的最優(yōu)解了。3.4問(wèn)題的求解和結(jié)果工作流程否工作流程否子程序I開(kāi)始D1>m-1?第D1種分組方式下2個(gè)虛擬機(jī)器,對(duì)應(yīng)加工時(shí)間t2對(duì)加工零件時(shí)間排序：t2<:,1>—A<:,D1>下標(biāo)—index1t2<:,2>—B<:,D1>下標(biāo)—index22臺(tái)機(jī)器下確定零件加工順序—newsort<:,D1>按上加工順序的時(shí)間矩陣—T1<:,:,D1>按約定算法生成按上加工順序的完工時(shí)間矩陣--T1<:,:,D1>將該分組方式下產(chǎn)生的最短工期放入矩陣—TD1=D1+1輸入原始數(shù)據(jù)t是對(duì)T進(jìn)行排序,sort<T>—tminT下標(biāo)—index0最優(yōu)解：最優(yōu)零件排序--No_sort最優(yōu)完工時(shí)間矩陣—Tmin最優(yōu)加工時(shí)間矩陣—t1限制坐標(biāo)范圍畫(huà)出甘特圖結(jié)束輸出結(jié)果：〔包含加工編號(hào),零件編號(hào),最優(yōu)加工時(shí)間絕陣t1,最短工期--result子程序IIii>n?初始線索index1/2下標(biāo)i1=1;i2=1是否最小值下標(biāo)Index1<i1,D1>=0?i1=i1+1否是最小值下標(biāo)Index2<i2,D1>=0?I2=i2+1得到?jīng)]有排位的零件index1/2下標(biāo)i1,i2是A<i1,D1><=B<i2,D1>?說(shuō)明遍歷t2,最小值在第一列零件index1<i1,D1>應(yīng)靠前加工Newsort<i>=index1<i1,D1>遍歷index2<:,D1>,在index2<:,D1>找到零件index1<i1,D1>并致零,index1<i1,D1>也=0說(shuō)明遍歷t2,最小值在第一列零件index2<i2,D1>應(yīng)靠后加工Newsort<n-i+1>=index2<i2,D1>遍歷index2<:,D1>,在index2<:,D1>找到零件index1<i1,D1>并致零,index1<i1,D1>也=0否i=i+1子程序I是否子程序II/甘特圖畫(huà)法子程序II/甘特圖畫(huà)法<過(guò)程1包含一個(gè)條件若j為偶數(shù),線條加粗,為簡(jiǎn)化流程圖,此處未列出>求出加工零件在機(jī)器j上加工時(shí)間x0=Tmin<i,j>-max<Tmin<i-1,j>,Tmin<I,j-1>>是否是否j>n?j=j+11i=i+11j=j+1i=i+1第i個(gè)加工零件在第一個(gè)機(jī)器上加工,開(kāi)始時(shí)間為Tmin<i,1>-x0,結(jié)束時(shí)間為Tmin<i,1>,高度為i,畫(huà)出這一段時(shí)間內(nèi)的加工圖過(guò)程1第i個(gè)加工零件在第j個(gè)機(jī)器上加工,開(kāi)始時(shí)間為Tmin<i,j>-x0,結(jié)束時(shí)間為Tmin<i,j>.高度為i,畫(huà)出這一段時(shí)間內(nèi)的加工圖過(guò)程1標(biāo)出機(jī)器號(hào)j標(biāo)出機(jī)器號(hào)j求出加工零件在機(jī)器j上加工時(shí)間x0=Tmin<I,1>-Tmin<I-1,1>是否j=1?i>n?標(biāo)出第i個(gè)生產(chǎn)的零件編號(hào)—No_sort<i>是i=1?否是否j=1?第一個(gè)加工零件在第一個(gè)機(jī)器上加工,開(kāi)始時(shí)間為0,結(jié)束時(shí)間為Tmin<1,1>,高度為i,畫(huà)出這一段時(shí)間內(nèi)的加工圖過(guò)程1第一個(gè)加工零件在第j個(gè)機(jī)器上加工,開(kāi)始時(shí)間為Tmin<1,j-1>,結(jié)束時(shí)間為Tmin<1,1>.高度為i,畫(huà)出這一段時(shí)間內(nèi)的加工圖過(guò)程1標(biāo)出機(jī)器號(hào)j標(biāo)出機(jī)器號(hào)j根據(jù)上述利用軟件進(jìn)行仿真,最終運(yùn)行結(jié)果為：>>請(qǐng)輸入加工時(shí)間矩陣t<i,j>表示第i個(gè)零件在機(jī)器j上的加工時(shí)間:[1487;2544;6563;7431;1468]result=151511192129192632414233043101929335417233234輸出結(jié)果說(shuō)明第一列元素表示加工順序,第二列表示加工零件編號(hào),第三列到以后為：每個(gè)零件在不同機(jī)器上的完工時(shí)間矩陣甘特圖是一種用來(lái)形象的表示機(jī)器生產(chǎn)進(jìn)度〔加工順序的圖形。此問(wèn)題中求解出的甘特圖如下：參考文獻(xiàn)[1]朱德通著,《最優(yōu)化模型與實(shí)驗(yàn)》[M],同濟(jì)大學(xué)出版社,2003.6[2]宋存利著,《求解多工藝路線車間調(diào)度問(wèn)題的禁忌-遺傳算法》[J],大連交通大學(xué)出版社,2008.4[3]陳國(guó)良著,《遺傳算法及其應(yīng)用》[M],人民郵電出版社,2000.4[4]董立華高秀蓮著,《數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)》[M],天津教育出版社,2009.5附錄有關(guān)工件加工順序的程序：clear;clf;t=input<'請(qǐng)輸入加工時(shí)間矩陣\nt<i,j>表示第i個(gè)零件在機(jī)器j上的加工時(shí)間:\n'>;[nm]=size<t>;%n表示加工零件數(shù),m表示機(jī)器數(shù)t2=zeros<n,2>;%t2用來(lái)存放兩臺(tái)虛擬機(jī)器的時(shí)間A=zeros<n,m-1>;%AB分別存放兩臺(tái)虛擬機(jī)器的時(shí)間排序后的時(shí)間,m-1為根據(jù)約翰遜貝爾曼法則〔Johnson-Bellmanrule,一下簡(jiǎn)稱J&B,當(dāng)m>2,可以分為m-1中情況B=zeros<n,m-1>;%A<:,i>表示第i中分法下的排序方法index1=zeros<n,m-1>;index2=zeros<n,m-1>;%index1index2分別存放兩臺(tái)虛擬機(jī)器的時(shí)間排序后對(duì)應(yīng)的零件序號(hào)newsort=zeros<n,m-1>;%newsort<:,i>表示根據(jù)J&B法則第i中分法下的加工順序T1=zeros<n,m,m-1>;%T1<:,:,i>表示根據(jù)J&B法則第i中分法下的加工順序后的時(shí)間表T2=zeros<n,m,m-1>;%T2<:,:,i>表示根據(jù)J&B法則第i中分法下的加工順序后的最短工期表T=zeros<1,m-1>;%Tmin<n,m>加工完成時(shí)間矩陣,表示i零件在j機(jī)器上完成后的總時(shí)間No_sort=zeros<1,n>;%No_sort為最后根據(jù)m-1中分法下的最后的最優(yōu)解fori=1:n%編號(hào)No<i,1>=i;end%J&B法則模擬兩個(gè)虛擬機(jī)器forD1=1:m-1fori=1:D1t2<:,1>=t2<:,1>+t<:,i>;%機(jī)器1endfori=D1:mt2<:,2>=t2<:,2>+t<:,i>;%機(jī)器2end[A<:,D1>,index1<:,D1>]=sort<t2<:,1>>;%A<:,D1>中保存第D1分法中機(jī)器1中按從小到大的排序值,index1<:,D1>對(duì)應(yīng)的零件下標(biāo)[B<:,D1>,index2<:,D1>]=sort<t2<:,2>>;%B<:,D1>中保存第D1分法中機(jī)器2中按從小到大的排序值,index2<:,D1>對(duì)應(yīng)的零件下標(biāo)endforD1=1:m-1%求m-1中兩個(gè)虛擬機(jī)的排序情況%根據(jù)J&B法則第D1中分法下的加工順序j0=1;j1=1;fori=1:n%思想為：一組中有n個(gè)零件排序,t2<:,1><機(jī)器1中時(shí)間值>,t2<:,2>〔機(jī)器1中時(shí)間值%A<:D1>B<:,D1>分別將機(jī)器1中時(shí)間值、機(jī)器2中時(shí)間值按從小到大排序%判定t2中最小值屬于機(jī)器〔1,2,每次從A<:,D1最小與B<:,D1>最小判定%若newsort<:,D1>對(duì)應(yīng)下標(biāo)確定,則將inde1<:,D1>,index2<:,D1>對(duì)應(yīng)下標(biāo)致零,確保下次不參與最小%值比較i1=1;%i1,i2分別表示每輪最小值A(chǔ)<:,D1>、B<:D1>下標(biāo)〔共n次,確定newsort<:,D1>的零件排序i2=1;%每次均從第一個(gè)最小值開(kāi)始判定whileindex1<i1,D1>==0%如果最小值下標(biāo)為零,已經(jīng)排位,不在比較,i1++;i2++,向下一位走i1=i1+1;endwhileindex2<i2,D1>==0i2=i2+1;endifA<i1,D1><=B<i2,D1>%如果最小值產(chǎn)生在A<：,D1>,即機(jī)器1,則先加工newsort<j0,D1>=index1<i1,D1>;j0=j0+1;%說(shuō)明靠前位置下移forj=1:nifindex2<j,D1>==index1<i1,D1>%遍歷index2,=0說(shuō)明該工件已經(jīng)加入排序中index2<j,D1>=0;index1<i1,D1>=0;%加入排位后,將下標(biāo)致零endendelse%如果最小值產(chǎn)生在B<：,D1>,即機(jī)器2,則最后加工newsort<n-j1+1,D1>=index2<i2,D1>;j1=j1+1;forj=1:nifindex1<j,D1>==index2<i2,D1>%遍歷index1,=0說(shuō)明該工件已經(jīng)加入排序中index1<j,D1>=0;index2<i2,D1>=0;%加入排位后,將下標(biāo)致零endendendendendforD1=1:m-1fori=1:nT1<i,:,D1>=t<newsort<i,D1>,:>;%排序后的時(shí)間矩陣endfori=1:n%為T2第一列賦值forj=1:iT2<i,1,D1>=T2<i,1,D1>+T1<j,1,D1>;endendfori=2:m%為T2第一行賦值forj=1:iT2<1,i,D1>=T2<1,i,D1>+T1<1,j,D1>;endendfori=2:n%為i>1,j>1賦值forj=2:mT2<i,j,D1>=T1<i,j,D1>+max<T2<i-1,j,D1>,T2<i,j-1,D1>>;%實(shí)際含義是：零件i在機(jī)器j上完成的時(shí)間為零件i在機(jī)器j的加工時(shí)間+%零件i在j-1機(jī)器〔滿足要求：順序加工和上一個(gè)零件加工完成中的最大一個(gè)〔每個(gè)機(jī)器一次只能加工一個(gè)零件endendT<D1>=T2<n,m,D1>;%將m-1種結(jié)果產(chǎn)生的最小時(shí)間賦值給Tend%對(duì)T排序,得到m-1中結(jié)果中的最優(yōu)解[tmin,index0]=sort<T>;Tmin=T2<:,:,index0<1>>;%最優(yōu)解中加工完成時(shí)間矩陣〔排序后的,不同與t中零件排序No_sort=newsort<:,index0<1>>;%Tmin每行對(duì)應(yīng)的的零件fori=1:nt1<i,:>=t<No_sort<i>,:>;%對(duì)應(yīng)最優(yōu)排序后的加工時(shí)間矩陣endresult=[No,No_sort,Tmin]fprintf<'輸出結(jié)果說(shuō)明第一列元素表示加工順序,\n第二列表示加工零件編號(hào),第三列到以后為：\n每個(gè)零件在不同機(jī)器上的完工時(shí)間矩陣'>;%畫(huà)出加工零件的甘特圖%變量說(shuō)明以及輸出說(shuō)明%每一行表示一個(gè)零件加工過(guò)程%在線條上的數(shù)字表示第幾個(gè)機(jī)器%圖片開(kāi)始的數(shù)字為零件的編號(hào)%line<>;畫(huà)出i零件在j機(jī)器上的加工情況%text<>;標(biāo)出機(jī)器代號(hào)gridon;axis<[-4Tmin<n,m>+20n+1]>;%限制坐標(biāo)范圍fori=1:nk=No_sort<i>;text<-2,i,int2str<k>>;forj=1:m%畫(huà)出零件編號(hào)ifi==1%第一個(gè)加工零件ifj==1%第一個(gè)機(jī)器加工情況line<[0,Tmin<i,j>],[ii]>;text<Tmin<i,j>/2,i,int2str<j>>;