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

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