基于遗传算法的多目标车间调度*

靳彬锋，毕 利

(宁夏大学 信息工程学院，银川 750021)

0 引言

车间调度问题是现代制造企业自身生存和发展的基础[1]。调度任务中的单目标与多目标问题，以及如何合理有效的使用调度方法，求出满足生产目标的优化结果，许多学者进行了研究并取得了丰富的成果[2]。由于多目标的生产安排更符合制造业的需求，尤其是柔性作业车间调度更贴近实际调度情况，受到了学者的广泛关注[3]。

文献[4]提出了一种针对柔性车间调度问题(FJSP)两阶段节能的优化方法。在第一阶段机器选择方面应用了改进的遗传算法(MGA)，在第二阶段工序选择方面采用了将遗传算法(GA)与粒子群优化(PSO)相结合的混合方法。文献[5]提出一种结合Cauchy分布的粒子群算法和遗传算子(HPSO+GA)相结合的混合方法，找到了FJSP问题中能使makespan最小化的工作序列。文献[6]提出了一种混合遗传算法(HGA)，用于解决分布式的柔性作业车间调度问题(DFJSP)，应用了一种新的编码机制来解决无效的作业分配问题。文献[7]提出了一种基于可变区间重调度策略(VIRS)的动态重新调度方法，以处理动态柔性作业车间调度中的机器故障、紧急工作到达和工件损伤等问题。另一方面，提出了一种改进的遗传算法(GA)，以求得makespan的最小化。文献[8]在遗传算法中加入再激活(reactivation)机制，避免了传统GA 算法在求解 FJSP 时陷入局部最优的情况，增加了种群的多样性。

本文针对遗传算法在柔性作业车间调度中存在的早熟和搜索性能较差的现象，除了对基本遗传算法做了改进以外，还结合模拟退火算法，应用模拟退火算法跳出局部最优的能力，给出了一种新的混合遗传算法(HGSA)，用以实现在柔性车间调度的寻优处理。

1 数学模型

对柔性作业车间调度的问题进行描述：由n个工件Ji组成的工件集J={Ji，1≤Ji≤n}，由m台机器Mi组成的机器集M={Mi，1≤Mi≤m}，同时每个工件Ji有nj道工序，Oij表示工件Ji的第j道工序，工序Oij可以选择的加工机器集为W，并且在加工过程中，必须满足以下约束条件：

(1)某一时刻同一台机器上只能加工一个工件；

(2)正在加工的工件不能被中断；

(3)同一工件中的工序之间具有先后约束，不同工件中的工序没有加工顺序的约束；

(4)某一时刻一个工件只能被加工一次。

柔性作业车间调度的主要任务就是将待加工的n个工件所包含的全部工序Oij选择相应机器进行加工，完成所设定的目标，并且对所求目标进行优化。

(1)最小化最大完工时间：全部待加工工件完成的最后时间，表示为F1，如式(1)所示：

F1= min{max{maxcj}}

(1)

其中，Cj表示工件Jj的完工时间。

(2)最小化加工成本：工件在机器上加工时所耗费的成本Cv与机器处于就绪状态所消耗的成本Cs之和，表示为F2，如式(2)所示：

(2)

FDk>0且FD0=0

(3)

FSk>0且FS0=0

(4)

tijk≥0且ti0k=0

(5)

其中，tijk表示工件Ji的第j道工序在加工机器Mk(Mk∈W)上的加工时间。Xijk表示为决策变量，即工件Ji的第j道工序是否选择在机器Mk上进行加工，Xijk=1表示机器Mk被选中，Oij在机器Mk上进行加工；Xijk=0表示机器Mk没有被选中。T*表示最优调度方案的最大完工时间。FDK表示第K台机器的动态耗费率；FSk表示第K台机器的静态耗费率。

(3)机器最大负荷：单台机器设备最大的使用负荷，表示为F3，如式(6)所示：

(6)

(4)机器总负荷：工件加工时所有机器设备的使用负荷，表示为F4，如式(7)所示：

(7)

(5)约束条件：

(8)

Stijk>0且Sti0k=0

(9)

2 HGSA算法

2.1 编码

