于 善，袁逸萍，李曉娟，馬會(huì)玲

(新疆大學(xué) 機(jī)械工程學(xué)院，新疆 烏魯木齊 830047)

MATLAB下基于遺傳算法作業(yè)車間調(diào)度系統(tǒng)開發(fā)

于 善，袁逸萍，李曉娟，馬會(huì)玲

(新疆大學(xué) 機(jī)械工程學(xué)院，新疆 烏魯木齊 830047)

針對MATLAB環(huán)境下基于遺傳算法的作業(yè)車間調(diào)度系統(tǒng)的關(guān)鍵技術(shù)和實(shí)現(xiàn)方法進(jìn)行了研究，提出一種基于MATLAB/GUI的作業(yè)車間調(diào)度系統(tǒng)的實(shí)現(xiàn)方法。對作業(yè)車間問題、作業(yè)車間遺傳算法思想、作業(yè)車間調(diào)度系統(tǒng)建立進(jìn)行描述，并結(jié)合對MATLAB/GUI技術(shù)、MATLAB與Excel數(shù)據(jù)交換技術(shù)的研究開發(fā)了一種方便、實(shí)用的作業(yè)車間調(diào)度系統(tǒng)。通過實(shí)例驗(yàn)證了調(diào)度系統(tǒng)的有效與實(shí)用性。

遺傳算法；作業(yè)車間調(diào)度；MATLAB /GUI ; Excel

0 引言

作業(yè)車間調(diào)度(Job-shop Scheduling Problem,JSP)[1-2]一直以來都是學(xué)術(shù)界廣泛研究的熱點(diǎn)。近年來，伴隨著遺傳算法不斷地改進(jìn)與日臻成熟，使用VB、C++等計(jì)算機(jī)語言開發(fā)的遺傳算法調(diào)度系統(tǒng)不斷出現(xiàn)。但由于系統(tǒng)處理矩陣能力較差，運(yùn)算效率低以及矩陣輸入過程繁瑣等問題，導(dǎo)致系統(tǒng)在實(shí)際應(yīng)用中不能滿足用戶需求。由于MATLAB在矩陣處理、數(shù)值計(jì)算、模擬仿真等方面強(qiáng)大的優(yōu)勢，并且遺傳算法程序是在MATLAB中完成編譯的，因此，本文以MATLAB為基礎(chǔ)，使用可視化工具GUI(圖形交互頁面)以及MATLAB與Excel數(shù)據(jù)交換技術(shù)，設(shè)計(jì)并開發(fā)出了更加實(shí)用、便捷的MATLAB環(huán)境下基于遺傳算法的作業(yè)車間調(diào)度系統(tǒng)。

1 作業(yè)車間問題描述

典型的作業(yè)車間調(diào)度問題可描述為：n個(gè)零件在m臺(tái)功能不同的機(jī)器上加工，各待加工零件具有多道工序且每道工序只能在一臺(tái)機(jī)器上完成，每個(gè)零件的加工路線不同，要求在已知各零件在每臺(tái)機(jī)器的加工順序及加工時(shí)間的前提下，確定各機(jī)器上所加工的全部零件的加工順序，以滿足某些加工性能指標(biāo)，如總加工時(shí)間最短。已知[3]：

(1) 待加工零件pi(i=1,2,…,n)。

(2) 加工機(jī)器mj(j=1,2,…,m)。

(3) 加工工序使用的機(jī)器號(hào)oij(i=1,2,…,n;j=1,2,…,m)表示加工第i個(gè)零件的第j道工序的機(jī)器號(hào)，oij=0表示零件pi的j道工序不加工。

(4) 加工時(shí)間cij(i=1,2,…,n;j=1,2,…,m)表示零件pi在第j臺(tái)機(jī)器上加工的時(shí)間。

車間調(diào)度約束條件如下：①每個(gè)零件必須按照規(guī)定的工序順序加工；②每臺(tái)機(jī)器每次只能加工一個(gè)零件。

2 作業(yè)車間調(diào)度系統(tǒng)總體框架

