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