针对FJSP的特点，采用基于工序-机器的双层实数编码方式，如表1所示。在关于车间调度问题的编码方式中，将加工工序还有机器作为调度编码来实现，这样得到的编码都是合法、有效的。采用实数型权值编码，解决了传统的整数型编码造成的搜索空间被制约的影响，并且有利于算法加入实数型遗传算子，从而提高算法的收敛[9]。

表1 编码操作

在表1中，基因的整数部分表示的是工件Ji。小数部分指的是由轮盘赌决定的该工件选择机器的可能性，比如工件J4的工序O41，可选机器有6个：M1，M2，M3，M4，M5，M6，每个机器被选择的概率都是1/6，O41的小数部分是0.21，则选择概率为[16.6,0.33)，选择机器为M2。

2.2 初始化参数

由于解空间个数远大于初始种群的个数，对于初始种群的产生，通过合适的方式可以保持种群的多样性[10]。而传统的随机方式可能因为随机解集中在某一区域致使算法搜索与收敛不能在全局范围内较好的展开。本文以距离为依据的方法来产生均匀的初始种群，其流程图见图1，步骤描述如下：

(1)选择初始个体X1，X2，X3，…，Xn，选取任意Xi(1≤i≤n)作为第一个种群中心Y1，即Xi=Y1；

(2)选取距离Xi最远的个体Xj为第二个种群中心Y2，则Xj=Y2，计算Y1与Y2的海明距离(Hamming distance)H12；

(3)依次计算个体X1，X2，X3，…，Xn与种群中心Y1、Y2的海明距离Hp1、Hp2，若有min{max(Hp1，Hp2)，p=1，2，…，n} < 0.5H12，则令Xp=Y3，转到(4)，否则转到(6)；

(4)计算Hp1、Hp2、Hp3，若有min{max(Hp1，Hp2，Hp3)，p=1，2，…，n} < 0.5H12，则令Xp=Y4，转到(5)，否则转到(6)；

(5)计算Hp1、Hp2、Hp3，Hp4，若有min{max(Hp1，Hp2，Hp3，Hp4)，p=1，2，…，n} < 0.5H12，则令Xp=Y1，形成新的种群中心，转到(1)，否则转到(6)；

(6)根据海明距离把全部个体分配到距离其最远的种群中。

图1 种群初始化流程图

2.3 适应度计算

在FJSP多目标生产中，适应度函数要综合考虑不同的目标值，因此设计了一种带权值的多目标适应度函数，如式(10)所示：

F=1/(ω1·θ1·F1+ω2·θ2·F2+ω3·θ3·F3+ω4·θ4·F4)

(10)

其中，ω1+ω2+ω3+ω4=1，根据实际调度情况选择不同的权值。θ值表示将数据集经过归一化处理后，将目标函数值转化成了相同的数量级。

2.4 选择操作

采用轮盘赌的选择方式[11]。首先对选择出的个体根据适应度函数进行适应度值的计算，然后按照适应度值对应的选择概率进行随机选取，直到选出满足设定数量的个体数。

2.5 交叉操作

交叉操作主要是通过父代染色体的交叉互换而得到新的个体[12]。根据编码方式，采用适用于浮点型的拉普拉斯交叉算子。拉普拉斯交叉算子，从父代的拉普拉斯分布得到密度函数系数，在算术交叉中加入拉普拉斯分布的两个系数，这样来达到控制子代破坏父代优良个体的概率，同时由于算术交叉的使用扩大搜索空间。假设在第s代的两个个体Xs1与Xs2进行交叉，则其第s+1代中的个体Xs1′与Xs2′为：

(11)

(12)

其中，β为：

(13)

式(13)中的μ、b为拉普拉斯的分布参数，μ∈R是位置参数，b>0是尺度参数。μ、b的值可由父代的函数分布逆推得到。μ的作用是决定与父代种群个体的距离，在此基础上，b越大表示离父代个体越远，b越小表示越靠近父代。a∈[0，1]表示一个分布均匀的随机数。在μ、b的共同作用下，父代个体之间的距离影响其子代之间的距离，即子代是对父代成正比例的延长。

2.6 变异操作

逆转变异是一种特别的变异算子。它通常是在个体的染色体编码上随机选择两个点，即逆转点，接着将这两个点的基因根据逆转概率ρ逆向排序。二进制编码的逆转概率例子如下：

