工时不确定条件下基于改进遗传算法的柔性作业车间调度问题的区间数求解方法

陈宇轩

(合肥工业大学机械工程学院，合肥 230009)

工时不确定条件下基于改进遗传算法的柔性作业车间调度问题的区间数求解方法

陈宇轩

(合肥工业大学机械工程学院，合肥 230009)

以不确定工序加工时间为切入点，使用区间数表征不确定工序加工时间，研究了基于不确定工时的单目标柔性作业车间调度问题，并设计了基于区间数理论的改进遗传算法对该问题进行求解。

不确定工序加工时间；区间数；改进遗传算法；柔性作业车间调度

0 引言

实际生产过程中，存在着大量的不确定因素，大多数不确定因素的随机波动都直接反映到工序加工时间的变化上[1]。然而以往文献为了简化问题难度常常假定工序具有确定的加工时间，这样做的后果是得出的调度方案严重偏离了实际生产情况[2-3]。因此，本文以不确定工序加工时间为切入点，研究不确定工时的车间调度问题。从目前国内外文献可以了解到，工序加工时间的描述方法基本可以分为三类：1）模糊数理论。以Zadeh提出模糊集理论[4]为核心，衍生出的一系列模糊方法，主要研究与处理问题的模糊性以及决策上的不确定性。2）随机数理论[5-6]。以大量实际数据为研究依据，归纳出研究对象服从的分布，并根据分布进行求解。3）区间数理论[7]。用区间数描述工序加工时间的分布区间，再根据区间数

的比较规则进行求解。随机数和模糊数都需要事先得知生产数据服从的分布。但在车间实际生产中，获得工序加工时间的分布受到统计等技术条件的影响相对比较困难，而工序加工时间往往都存在一个上限和下限，因此本文使用区间数理论表征不确定工时[8]。

1 区间数理论及问题模型

1.1 区间数理论概述

通常情况下人们对事物的判断往往不会是一个定量的值，而是一个在特定范围内的变量。这种在特定范围内的变量，我们称之为区间数。区间数的数学定义如下：

定义1.1：设R为实数域，［a］=［a-,a+］，称a为区间数。

区间数之间的比较规则比较特殊[8]：设［a］、［b］为两个区间数，则有：

1.2 问题模型

该问题数学模型可以表示为：

下面对上述约束条件进行介绍：Cj表示工件j的加工完成时间，Sij,k表示工件Ji的第j道工序在第k台设备上的开始加工时间；Pijk表示工件Ji的第j道工序在第k台设备上的加工时间；ni表示工件Ji的工序数，Q表示无穷大的整数，xijk表示工件决策变量，可以从{0,1}中取值，表示工件Ji的第j道工序是否在加工机器Mk上加工；yihk表示机器决策变量，可以从{0,1}中取值，表示同一个机器上不同工序的先后加工顺序；式（3）表示同一工件的工序之间存在顺序约束；式（5）和式（6）表示机器只能同时加工一个工件。值得一提的是本文涉及工序加工时间的内容，均使用区间数进行表征。

2 算法设计

本文针对柔性作业车间调度问题设计了改进遗传算法进行计算[9]：使用双层编码及解码方式进行操作，并设计了随机初始化种群方法和基于区间数的选优方法相结合的初始种群方法，同时设计了基于区间数的最佳个体保存法的选择方法，并采用了基于POX[10]方法和多点交叉法[11]的交叉操作以及平移变异[12]和两点变异[13]的编译方法。

2.1 编码与解码

根据柔性作业车间调度问题的特性，本文按照工序码和机器码的双层编码和解码方式进行介绍[14]。

1）工序码。包含多个基因，基因中的数字代表工件号，该数字出现的次数表示工序号。也就是说第j次出现的工件序号i表示工件Ji的第j道工序，即Oij。

2）机器码。包含若干片段，片段按照工件序号排序，同时每个片段又包含多个基因，基因中的数字表示该道工序分配到那一台机器，如在某个机器码中，第3个片段的第2个基因中数字为4，表示工件J3的Q32在加工机器M4上加工。

2.2 改进初始种群方法

我们提出随机初始化种群方法和基于区间数的选择方法综合判定。具体思路如下：1）为种群中的所有个体随机产生的0～1之间随机值；2）若随机数大于0.8，则个体采用随机方式生成，反之，则个体采用基于区间数的选择方法生成。基于区间数的选择方法的核心思想是按照工件完工时间最短的原则选择加工机器。具体来说是将所有工件的全部工序的加工时间根据式（1）区间数比较规则进行排序，用时最少的优先配置机器，循环上述过程直到全部工序分配到机器。

2.3 改进选择操作

本文采用基于区间数最佳个体保存选择的方法进行选择操作。对于基于区间数最佳个体保存法其过程为：1）使用区间可能度的比较规则将工序时间进行排序，将用时最短的父代种群中的个体直接复制到下一代中。2）当一个选择完成后，将被选择的个体重新放回种群。并且被选择的个体仍可作为一个父染色体继续参与选择。使用该方法的主要目的是该方法可以使得选择出的所有个体不会被交叉和变异操作破坏，从而可以提高实例模拟收敛可靠性。

