徐嘉琦 田 野②

（①长春理工大学计算机学院，吉林 长春 130022；②长春理工大学人工智能学院，吉林 长春 130022）

柔性流水车间调度问题（flexible flow shop scheduling problem，FFSP）也称混合流水车间调度问题，是在传统车间调度问题的基础上加入了并行机的机制，更加符合如今的工厂车间生产的实际情况。随着智能化自动化的普遍应用与升级，目前柔性流水车间调度问题被广泛应用于机械[1]、化工、汽车生产、运输等各行各业。该问题已被证实为NP-Hard问题，解决此问题目前最常用的办法就是智能优化算法[2]，如粒子群算法、蜂群算法、遗传算法等[3]。随着问题规模的扩大，原始群智能算法出现计算慢、收敛过早、结果不好等问题[4]，因此对原算法的优化改进是必然的趋势。本文研究为经典的遗传算法在该问题上的应用。Bao T 等[5]针对遗传算法引入了基于有向变异的种群初始化，和基于免疫的物种选择对算法进行了优化。杨森等[6]提出了一种自适应遗传算法的改进方法，优化了交叉概率和变异概率的计算方式，并对该算法进行了验证。Shao W S等[7]提出了基于多邻域局部搜索的多目标进化算法求解多目标分布式混合流水车间调度问题。

经过众多的文献查询[8]，柔性流水车间问题在实际生产应用中的最优化目标有机器闲置时间最少，完工最快。问题的编码以及解码方式也是影响结果的重要原因之一。基于此，本文提出了一种改进遗传算法求解柔性流水车间调度问题，以完工时间最小化为目标，设计了针对该问题的编码与解码，算法针对该编码在复制、遗传、变异上进行相应优化，并引入了多种策略以提高算法的性能，在高收敛速度下，避免陷入局部最优无法更新最优解，最后通过多种对比试验验证算法的有效性。

1 柔性流水车间调度问题

1.1 问题概述

柔性流水车间问题即：工厂生产n个产品，每个产品的工艺路径是相同的，都需要m道工序，不同产品在同一道工序上加工时间不同，并且存在并行机，即m道工序中有一道或多道工序的机器数量为两台或多台，这些机器的性能是相同的，如图1 所示。

图1 柔性流水车间调度

有关参数定义如下：j为作业的索引，j=1,2,···,n；j′为j的上一个作业；i=1,2,···,m为工序索引；hi表示工序i可操作的机器有h个，hi=1,2,···,ki，其中ki为工序i中可用来加工的机器数量；Gi表示工序i中可用来加工的机器合集；Cij表示工序i中开工顺序为j的作业完成时间；Pij表示作业i的第j道工序的需要工作的时间；Mhi表示机器集合Gi里的第h个机器；Z表示工作的完成时间。

有关决策变量的定义如下：

1.2 柔性流水车间问题的数学模型

式（1）为目标函数最小完工时间Z的最小值；式（2）在一道工序中任何作业只可以有一个紧前作业；式（3）为所有的作业在同一工序的每个机器上只能成为一个作业的紧前作业；式（4）为任意作业的排产无论是否出现在某机器上，它的紧前、紧后作业变量一定相等；式（5）是同一个机器的同一个位置上的作业不存在紧前或紧后的关系；式（6）是对完工时间的约束，两个作业在同一台机器上有紧前关系，该定义才有效，在不同机器上完工时间无规定，或者同一机器无紧前紧后关系可用此约束，M为一个极大值；式（7）为同一作业前一道工序完成时间加当前工序的作业时间不能大于当前工序完成时间；式（8）为各作业的准备时间为0。

2 改进遗传算法

2.1 算法流程

针对柔性流水车间的改进遗传算法，输入具体的问题，包括作业数、工序数和每个作业的每道工序所需时间的矩阵，以及每道工序对应的可用机器数量；输出为最优的工件安排表，包括最小完成时间以及Gantt 图。算法在遗传算法基础上针对柔性流水车间问题进行了改进，由于该问题解的离散性对多处进行了优化与添加，流程图如图2 所示。

图2 MGTA 算法流程图

2.2 编码与解码

染色体的编码是遗传算法的第一步，后续的一切操作都围绕着编码进行操作。本文采取一维的编码形式，由于自动选择机器，而完工时间仅由每道工序的作业加工顺序决定。与传统一维编码相比，传统编码为从1 到(n×m)的乱序，这里将一个个体的编码在内部分为m份，则每份的排列为从(n－1)×m+1 到(n×m)，此处n的取值范围为[1,n]。如有一作业数为4、工序数为3 的初始问题，则个体的编码如图3 所示。

图3 染色体编码