基于遺傳算法的作業(yè)車間調(diào)度系統(tǒng)結(jié)構(gòu)框架基于三層體系的C/S(客戶端/服務(wù)器)模式，包括用戶層、業(yè)務(wù)層和數(shù)據(jù)層。用戶只需要安裝客戶端后登錄就可以使用系統(tǒng)進(jìn)行調(diào)度計(jì)算。所有的系統(tǒng)開發(fā)與維護(hù)在服務(wù)器主機(jī)就可以完成，服務(wù)器主機(jī)需要安裝MATLAB組件運(yùn)行程序MCR.exe(MATLAB Components Runtime)。作業(yè)車間調(diào)度系統(tǒng)總體框架如圖1所示。

用戶層是系統(tǒng)與用戶交互的窗口，通過用戶層，用戶可以選擇調(diào)度規(guī)則、數(shù)據(jù)輸入、瀏覽調(diào)度結(jié)果。業(yè)務(wù)層和數(shù)據(jù)層是由服務(wù)器內(nèi)的應(yīng)用程序組成，業(yè)務(wù)層是系統(tǒng)的過程層，該層包括系統(tǒng)需要的所有功能模塊，是系統(tǒng)實(shí)現(xiàn)調(diào)度的功能核心；數(shù)據(jù)層是整個(gè)系統(tǒng)的支撐，用于保存業(yè)務(wù)層需要的數(shù)據(jù)與調(diào)度結(jié)果。

3 作業(yè)車間調(diào)度系統(tǒng)實(shí)現(xiàn)關(guān)鍵技術(shù)

3.1 遺傳算法調(diào)度模塊實(shí)現(xiàn)技術(shù)

遺傳算法調(diào)度模塊是該系統(tǒng)中的核心功能模塊，負(fù)責(zé)系統(tǒng)所有調(diào)度請求。遺傳算法調(diào)度模塊流程如圖2所示。

圖1 作業(yè)車間調(diào)度系統(tǒng)總體框架

圖2 遺傳算法調(diào)度模塊工作流程

3.1.1 基因編碼

如果在編碼與解碼過程中沒有考慮加工機(jī)器順序約束，就會(huì)出現(xiàn)死鎖情況。與其他編碼方式相比，基于加工工序的編碼方式[5]具有不冗余、不易產(chǎn)生死鎖和不依賴啟發(fā)式算法等優(yōu)點(diǎn)，因此本文采用基于加工工序的編碼方式。以矩陣實(shí)現(xiàn)染色體編碼，第1行為加工順序編碼,第2行為與第1行工序相對應(yīng)的加工設(shè)備編碼[6],如：

3.1.2 種群初始化

為確保初始種群能夠均勻分布，一般在染色體編碼時(shí)預(yù)先選擇幾個(gè)工序號(hào)，隨機(jī)生成剩余工序編碼序列，然后加入染色體。種群規(guī)模大小將影響調(diào)度優(yōu)化的結(jié)果以及計(jì)算效率，對于作業(yè)車間調(diào)度問題，種群規(guī)模一般取30～200。

3.1.3 確定適應(yīng)度函數(shù)

用xij表示第i個(gè)零件是否在第j臺(tái)機(jī)床上加工，xij取值為：

則車間調(diào)度的主函數(shù)數(shù)學(xué)模型如下：

F(x)=k[f(x)]-lg[f(x)].

其中：k取102。

3.1.4 交叉

為避免只能在現(xiàn)有的種群中尋找最優(yōu)解以及促進(jìn)各個(gè)體之間優(yōu)秀基因的交流，遺傳算法引入交叉操作。其方法步驟如下：①從種群中隨機(jī)選取兩個(gè)個(gè)體；②隨機(jī)選擇交叉位置(一般取染色體非開始與結(jié)束的位置)；③交換兩個(gè)體的部分染色體(即工序號(hào))，得到兩個(gè)新的個(gè)體；④找出新個(gè)體相對原個(gè)體多余、缺失的染色體，使用缺失的染色體修復(fù)多余的染色體，再交換相對應(yīng)的機(jī)器號(hào)。

3.1.5 變異