父代染色体:1 0 0 1 0 1 1 0 1 0 0

假设3和8是两个逆转点，则

子代染色体:1 0 0 1 1 0 1 0 1 0 0

从上面可以看出，子代染色体经过逆转变异操作以后，逆转点3和逆转点8之间的基因序列被逆向排序，即从0 1 0 1 1 0序列，变成了0 1 1 0 1 0序列。

2.7 模拟退火算法

在用遗传算法求解问题的过程中，收敛速度在后期会变慢下来，这是因为它有突出的全局搜索能力，同时局部搜索能力较弱。为了解决这一问题，让新的混合算法具有很好的全局搜索和局部搜索能力在遗传算法中引入模拟退火算法。模拟退火算法因为其杰出的摆脱局部极值能力而受欢迎，其步骤如下所示：

(1)初始化参数：初始温度Tmax，初始解S，每个温度值T的迭代次数L；

(2)fork=1:L；

①扰动产生新解S′；

②Metropolis准则。计算增量△T=C(S′)-C(S)，C(S)为评价函数；

③若△T< 0，S′成为新的当前解，否则以概率exp(-△T/T)接受S′作为当前解；

④若满足终止条件，输出当前解作为最优解，算法结束；

(3)温度T逐渐减少，且T≥ 0，转到第(2)步。

因为局部搜索比较耗时，为了顺利地找到最优解，在模拟退火算法中加入了基于逆序的局部搜索方法，具体流程图见图2。其基本思想是：在遗传算法中，每一代个体经过选择、交叉和变异等遗传操作之后，都需要对当前最优个体进行局部搜索。基于逆序的局部搜索方法如下：

(1)在当前解中随机选择编码的两个不同位置c、d(c

(2)对新个体进行解码，并计算其适应度值，如果优于逆序前的个体则替换，否则继续保留；

(3)返回(1)。

图2 基于逆序的SA流程图

3 仿真分析

3.1 运行环境

在Intel(R) Core(TM) i5-3337U、CPU主频 1. 80 GHz、4.00GB 内存、Windows8.1操作系统下, 利用 Matlab R2014b编程实现上述算法。

3.2 实例仿真

对某航空发动机公司生产车间一个生产线上的实际数据经过取整处理后，得到 6 个工件和6 台机器，每个工件有 10 道工序的 FJSP 问题, 进行了仿真实验。

HGSA算法初始参数设置如下：遗传算法的种群规模为100，最大迭代次数为300，交叉概率为0.9，变异概率为0.1，适应度函数权值根据工厂调研设置为ω1=0.6，ω2=0.2，ω3=ω4=0.1。模拟退火算法的初始温度是100，冷却系数是0.99。用改进的混合算法得到的近似Pareto解集如表2所示，调度人员可以根据情况选一组解进行加工安排。另外由于所得甘特图较多，这里只展示第一个Pareto解对应的甘特图如图3所示，图4为其对应的收敛图。

表2 所得Pareto近似解集

图3 序号 1Pareto解对应的甘特图

图4 序号1Pareto解对应的收敛图

为了验证本算法的性能，与其他算法进行对比分析。运行20次取平均值。它们的比较结果如表3所示。

表3 不同算法的结果比较

从表3可以看出，HGSA算法各项值均比传统的混合算法、遗传算法的结果要好，完工时间分别缩小了54.7%、61.6%，加工成本分别节省了36.1%、34.8%，最大机器负荷分别降低了62.2%、69.5%，机器总负荷分别降低了9.7%、10.2%。另外，单一的模拟退火算法应用于柔性作业车间调度时，其算法本身的特性，使得算法的时间复杂度特别大，与HGSA算法相比不具有优势。

4 结束语

多目标柔性作业车间调度是离散制造业中的重要一环，它比JSP更加贴近实际生产，文本提出了HGSA算法来求解这一问题。首先是用距离来得出均匀的初始化种群，然后是轮盘赌的方式进行选择，随后经行了拉普拉斯交叉和逆转变异操作，接着是模拟退火的局部寻优，从而使本算法达到全局最优。仿真实例证明，本算法有较好的全局搜索能力，能得出质量较高的Pareto解，对实际的生产调度问题具有一定的借鉴意义。