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

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