该编码在一定程度可以避免种群的重复，也可以减少后期的计算量。解码为编码的逆操作，本文使用解码方式为针对最早结束时间的启发式解码规则。按顺序排产，当前操作数为a，工序数为proc,作业数为job，当前操作数的工序为(a-1)与job取商后加1，当前操作数的作业数为(a-1)与job取余后加1，并安排机器。分配前进行机器空闲时间检查，在可排产的可用机器中再次搜索是否有两个工作间隔的空闲时间、是否可以塞入当前任务，若没有再安排到当前工序可用机器里可开工时间最小的机器上，优先完成先分配的方案。

2.3 种群初始化

由于随机生成的初始种群存在不确定性，有可能生成种群聚集，本文采用对立方法进行初始化操作，先随机生成一半的初始种群。由于该问题属于离散型，对立方式为将生成的一半种群全部进行逆序排列，即将每道工序全部进行逆序，如一作业数为4、工序数为3 的问题随机生成的个体和对立后个体如图4 所示，避免了初始种群聚集，可生成更优解提升算法效率。

图4 对立方法

2.4 交叉操作

传统遗传算法多为单点或多点交叉，即交换两个或多个点生成全新的DNA 个体。由于本文的离散型编码，单点或多点交叉后会出现缺失或重复，需重新验证个体完整性，导致计算时间增加，并破坏原有基因格式。为保留原有基因编码格式的同时交叉产生新个体，这里采用片段交叉，将两个个体的某一工序整体进行交叉变换，这样可以在生成新个体的同时更直观地保留父代的优秀基因。如有两个DNA 个体，则交叉方式如图5 所示。

图5 交叉操作

2.5 优化变异操作

变异操作是扩大搜索范围找到更优解的关键步骤。首先由概率判断该个体是否需要进行变异，为了变异程度更大跳出局部最优，针对该文的编码方式设计如下变异：个体的每道工序都进行变异，每道工序中随机选取两个作业数进行交换，如图6 所示。

图6 优化变异操作

这样针对n个作业、m道工序的个体，每经过一次变异就有2m处发生了变异，增大变异的程度并且保证了编码的格式。

2.6 多目标选择

选择操作的目的是使种群向最优个体靠拢，并将最优个体遗传到下一代，在一定程度上在最优个体附近更新寻找最优解。为了降低种群陷入局部最优的情况，根据离散型的问题设计了多目标选择，即选出b个较优个体，使其他个体向这些个体靠拢。按照次序使除较优个体分别进行选择操作，每次选择操作前都随机获取个体的一个片段，使该片段直接被其目标较优个体的相同位置的片段替换。再从头检查个体去除重复部分，补上缺失部分。在较优个体上随机选取片段如图7 所示，非较优个体靠拢方式如图8 所示。

图7 片段选取

图8 靠拢方式

多目标选择增大了算法的搜索程度，给出了更多疑似最优的选择，并且未增加时间复杂度的量级，在不影响收敛速度的同时，增大了搜索范围。

2.7 交叉概率变异概率更替

交叉和变异操作作为遗传算法中的两个重要步骤，交叉和变异的概率更加决定了算法的效率。本文设计了两套交叉概率和变异概率，用来针对不同的情况。初始情况为高交叉概率、低变异概率，并记录迭代过程中最优解更新情况，若g次迭代仍未出现最优解的改变则调整为低交叉概率、高变异概率，再次出现最优解更新后恢复高交叉概率、低变异概率。这样使整体算法更加灵活，能更好地跳出陷入局部最优解的情况。

3 仿真试验及结果分析

3.1 参数设置和对比试验

MTGA 在求解柔性流水车间调度中的主要参数包括种群大小（pop）、最大迭代次数（G）、较优个体数（b）、高交叉概率（c1）、低交叉概率（c2）、低变异概率（m1）、高变异概率（m2）、最优解未更新代数（g）。由于多目标选择的因素种群大小在较大时可以更好地发挥意义，因此种群大小设置为200。针对交叉以及变异概率的设置，交叉概率过大会导致种群归一化，过小则没有保留优秀基因的效果；变异概率过大会导致种群倾向于随机无规律搜索，过小则无法跳出局部最优解。经过多次试验结果统计，高交叉概率为0.7，低交叉概率为0.3，高变异概率为0.5，低变异概率为0.2，g为pop/4，b为5，最大迭代次数分别设置为100和200。为验证本文改进算法（MTGA）的性能，将算法与改进遗传算法（NSAGA）[9]、改进贪婪遗传算法（GGA）[10]、混沌自适应粒子群优化算法（CAPSO）[11]、基于Lévy 飞行和差分进化的混合鲸鱼优化算法（WOA-LFDE）[12]进行对比。以上对比算法都是近期发布的可应用于FFSP 的优秀算法。对比算法参数均按照原论文给出的最优参数进行设置。试验均采用Matlab R2016a 编写，在Intel Core i5-10200H、2.40GHz CPU、16GB RAM、Windows 10 环境下进行测试。

3.2 寻优效果测试