為防止調(diào)度過程中出現(xiàn)早熟現(xiàn)象以及增加種群的多樣性，引入變異操作，本文采用基于加工順序變異方式，即在染色體上隨機(jī)選擇一個(gè)變異點(diǎn)，并以此點(diǎn)為基點(diǎn)，分別向左、右兩側(cè)尋找與該點(diǎn)工件號(hào)相同的點(diǎn)，再隨機(jī)產(chǎn)生一個(gè)整數(shù)，將該工件號(hào)與加工設(shè)備號(hào)移動(dòng)到位置之前，產(chǎn)生新的加工順序，完成順序的變異操作。

3.2 MATLAB與Excel數(shù)據(jù)交換模塊實(shí)現(xiàn)技術(shù)

3.2.1 對Excel中的數(shù)據(jù)讀取

在實(shí)際使用中，由于有些矩陣維數(shù)較大，輸入較為繁瑣且易出錯(cuò)。因此，預(yù)先將數(shù)據(jù)存在Excel表格中，再通過MATLAB讀取Excel，達(dá)到數(shù)據(jù)交換的目的。

MATLAB讀取Excel中的數(shù)據(jù)較為復(fù)雜，可使用函數(shù)xlsread實(shí)現(xiàn)[8]，此函數(shù)主要涉及的參數(shù)為文件名及讀取范圍。函數(shù)形式為T=xlsread(‘文件名’，變量名)，實(shí)現(xiàn)導(dǎo)入任意路徑Excel數(shù)據(jù)代碼如下：

[filename,pathname]=uigetfile({'*.xls'},'Choose the file');

if(filename==0 & pathname==0)/

msgbox('您沒有選文件，請重新打開！','打開文件出錯(cuò)','error');

else

NumericalData=xlsread([pathname filename]);

xlswrite('NumericalData.xls',NumericalData);

msgbox('讀取數(shù)據(jù)完畢！','確定','warn');

end;

D=xlsread('NumericalData.xls');

set(handles.edit1,’string’,D);

3.2.2 向Excel存儲(chǔ)數(shù)據(jù)

通常調(diào)度結(jié)果是以甘特圖表示，但如果零件較多，圖像將會(huì)重疊，不易讀取、保存及修改。若將結(jié)果以數(shù)字的形式輸出，結(jié)果不僅直觀，還可以根據(jù)實(shí)際生產(chǎn)情況進(jìn)行修改保存，大大提高系統(tǒng)的實(shí)用性。MATLAB中的數(shù)據(jù)可以實(shí)現(xiàn)多種格式存儲(chǔ)，使用xlswrite函數(shù)可實(shí)現(xiàn)向Excel存儲(chǔ)數(shù)據(jù)。對于以Excel為數(shù)據(jù)源的程序，希望結(jié)果與源數(shù)據(jù)在一個(gè)文件中。函數(shù)xlswrite格式[9]為：xlswrite(文件名，變量名，頁數(shù))。實(shí)現(xiàn)保存到任意路徑的Excel代碼如下：

[filename,pathaname]=uiputfile({'*.xls','Excel'},'open');

if (filename!=0&pathaname!=0)

xlswrite([path file],str2num(變量名),'sheet1');

msgbox('the result is saved in sheet1','save');

else

msgbox('you havenot saved the result','not save');

end;

4 系統(tǒng)實(shí)現(xiàn)

為了很好地展示所開發(fā)系統(tǒng)的可應(yīng)用性，以單機(jī)單資源車間調(diào)度為實(shí)例進(jìn)行說明?，F(xiàn)某工廠單機(jī)單資源作業(yè)車間加工10個(gè)工件，每個(gè)工件有10道工序，經(jīng)過實(shí)際調(diào)研，獲得：

時(shí)間矩陣T與加工機(jī)器矩陣M均為10×10矩陣，行數(shù)表示工件編號(hào)，列數(shù)表示該工件的工序編號(hào)，T矩陣中的數(shù)字表示該編號(hào)工件該工序的加工時(shí)間，M矩陣中的數(shù)字表示該編號(hào)工件該工序的加工機(jī)器編號(hào)。

系統(tǒng)中涉及的遺傳算法相關(guān)系數(shù)如表1所示。

