加工調度問題的計算機仿真模型

1、 編號：第六屆計算機仿真大賽參賽作品題號: 4 組別： 高年級 作者： xxx 學院： xxx 聯(lián)系電話： xxx 有關加工調度問題的計算機仿真模型摘要本文討論在工業(yè)生產(chǎn)中，利用建立模型，優(yōu)化多個零件在多臺機器上進行加工的順序安排，以提高設備利用率和生產(chǎn)效率的調度問題。主要建立的模型如下：流水線調度優(yōu)化模型：通過利用約翰遜貝爾曼法則找出最優(yōu)結果排序。首先寫出約翰遜貝爾曼法則在多個機器（m>2）的算法，根據(jù)算法利用matlab軟件進行計算機仿真，得出最優(yōu)加工順序的結果（見正文第9頁）。為了形象描述問題并得到本系統(tǒng)的流程圖和核心程序的流程圖，利用甘特圖模型進行仿真，最終形象的表示機器設備的生

2、產(chǎn)進度。關鍵字：加工順序最優(yōu) matlab 甘特圖 約翰遜貝爾曼算法目錄一、問題重述與分析21.1問題的重述21.2問題的分析2二、符號說明2三、調度問題模型的建立33.1 兩個工作條件的給出33.3算法的描述43.4問題的求解和結果5四、參考文獻9五、附錄9一、 問題重述與分析1.1問題的重述工廠中，有n個不同的配件需要生產(chǎn)，每個配件都必須由m臺不同的機器進行順序加工處理，配件i在機器j上所需的處理時間為t(i,j)?，F(xiàn)約定未完工前不允許中斷處理，配件不能拆分成更小配件。要求給出一種配件調度方案，使所給的n個配件在盡可能短的時間內(nèi)處理完成。1.2問題的分析 此問題的求解主要依靠運用運籌學相關

3、理論學科，解決加工順序的最優(yōu)安排以達到零件生產(chǎn)效率提高的工業(yè)要求，可以利用約翰遜貝爾曼法則找出最優(yōu)結果排序，利用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種分組方式下

4、，按大小排序后的 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表示靠前加工零

5、件的個數(shù)j1表示靠后加工零件的個數(shù)i1i1,i2分別表示每輪最小值a(:,d1)、b(:d1)下標（共n次，確定newsort(:,d1)的零件排序）i2resultresult=no,no_sort,tmin輸出結果說明第一列元素表示加工順序，第二列表示加工零件編號，第三列到以后為：每個零件在不同機器上的完工時間矩陣三、 調度問題模型的建立3.1 兩個工作條件的給出：n個工件在m臺機器上的加工順序相同。工件在機器上的加工時間是給定的(時間矩陣t(n,m),t(i,j)表示i零件在機器j上加工時間)。問題的目標是求n個工件在每合機器上的最大完工時間等于最大流程時間。這種流水線調度問題要在滿足以

6、下兩個約束條件的前提下，使得加工完所有的工件所花的時間盡可能地少：1、工件約束每個工件在每臺機器上恰好加工一次，每個工件在各機器上加工順序相同。不失一般性，假設各工件按機器1至m的順序進行加工。各工件在各機器上的加工時間已知。2、機器約束每臺機器在任何時刻至多加工一個工件，每臺機器加工的各工件的順序相同。3.2 工件加工順序的原則：置換流水線調度問題實質是如何調整加工工件的序列，提高機器的利用率的問題，即在同一時刻正在加工的機器數(shù)越多，機器利用率越大口根據(jù)該原則，我們根據(jù)下面規(guī)則安排：1、在前面機器加工時間較短、后面機器加工時間較長的工件，安排在序列前。這樣可以使得后面的機器盡快參加工作，并且

7、后面的機器不需要作空等待，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) 上述最小值如果屬

8、于第一列，則該零件應靠前加工，相反，若在第二列則靠后加工2、將j&b法則推廣到m臺機器情況，把m臺機器分成第1、第2兩組，每組看成一個機器，分法如下（該步為2臺虛擬機器假設過程）組號（d1）第一組（加工時間t2(:,1)）第二組（加工時間t2(:,2)）1m1m2+m3+ +mm2m1+m2m3+m4+ +mmm-1m1+m2+ +mm-1mmm臺機器共有m-1種分法，每種分法均按照j&b法則找出最短加工期的加工順序。newsort(:,d1)表示第d1種分組方式下的零件序號排序（此部分用子程序i完成）3、在d1中分組方式下生成的加工時間矩陣t1(:,:,d1)和完工時間矩陣t