首先对几种算法的寻优能力进行测试，算例为中等规模，10 个作业均有9 个工序，每道工序配备的机器数量为[2 3 2 1 2 4 6 2 4]，每个工件的每道工序加工时间通过随机生成取值范围为(0,180)，具体见表1，通过暴力搜索算法得出最优解为919。5 种算法在迭代次数为200、求解10 次求得的最优解见表2。

表1 工作时间

表2 运算结果

由表2 可知，除WOA-LFDE 算法外，4 种算法在10 次实验中均成功得出过最优解。为了便于对比，在此引入每次实验的最优解与已知最优解的平均相对偏离度（average relative percentage deviation，ARPD）[13]，定义如下：

式中：L表示算法的实验次数，soli表示算法。

在第i次实验求得的最优解，BKS 为问题已知最优解。ARPD 能够有效地表示算法求的解与最优解之间的相对偏离程度以及算法的寻优能力。表3为算法10 次求解上述算例后求得的ARPD。

表3 算法的ARPD

由表3 可知，MTGA 算法可以求得在最优解附近误差较小的结果，其ARPD 的值也是最小的；NSAGA 与CAPSO 算法虽然也求出了最优解，但是存在某次结果距最优解偏离较大，因此导致ARPD较大；WOA-LFDE 算法虽然未求得最优解，但其运算结果较为集中，离散程度很小，并且与最优解相差不大；GGA 算法虽然表现结果与MTGA 相差不大，但由于其贪婪选择的原因导致运算量与运算时间也相对较大，因此在寻优能力方面MTGA 有着较好的效果。

3.3 大规模基准算例测试

为进一步验证MTGA 的各方面性能，本文参考Carlier I 和 Néron E[14]所提的12 种算例进行测试，如10-5-1 表示有10 个作业，每个作业有5 道工序，1 是每道工序机器数的索引。索引对应机器数见表4。

表4 机器数量类型汇总

针对每个算例进行20 次测试，种群大小为200，迭代次数为100，分别记录20 次实验中的最优解（Cmin）、平均解（Cave）和标准差（Std），结果见表5。针对大型算例的收敛曲线如图9～图12 所示，算例10-5-1 的甘特图如图13 所示。

表5 大规模实验结果

图9 算例20-10-6 收敛曲线

图10 算例20-10-5 收敛曲线

图11 算例20-10-4 收敛曲线

图12 算例15-10-4 收敛曲线

图13 算例10-5-1 甘特图

4 结果分析

由实验结果可以明显看出，针对机器数量瓶颈阶段在开头的实验（机器索引为2 和5），5 种算法寻优能力相差不大，所求的最优解相近，在问题规模不大的情况下离散程度也很好，算法都十分稳定。在20-10-5 的实验中，NSAGA、WOA-LFDE、GGA 标准差较大，算法稳定性较差。针对瓶颈阶段在中间的实验（机器索引为1、3、4、6）MTGA算法的寻优能力明显优于其对比算法，在小规模算例中差距不大，但随着问题规模的扩大，MTGA 的最优解与其他算法差距也变大，并且除20-10-6 算例稳定性不输于其对比试验。20-10-6 算例标准差明显变大的原因是MTGA 在实验中搜索到十分优秀的解导致标准差的扩大，也能侧面说明其寻优能力，以及可以有效跳出局部最优解的优点。在表5中还可以发现，GGA 算法在部分大规模实验中表现与MTGA 相近，但由于其贪婪搜索的原因导致其运行时间大幅度增加，效果也未超越MTGA，因此验证了MTGA 算法在寻优能力上的有效性和优越性。针对收敛曲线，由于小规模算例各算法差距不大，因此选择4 个典型的大规模算例进行收敛曲线对比。由图9 针对机器数瓶颈期在开头的算例中，各种算法的精度和收敛速度相差不大，其中MTGA和GGA 精度相对较高。由图10～图12 可知，MTGA算法在机器数瓶颈期在中间的大规模算例中精度远远高于其他算法，收敛速度在图11 和图12 中不低于其他对比算法。图9 中收敛速度在迭代前期不是最佳，但能够及时跳出局部最优解获得更优秀的解。

5 结语

本文研究了改进的遗传算法应用于柔性流水车间调度问题，介绍了柔性流水车间问题，设计了针对该问题的编码与解码方案，用对立方法生成初始种群，设计了两套交叉变异概率灵活交替应用，针对编码方式更新了交叉与变异，采用了多目标选择，使收敛方向多个最优解靠拢，降低陷入局部最优的概率。通过实验对比NSAGA、CAPSO、WOA-LFDE和GGA 这4 种优秀的改进算法验证了MTGA 的精度与稳定性，又通过12 个算例，包括机器瓶颈期在开头和中间的情况，验证了MTGA 算法在不同规模，不同类型的算例中收敛性和精度表现得出算法的精度是在对比实验中最高的，且有较好的收敛性，证明了算法的有效性和优越性。未来的工作将从算法的收敛速度入手，为明显加快算法收敛速度使其明显优于其他算法进行研究。