表1 遺傳算法相關(guān)系數(shù)

調(diào)度結(jié)果甘特圖如圖3所示，結(jié)果輸出如圖4所示，結(jié)果輸出與甘特圖一一對應(yīng)。

圖4中的矩陣從上到下每行表示每臺(tái)機(jī)器上零件加工的順序，每個(gè)數(shù)字代表零件號(hào)及工序號(hào)，例如：第一行表示第10臺(tái)機(jī)器上零件的加工順序，101表示第10個(gè)工件的第1道工序。

圖4 調(diào)度結(jié)果輸出

5 結(jié)束語

以MATLAB/GUI為基礎(chǔ)，本文提出一種作業(yè)車間遺傳算法可視方法，實(shí)現(xiàn)了基于遺傳算法的作業(yè)車間調(diào)度系統(tǒng)的研究與開發(fā)。通過MATLAB與Excel數(shù)據(jù)交換技術(shù)，簡化系統(tǒng)矩陣輸入操作，提高系統(tǒng)效率。用戶還可以保存調(diào)度結(jié)果，再通過Excel表格輸出；并可以根據(jù)實(shí)際生產(chǎn)情況修改調(diào)度結(jié)果，提高系統(tǒng)的指導(dǎo)性。

[1] 余琦瑋.基于遺傳算法的作業(yè)車間調(diào)度問題研究[D].杭州：浙江大學(xué),2004：1-30.

[2] 范路橋,常會(huì)友,朱旭東.一種改進(jìn)的作業(yè)車間調(diào)度算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)集成制造系統(tǒng),2005,11(5):673-677.

[3] 祁建程,楊建剛.并行混合遺傳算法在車間調(diào)度問題的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(1):233-236.

[4] 周宏根,戚雪峰,景旭文,等.基于遺傳算法的作業(yè)車間調(diào)度研究與應(yīng)用[J].現(xiàn)代制造工程,2006(8):5-8.

[5] Hansen E, Mladenovic N. Variable neighborhood search: principles and applications[J].Operational Research，2001，130(2):449-467.

[6] 袁志玲.基于遺傳算法的車間調(diào)度問題研究與應(yīng)用[D].烏魯木齊：新疆大學(xué),2013：1-25.

[7] 歐陽浩,王萌,黃鎮(zhèn)謹(jǐn),等.用遺傳算法解決物流中的倉庫選址問題[J].制造業(yè)自動(dòng)化,2014(2):51-52.

[8] 羅天添,劉書豪.MATLAB-Excel數(shù)據(jù)交換方法與實(shí)例[J].電腦編程技巧與維護(hù),2010(18):63-65,68.

[9] 羅華飛.MATLAB GUI設(shè)計(jì)學(xué)習(xí)手記[M].第2版.北京：北京航空航天大學(xué)出版社，2011.

(英文摘要Development of Job-shop Scheduling System Based on Genetic Algorithm in MATLAB

YU Shan, YUAN Yi-ping, LI Xiao-juan, MA Hui-ling

(College of Mechanical Engineering, Xinjiang University, Urumqi 830047, China)

On the research of the key technology and realization method of job-shop scheduling system based on genetic algorithm in MATLAB, a kind implementation method of job-shop scheduling system based on MATLAB/GUI is put forward. Job-shop pro-blems, job-shop genetic algorithm and job-shop scheduling system are established by mathematical description. And combined with the research of the technology of MATLAB/GUI and data exchange technology between MATLAB and Excel, a convenient and practical job-shop scheduling system is developed.The effectiveness and practicability of the scheduling system are demonstrated by an example of job-shop scheduling .

job-shop scheduling ; MATLAB/GUI; genetic algorithm; Excel

1672- 6413(2015)06- 0005- 03

國家自然科學(xué)基金資助項(xiàng)目(51065028，51365054)；新疆維吾爾自治區(qū)科技廳“十二五”重大專項(xiàng)(201130110-1 )

2015- 01- 08；

2015- 08- 30

于善(1988-)，男，山東棗莊人，在讀碩士研究生，研究方向： 計(jì)算機(jī)集成制造。

TP273∶TH186

A