9、2(:,:,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問題的求解和結果工作流程否子程序i開始d1>m-1 ?第d1種分組方式下2個虛擬機器，對應加工時間t2對加工零件時間排序：t2(:,1)a(:,d1) 下標index1t2(:,2)b(:,d1) 下標index22臺機器下確定零件加工順序newsort(:,d1)按上加工順序的時間矩陣t1(:,:,d1)按約定算法生成按上加工順序的完工時間矩

10、陣- t1(:,:,d1)將該分組方式下產(chǎn)生的最短工期放入矩陣td1=d1+1輸入原始數(shù)據(jù)t是對t進行排序，sort(t)tmint下標index0最優(yōu)解：最優(yōu)零件排序 -no_sort 最優(yōu)完工時間矩陣tmin最優(yōu)加工時間矩陣t1限制坐標范圍畫出甘特圖結束輸出結果：（包含加工編號，零件編號，最優(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是

11、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

12、包含一個條件若j為偶數(shù)，線條加粗，為簡化流程圖，此處未列出)求出加工零件在機器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個加工零件在第一個機器上加工，開始時間為tmin(i,1)-x0，結束時間為tmin(i,1)，高度為i,畫出這一段時間內(nèi)的加工圖過程1第i個加工零件在第j個機器上加工，開始時間為tmin(i,j)-x0，結束時間為tmin(i,j). 高度為i,畫出這一段時間內(nèi)的加工圖過程1標出機器號j 標出機器號j 求出加工零件在機器j上加工時間x0 =tmin(i

13、,1)-tmin(i-1,1)是否j=1 ? i>n ?標出第i個生產(chǎn)的零件編號no_sort(i)是i =1 ?否是否j=1 ?第一個加工零件在第一個機器上加工，開始時間為0，結束時間為tmin(1,1)，高度為i,畫出這一段時間內(nèi)的加工圖過程1第一個加工零件在第j個機器上加工，開始時間為tmin(1,j-1)，結束時間為tmin(1,1). 高度為i,畫出這一段時間內(nèi)的加工圖過程1標出機器號j 標出機器號j 根據(jù)上述利用軟件進行仿真，最終運行結果為：>>請輸入加工時間矩陣t(i,j)表示第i個零件在機器j上的加工時間:1 4 8 7;2 5 4 4;6 5 6 3;7 4

14、 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輸出結果說明第一列元素表示加工順序，第二列表示加工零件編號，第三列到以后為：每個零件在不同機器上的完工時間矩陣甘特圖是一種用來形象的表示機器生產(chǎn)進度（加工順序的）圖形。此問題中求解出的甘特圖如下：四、 參考文獻1 朱德通著，最優(yōu)化模型與實驗m,同濟大學出版社，2003.62 宋存利著，求解多工藝路線車間調度問題的禁忌-遺傳算法j,大 連交通大學出版社，2008.4 3陳國良著，遺傳算法及其應用m,人民郵電

15、出版社，2000.44董立華 高秀蓮著 ，數(shù)學建模與數(shù)學實驗m , 天津教育出版社,2009.5五、 附錄有關工件加工順序的程序：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,可以分為

16、 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中分

17、法下的加工順序后的最短工期表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);

18、 % a(:,d1)中保存第d1分法中機器1中按從小到大的排序值，index1(:,d1)對應的零件下標 b(:,d1), index2(:,d1)=sort(t2(:,2); % b(:,d1)中保存第d1分法中機器2中按從小到大的排序值，index2(:,d1)對應的零件下標endfor 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中時間值、機器

19、2中時間值按從小到大排序% 判定t2中最小值屬于機器（1,2），每次從a(:,d1）最小與b(:,d1)最小判定% 若newsort(:,d1)對應下標確定，則將inde1(:,d1),index2(:,d1)對應下標致零，確保下次不參與最小% 值比較 i1=1; % i1,i2分別表示每輪最小值a(:,d1)、b(:d1)下標（共n次，確定newsort(:,d1)的零件排序） i2=1; % 每次均從第一個最小值開始判定 while index1(i1,d1)=0 % 如果最小值下標為零，已經(jīng)排位，不在比較，i1+;i2+,向下一位走 i1=i1+1; end while index2(i

20、2,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)=inde

21、x2(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 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

22、 %為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種結果產(chǎn)生的最小時間賦值給tend% 對t排序，

23、得到m-1中結果中的最優(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)排序后的加工時間矩陣 endresult=no,no_sort,tminfprintf('輸出結果說明第一列元素表示加工順序，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); t