MATLAB下基于遺傳算法作業車間調度系統開發

于 善，袁逸萍，李曉娟，馬會玲

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

MATLAB下基于遺傳算法作業車間調度系統開發

于 善，袁逸萍，李曉娟，馬會玲

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

針對MATLAB環境下基于遺傳算法的作業車間調度系統的關鍵技術和實現方法進行了研究，提出一種基于MATLAB/GUI的作業車間調度系統的實現方法。對作業車間問題、作業車間遺傳算法思想、作業車間調度系統建立進行描述，并結合對MATLAB/GUI技術、MATLAB與Excel數據交換技術的研究開發了一種方便、實用的作業車間調度系統。通過實例驗證了調度系統的有效與實用性。

遺傳算法；作業車間調度；MATLAB /GUI ; Excel

0 引言

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

1 作業車間問題描述

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

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

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

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

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

車間調度約束條件如下：①每個零件必須按照規定的工序順序加工；②每臺機器每次只能加工一個零件。

2 作業車間調度系統總體框架

基于遺傳算法的作業車間調度系統結構框架基于三層體系的C/S(客戶端/服務器)模式，包括用戶層、業務層和數據層。用戶只需要安裝客戶端后登錄就可以使用系統進行調度計算。所有的系統開發與維護在服務器主機就可以完成，服務器主機需要安裝MATLAB組件運行程序MCR.exe(MATLAB Components Runtime)。作業車間調度系統總體框架如圖1所示。

用戶層是系統與用戶交互的窗口，通過用戶層，用戶可以選擇調度規則、數據輸入、瀏覽調度結果。業務層和數據層是由服務器內的應用程序組成，業務層是系統的過程層，該層包括系統需要的所有功能模塊，是系統實現調度的功能核心；數據層是整個系統的支撐，用于保存業務層需要的數據與調度結果。

3 作業車間調度系統實現關鍵技術

3.1 遺傳算法調度模塊實現技術

遺傳算法調度模塊是該系統中的核心功能模塊，負責系統所有調度請求。遺傳算法調度模塊流程如圖2所示。

圖1 作業車間調度系統總體框架

圖2 遺傳算法調度模塊工作流程

3.1.1 基因編碼

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

3.1.2 種群初始化

為確保初始種群能夠均勻分布，一般在染色體編碼時預先選擇幾個工序號，隨機生成剩余工序編碼序列，然后加入染色體。種群規模大小將影響調度優化的結果以及計算效率，對于作業車間調度問題，種群規模一般取30～200。

3.1.3 確定適應度函數

用xij表示第i個零件是否在第j臺機床上加工，xij取值為：

則車間調度的主函數數學模型如下：

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

其中：k取102。

3.1.4 交叉

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

3.1.5 變異

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

3.2 MATLAB與Excel數據交換模塊實現技術

3.2.1 對Excel中的數據讀取

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

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

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

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

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

else

NumericalData=xlsread([pathname filename]);

xlswrite('NumericalData.xls',NumericalData);

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

end;

D=xlsread('NumericalData.xls');

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

3.2.2 向Excel存儲數據

通常調度結果是以甘特圖表示，但如果零件較多，圖像將會重疊，不易讀取、保存及修改。若將結果以數字的形式輸出，結果不僅直觀，還可以根據實際生產情況進行修改保存，大大提高系統的實用性。MATLAB中的數據可以實現多種格式存儲，使用xlswrite函數可實現向Excel存儲數據。對于以Excel為數據源的程序，希望結果與源數據在一個文件中。函數xlswrite格式[9]為：xlswrite(文件名，變量名，頁數)。實現保存到任意路徑的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 系統實現

為了很好地展示所開發系統的可應用性，以單機單資源車間調度為實例進行說明。現某工廠單機單資源作業車間加工10個工件，每個工件有10道工序，經過實際調研，獲得：

時間矩陣T與加工機器矩陣M均為10×10矩陣，行數表示工件編號，列數表示該工件的工序編號，T矩陣中的數字表示該編號工件該工序的加工時間，M矩陣中的數字表示該編號工件該工序的加工機器編號。

系統中涉及的遺傳算法相關系數如表1所示。

表1 遺傳算法相關系數

調度結果甘特圖如圖3所示，結果輸出如圖4所示，結果輸出與甘特圖一一對應。

圖4中的矩陣從上到下每行表示每臺機器上零件加工的順序，每個數字代表零件號及工序號，例如：第一行表示第10臺機器上零件的加工順序，101表示第10個工件的第1道工序。

圖4 調度結果輸出

5 結束語

以MATLAB/GUI為基礎，本文提出一種作業車間遺傳算法可視方法，實現了基于遺傳算法的作業車間調度系統的研究與開發。通過MATLAB與Excel數據交換技術，簡化系統矩陣輸入操作，提高系統效率。用戶還可以保存調度結果，再通過Excel表格輸出；并可以根據實際生產情況修改調度結果，提高系統的指導性。

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

[2] 范路橋,常會友,朱旭東.一種改進的作業車間調度算法及其實現[J].計算機集成制造系統,2005,11(5):673-677.

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

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

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

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

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

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

[9] 羅華飛.MATLAB GUI設計學習手記[M].第2版.北京：北京航空航天大學出版社，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

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

2015- 01- 08；

2015- 08- 30

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

TP273∶TH186

A