基于改进遗传算法的多目标柔性车间调度问题研究

潘 颖，周柏城

（大连海洋大学机械与动力工程学院，大连116023）



基于改进遗传算法的多目标柔性车间调度问题研究

潘 颖，周柏城

（大连海洋大学机械与动力工程学院，大连116023）

摘要：通过对车间生产调度的特点和算法的研究，建立了离散车间多目标动态调度的数学模型及设计了改进的遗传算法。以最大完工时间最短、总延期时间最小和设备总负荷最小这3个目标作为车间生产优化目标调度模型。利用改进的遗传算法确定车间调度的最优解。最后通过实例分析，验证了算法的可行性。

关键词：车间调度；多目标；遗传算法

在当今激烈的市场竞争中，为了增强企业的核心竞争力，企业就要对现有的生产管理方式进行改善，而车间的生产调度更是生产管理的核心技术［1］。随着专家学者对各类经典车间调度问题的不断的深入研究，相继出现了许多经典车间调度问题的新的理论与方法［2-6］，这些理论与方法对制造业生产车间调度的研究具有重要的研究意义，能够提高制造业的生产效率，同时也能带来经济利益。

本文建立了3个优化目标的车间生产调度模型，分别是最大完工时间最短、总延期时间最小和设备总负荷最小，通过改进遗传算法寻求车间调度的最优解。最后通过车间调度案例，证实改进的遗传算法比传统算法更可行。

1　柔性车间调度的模型建立

1.1柔性作业车间问题参数描述

多目标柔性作业车间调度是指生产车间中在m台设备上加工n个工件，每个工件包含ni个事先确定加工顺序的工序，每个工序可以在多台设备上加工。其建模应用符号参数如下：

tijs：加工工件ji的第j步工序在s上设备的加工所需时间；

ETi：加工工件ji完成最后一步工序所需时间；

ETijs：加工工件ji的第j步工序在s设备上完成加工的时间；

DTi：工件ji的交货时间；

Ttijs：工件ji的第j步工序在设备上的调整时间；

qs：设备s的故障率；

Xijs为0，1变量，如果工件ji的第j道工序在设备s上加工取值为1，否则为0；

其中，针对上述建模并做如下假设：

（1）所有设备一开始均处于正常状态，没有设备故障。

（2）工件完成上一道加工工序后，立即开始下一道加工工序，之前的设备处于空闲。

（3）加工一旦开始，就不能中断，机器出现故障除外。

（4）已知不同工序在每台设备上的调整时间

（5）工件在加工设备上的加工与装卸时间都能确定，计入加工时间。

1.2目标函数模型的建立

1.2.1目标函数：

（1）最大完工时间最短：

minf1=min（maxETi）（1）

（2）总延期最小：

2　改进遗传算法的设计

2.1染色体编码

染色体编码利用整数编码方式，并对染色体进行两层编码，分别是基于其加工工序编码方式和加工设备的编码方式，弥补了传统遗传算法采用单层编码的基因多样性和完整性不足的缺点。获得到每条染色体长度是为工件数量，ni为第i个工件的工序数。染色体被分成前后两个部分，前部分染色体对应工件加工工序，后部分染色体对应相应的加工设备。

2.2适应度函数

采用线性尺度转换方法，其适应度函数，转换公式为：

2.3选择

在Matlab的遗传算法工具箱中，选择里面的锦标赛方法进行函数选择，选取最优个体。首先经过计算得出个体的序值，然后选择序值相对较小的个体进行遗传传给下一代。两条个体的序值相同时，需要计算其拥挤距离，优先选择拥挤距离相对较大的个体进行遗传，以便保持种群个体基因的多样性。

2.4交叉

交叉方法采用单点交叉，在种群中随机选择两条染色体，通过前面染色体编码相同的思路，获取到前半部分的染色体，得知染色体长度是然后随机设定一处交叉点进行交叉。

2.5变异

2.6解码

解码方法采用方法是染色体全自动动解码方法，在染色体的前半部分基因中，在子目标中按照最大综合权重大小对应其工序排列，从而确定加工设备顺序。根据染色体上各基因的排列顺序，可以确定总体加工时间，并通过绘制甘特图将完成的车间调度结果显示出来。i和j，其数值在

3　实例应用与分析

为了证明算法的可行性，本文对10×10算例进行了分析。参数为：种群中个体数目m=500，种群进化代数T=500，种群代沟G=0.8，交叉概率Pc=0.85，变异概Pm=0.1.表1所示。

表1　发动机各零部件的工序可选择的加工设备列表

改进的算法比改进前的算法加工时间提前。实例测试结果如图1所示。

图1　传统遗传算法发动机零部件加工甘特图

图2　改进遗传算法发动机零部件加工甘特图

4　结束语

本文描述了离散车间多目标动态调度问题研究现状并运用遗传算法来求解此类问题。通过基于遗传算法的多目标优化算法实现了对离散车间多目标组合最优的选择。染色体编码采用基于工件加工工序和工件加工设备的两层编码方法，并通过实例分析，验证了本文算法的可行性，解决了离散车间多目标调度问题。

参考文献：

［1］曾强，沈玲，杨育，等.多目标等量分批柔性作业车间调度集成优化方法［J］.计算机工程与应用，2012，48（16）: 237-243.

［2］刘烽，游海，丁一钧，等.基于NSGA2算法的混合流水车间多目标调度问题研究［J］.人工智能及识别技术，2012，24（2）:86-87.

［3］谢皓，应保胜，袁波.基于遗传算法的路径柔性作业车间调度优化［J］.2012，12（2）:465-468.

［4］杨开兵，刘晓冰.流水车间成组工件调度问题的多目标优化算法［J］.计算机应用，2012，12（12）:3343-3346.

［5］王硕，顾幸生.基于改进蚁群算法的作业车间调度.青岛科技大学学报（自然科学版），2012，10（5）:489-494.

［6］曹岩，雷蕾，房亚东.蚁群算法在离散型车间派工中的应用.西安工业大学学报（社科版），2011，12（7）:611-615.

Research on Multi-objective Flexible Job Shop Scheduling based on the Improved Genetic Algorithm

PAN Ying，ZHOU Bai-cheng
（Machanical Engineering Institute，Dalian Ocean University，Dalian 116023，China）

Abstract：Through the study of the characteristics and the workshop production scheduling algorithms，and a mathematical model of discrete shop scheduling and dynamic multi-objective design improved genetic algorithm.In the shortest makespan，the total delay time and the minimum total equipment load the smallest of these three goals as the workshop production scheduling model optimization goal.Improved genetic algorithm to determine the optimal shop scheduling.Finally，an example analysis to verify the feasibility of the algorithm.

Key words：job shop scheduling；multi-objective；genetic algorithm

中图分类号：TH16

文献标识码：A

文章编号：1672-545X（2016）03-0266-02

收稿日期：2015-12-03

基金项目：大连海洋大学博士启动基金（SYBS2a01205）；国家科技支撑计划“大连市制造业信息化科技示范工程”（2013BAF02B03-2）

作者简介：潘颖（1977-），女，黑龙江双鸭山人，博士，讲师，研究方向为车间调度，精益生产。