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

《加工調(diào)度問題的計算機仿真模型》由會員分享，可在線閱讀，更多相關(guān)《加工調(diào)度問題的計算機仿真模型（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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