2.4 基于POX法多点交叉法的交叉操作

本文针对工序码采用POX交叉[10]算子，针对机器码采用多点交叉[11]的方法。

2.5 基于平移变异和两点变异的变异操作

本文针对工时不确定条件下的柔性作业车间调度问题中工序排序和设备分配的不同需求，对工序编码采用平移变异[12]；对机器分配编码采用两点变异[13]方法。

2.6 算法流程

步骤1：首先设置算法相关参数，具体包括种群规模、算法最大迭代代数、交叉概率、变异概率等[15]。步骤2：采用随机方法和基于区间数的选择方法相结合的初始种群方法产生N个个体组成一个初始种群，并令其规模为P。步骤3：使用POX交叉对父代种群进行操作，其中当t=0时，Pt表示初始种群。步骤4：对个体进行适应度评价。步骤5：采用基于区间数的最佳个体保存法进行选择操作。步骤6：工序码和机器码分别使用平移变异和两点变异，产生子代种群Ct。步骤7：产生下一代种群并返回到步骤4。

3 实例验证

本文以3×5FJSP问题作为样本，数据如表1，并设计了原型系统根据上文设计的改进遗传算法进行计算。

表1 原始数据

图1为原型系统主界面，对于单目标问题进行目标选择，针对本文研究内容勾选最大完工时间最小，然后点击【问题导入】插入计算基础数据，然后点击【参数设置】。

图2为参数设置界面，选择种群规模、变异概率、交叉概率、选择概率和最大进化代数。

最后点击计算，这里我们进行10次运算求得最优解，具体数据如表2所示。

4 结语

图1 原型系统主界面

图2 参数设置

文中针对不确定工序加工时间的柔性作业车间调度问题，使用区间数理论对传统遗传算法进行改造。首先使用双层编码及解码方式进行编码和解码操作，并设计了随机初始化种群方法和基于区间数的选优方法相结合的初始种群方法，同时设计了基于区间数的最佳个体保存法的选择方法，并采用了基于POX方法和多点交叉法的交叉操作以及平移变异和两点变异的编译方法。最后开发了调度模型系统，计算求得了调度问题最优解。

图3 计算结果

表2 运行结果

[1] 王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.

[2] 何霆,刘飞,马玉林.车间生产调度问题研究[J].机械工程学报,2000,36(5):97-102.

[3] 李怀祖.生产计划与控制[M].北京:中国科技出版社,2010.

[4] ZADEH L A.Fuzzy Sets[J].Information and Control,1965,8(3):338-353.

[5] 彭建刚,刘明周,张玺,等.工序加工时间不确定的柔性制造车间重调度算法[J].中国机械工程,2014,25(17):2320-2326.

[6] 贾春福.加工时间服从指数分布单机随机调度[J].系统工程,2002,20(6):58-61.

[7] SAKAWA M,Mori T.An efficient genetic algorithm for jobshop scheduling problems with fuzzy processing time and fuzzy duedate[J].Computers&Industrial Engineering,1999,36(2):325-341.

[8] 杨宏安,王周锋,吕阳阳,等.工序加工时间不确定条件下作业车间调度问题的区间数求解方法[J].计算机集成制造系统,2014,20(9):2231-2240.

[9] 袁波,应保胜,谢皓.基于遗传算法的不确定条件下作业车间调度[J].现代制造工程,2012(10):52-56.

[10]张超勇,饶运清,李培根.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004,15(23):2149-2153.

[11]张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124.

[12]葛继科,邱玉辉,吴春明,等.遗传算法研究综述[J].计算机应用研究,2008,25(10):2911-2916.

[13]席裕庚,柴天佑,恽为民.遗传算法综述[J].控制理论与应用,1996(6):697-708.

[14]刘壮.基于改进遗传算法的柔性作业车间调度[J].机械工程师,2016(10):43-45.

[15]刘捷.不确定条件下基于遗传算法的柔性作业车间调度问题研究[D].武汉:华中科技大学,2009.

Solution about the Interval Number of Flexible Job Shop Scheduling Problem Based on Improved Genetic Algorithm under Uncertain Time

CHEN Yuxuan
(School ofMechanical Engineering,Hefei UniversityofTechnology,Hefei 230009,China)

In this paper,the processing time of indefinite process is characterized by interval number,and the singleobjective flexible job-shop scheduling problem based on uncertain processing time is studied.The improved genetic algorithm based on interval number theory is designed.The problem is solved.

uncertain process processing time;interval number;improved genetic algorithm;flexible job shop scheduling

TH 186

A

1002－2333（2018）01－0074－03

（编辑黄 荻）

陈宇轩(1992—)，男，硕士研究生，主要从事制造过程监测与控制研究。

2017-04-01