指针网络与遗传算法求解置换流水车间调度问题

蔡国帅，金 淳，华顺刚

（1.大连理工大学机械工程学院，辽宁大连 116024；2.大连理工大学经济管理学院，辽宁大连 116024）

0 引言

置换流水车间调度问题（Permutation Flow-shop Scheduling problem，PFSP）作为典型的生产调度问题，是许多实际生产调度问题的简化模型，在运输、物流、车间生产等领域有着大量的应用[1]，已被证明3台机器以上的PFSP问题属于NP-Hard难题[2]。因此，研究该问题的优化算法具有重要的理论意义和工程价值。

求解PFSP的方法主要分为3类，精确算法、启发式算法和智能优化算法。精确算法主要有分支定界法、整数规划和动态规划等方法，由于其计算复杂度大，仅用于求解小规模问题。启发式算法有CDS（Campbell Dudek Smith）算法、Palmer算法以及NEH（Nawaz Enscore Ham）算法，启发式算法具有求解速度快的优势，但是其求得的解的质量较差。由于精确算法和启发式算法存在不足，目前对PFSP的研究多集中于智能优化算法。常用的智能优化算法有粒子群优化算法、遗传算法、蚁群算法和差分进化算法等。尽管许多智能优化算法在PFSP上取得了不错的效果，但是其迭代过程通常比较耗时，因此很多文献中利用不同的算法生成群智能优化算法的初始种群，以提高初始种群的质量，提升算法的性能。如Zhang等[3]将NEH算法与遗传算法结合，并融合模拟退火算法，以提升算法性能。秦旋等[4]将NEH算法和共生生物搜索算法相结合，设计了一种混合生物共生算法，并获得了良好的性能。王凌等[5]利用训练好的指针网络输出初始解，设计一种带反馈机制的迭代贪婪算法。

由此可见，种群初始化是群智能优化算法的第一个阶段，也是影响算法性能的一个重要因素。而深度强化学习技术求解组合优化问题具有求解速度快、泛化能力强的优点，并且可以利用训练好的网络直接输出问题的解。因此适合用来对群智能优化算法的初始种群进行初始化，以提高初始种群质量，提升算法性能。近年来，在组合优化领域出现了多个深度强化学习的新方法[6]，如指针网络、图神经网络。Vinyals等[7]提出了一种名为指针网络的神经架构来学习输出序列的条件概率，并用于求解旅行商问题。Bello等[8]提出了一个使用神经网络和强化学习来解决组合优化问题的框架，在100个城市规模旅行商问题上接近最优解。

因此本文将指针网络和遗传算法相结合，利用指针网络来生成PFSP问题的初始序列，并用于遗传算法初始种群的构造，然后利用结合重启机制和局部搜索技术的遗传算法来获得最终的解。通过仿真实验测试Reeves标准数据集，验证了算法的有效性。

1 置换流水车间调度问题描述

PFSP问题通常描述为n个工件J={1,…,n}在m台机器M={1,…,m}上加工，每个工件在各机器上加工顺序相同而且每台机器加工的各工件顺序也相同，给定工件i(i∈J)在机器j(j∈M)上的处理时间pij，目标是求得一个工件加工顺序使得某个调度目标达到最优，常用的调度目标是最大完工时间Cmax。

PFSP问题的假设如下：（1）所有工件在零时刻均可加工；（2）工件在不同机器间的运输时间和设置时间包含在处理时间中；（3）每台机器在同一时刻只能处理一个工件；（4）不允许作业抢占，即在每台机器上工件一旦开始加工则不能中断；（5）机器之间的缓冲区容量无限大。

令π=(π1,…,πn)代表所有工件一个加工序列，其中πi∈J。Cπi,j和pπi,j分别表示工件πi在机器j上的完成时间和加工时间。最大完工时间Cmax的计算过程如下：

置换流水车间调度的目标是求得一个最优工件加工顺序π=(π1,…,πn)，使得Cmax最小。

2 指针网络与遗传算法求解流程

指针网络改进遗传算法框架如图1所示。

图1 PN-HGA算法框架

2.1 指针网络与参数优化

2.1.1 数据预处理

传统的指针网络是用来求解TSP问题，编码网络的输入为二维向量，而PFSP问题的输入维度则是机器的数量m，因问题不同而不同，这导致指针网络不能直接应用于PFSP问题。

因此本文对PFSP问题的数据进行预处理，考虑到标准算例（Carlier、Reeves、Taillard）的最大机器数为20，因此可以在算例数据后面增加（20-m）个所有工件加工时间都为0的机器，其最终的最大完工时间和原算例相同，并不会影响调度结果。因此对于一个n个工件，m(m≤20)个机器的调度问题，经过预处理操作后转化为一个n个工件，20个机器的调度问题。因此对于不同的调度问题，其机器维度固定为20，然后可以通过指针网络进行求解。

2.1.2 编码与解码

指针网络包括两个循环神经网络（RNN）模块，编码网络和解码网络，如图2所示。

图2 指针网络结构

这两个模块都由长短期记忆（LSTM）网络组成。编码网络读取实例是由工件i在每台机器上的处理时间组成的向量。每次读取一个工件，并将其转化为一系列的隐藏状态。在第i步时：

式中：Whp、Whh、h0为待训练的网络参数；sigmod()为激活函数；q()表示c是h1,…,h n线性组合；c为编码网络的最终输出，是一个存储了输入序列信息的语义向量。

解码网络对语义向量c进行解码。在第一步解码过程中，即t=0时，解码网络读入语义向量c，输出当前的隐藏状态s0，利用Ateention机制跟据s0和编码器得到的各个工件的隐藏状态计算选择各个工件的概率，此时可选择概率最大的节点作为第一步选择的工件；在接下来的解码过程中，即t=1,2,…,n时，解码网络读入上一步的隐藏状态和上一步选择工件的特征向量，输出当前的隐藏状态st。根据st和各个工件的隐藏状态计算选择各个工件的概率。继续选择具有最大概率值且没有被选择过的节点添加到解当中，按照该方式不断选择工件，直至构造一个完整的解。计算公式如下：

式中：v T、W1、W2、y0、Why、Whs为待训练的网络参数；s0=c；y t∈o。

2.1.3 策略梯度优化参数

由于采用监督式的训练方式往往依赖高质量的标签，而对于PFSP问题，获得高质量标签是很困难的。因此采用基于策略的强化学习来优化指针网络的参数。训练目标是预期的完工时间，在给定实例o的情况下，该完工时间的期望如下：

假设实例o的加工时间服从分布O，则训练的目标函数为：

采用策略梯度法优化参数，上式的梯度是使用众所周知的REINFORCE算法[9]来计算的：

式中：b(s)为不依赖于π的基线函数，并估计预期完工时间以减小梯度的方差。

在训练过程中，每次从分布S采样M个实例，并对每个实例oi采样一个加工序列πi～pθ(.|o i)，上式中的梯度用Monte Carlo采样近似如下：

然后采用ADAM优化器进行参数优化参数：

2.2 改进的遗传算法

现有遗传算法求解PFSP问题通常使用NEH算法来生成一个解，然后随机生成来初始化种群，而且在迭代后期通常由于种群多样性降低而停滞在局部最优值附近。因此本文通过训练的指针网络与NEH算法相结合来初始化种群，以提高初始种群的质量，并利用重启机制，在算法陷入局部最优的时候对种群进行调整，来提高算法性能。

2.2.1 编码与种群初始化

PFSP最常用的编码是工件的简单排列，排列中工件的相对顺序表示车间机器对工件的加工顺序。如一个个体为（2，1，3）表示工件2最先加工，然后加工工件1，最后加工工件3。

为了更好地理解本文初始化过程，简要描述NEH过程[10]，该过程基于这样的思想，即所有机器上总加工时间最长的工件应该尽可能早地被调度。这种启发式方法可以分为3个简单的步骤如下。

（1）m台机器上作业的总加工时间计算如下:

（2）工件按Pi的降序排序。然后，获取前两个工件（具有较高Pi的两个工件），这两个工件有两种可能的加工序列，计算这两个加工序列的完工时间，选择完工时间较小的那个序列。

（3）继续选择第i个工件（Pi排第i的工件），并通过将其放置在已调度工件序列中所有可能的i位置来找到最佳调度序列。假如i=3，分别将其插入步骤（2）中选择序列的头部、中间和尾部生成3个序列，将选择3个中的最佳序列用于下一次迭代。

初始化过程基于这个NEH算法和这个算法的修改，初始化种群采用两种方法：第一种在步骤（2）中对工件进行排序后，只需从有序列表中选择两个随机工件，并用它们来交换前两个工件，然后继续步骤2和3的剩余部分来生成部分个体；第二种则在在步骤（2）中工件的序列为训练好的指针网络生成的序列，之后和第一种方法一样生成部分个体。

2.2.2 选择与种群迭代方案

常用的选择方案为轮盘赌选择和锦标赛选择。本文选择锦标赛选择，在整个种群中随机抽取n个个体，选择其中的最优的个体作为父代个体。

种群迭代方案有子代取代种群中最差个体和子代直接取代父代的两种方法。本文采用子代取代种群中最差个体的方法，即子代个体适应度大于种群中最差个体的适应度，并且子代并不存在与种群中的时候子代取代种群中最差个体。

2.2.3 交叉

遗传交叉算子通过组合父代来产生新的子代。目标是产生“更好的”子代，即在与父母杂交后创造更好的序列。常用的交叉算子有单点顺序交叉（OP）、两点顺序交叉（TP）、部分匹配交叉（PMX）等。本文采取一种相似块序两点交叉（SBOX）的算子，该算子首先考虑至少两个连续相同作业的块，只有那些在父代中占据相同位置的相同块才被直接复制到子代，然后再保留相同块的基础上采用单点顺序交叉的方法对父代进行交叉，具体过程如图3所示。

图3 SBOX算子

2.2.4 变异

遗传算法中的变异算子主要是为了避免收敛到局部最优，并在种群中重新引入丢失的基因。变异算子主要有互换突变、位置突变和移码突变。本文采用移码突变，即随机选择一个工件插入到另一个随机的位置上去，具体过程如图4所示。

图4 移码突变

2.2.5 重启机制

在遗传算法中，种群经过多次迭代之后，种群的多样性降低，使其停滞在局部最优值附近。因此在遗传算法中加入重启机制：在每次迭代，存储种群的最小完工时间mak i；如果mak i=maki-1则count mark+=1，否则countmark=0；如果countmar k＞Gr，则重新调整种群：首先将种群按照Cmax升序排序，将最小的20%加入新得种群，然后通过对最佳20%个体进行移码突变产生新的20%的个体加入新得种群，之后通过初始化种群的两种方法分别生成20%的个体加入新得种群，剩余20%个体则随机产生。

利用重启机制，每当种群中最小的最大完工时间超过Gr代不变时，重启机制将替换种群中除20%以外的所有最佳个体，希望重新引入种群多样性并脱离局部最优。

2.2.6 局部搜索

局部搜索从个体中随机提取所有工件，并将其重新插入所有可能的位置，当找到更好的个体时，它将被保留，并且该过程将继续，直到检查完所有工件。对每一代中的所有个体应用局部搜索会消耗很多时间，因此通常设置一个局部搜索概率Penh来控制个体是否进行局部搜索。本文在变异之后以Penh的概率对子代进行局部搜索，并且在每一代之后对种群中的最优个体以2Penh的概率进行局部搜索，以提高个体质量。

3 实验结果与分析

3.1 实验设计和参数设置

指针网络训练阶段相关参数设置如下：指针网络每次采样数（Batchsize）设为512，RNN采用长短时记忆网络（LSTM），网络隐藏层维数设为128，参数优化采用Adam算法，学习率设为1×10-4，学习率衰减速率每5 000步0.96。网络初始参数为[-0.08，0.08]之间均匀分布的随机数。训练数据随机生成1 024 000个数据，其中规模n_m=（30_5，30_10，30_15，30_20）的训练数据各占1/4，工件在各个机器上的加工时间为[0，1]均匀分布的随机数，经过预处理操作后进行训练。

在遗传算法迭代搜索环节相关参数设置如下：迭代次数为4 000，重启参数Gr=25，种群规模Psize=20。遗传算法中3个关键参数交叉概率Pc、变异概率Pm、局部搜索概率Penh的取值会影响算法的性能，因此采用Rec19算例进行正交试验，每个参数设置4个水平值，数值如表1所示。

表1 参数水平

利用正交表L16进行实验，在每组参数组合下独立运行算法10次，采用10次所得的完工时间平均值（AVG）作为响应值，结果如表2所示。

表2 实验方案与实验结果

各参数响应值如表3所示。由表3可知，Penh对算法性能的影响最大，Pc其次，Pm对性能的影响最小。根据试验结果的对比，最佳参数组合为：Pc=0.4，Pm=0.015，Penh=0.075。

表3 各参数响应值

算法性能评价标准采用最优相对误差（Best Relative Error，BRE）和平均相对误差（Average Relative Error，ARE），计算公式如下：

式中：Cmax为运行10次中的最优值；为运行10次的平均值；C*为当前算例的最优解。

本文使用Python 3.7编程，进行测试的平台的参数如下：CPU为Intel（R）Core（TM）i5-8300H CPU@2.30 GHz，内存16 GB，操作系统为Windows 10。

3.2 指针网络效果检验

为了验证指针网络生成初始解的有效性，将指针网络生成的解与NEH算法生成的解进行比较。选择PFSP问题常用的Rec测试算例，指针网络独立运行10次，取最优相对误差进行比较。比较结果如表4所示。从表中可以看出，指针网络生成的解有13算例结果优于NEH算法，因此采用指针网络与NEH算法结合来初始化遗传算法能够提高初始种群的质量。虽然21个算例的平均值指针网络结果比NEH算法差，主要是由于训练网络的数据最大为30个工件，而最后3个算例（Rec37、Rec39、Rec41）的工件数达到75个，因此在这几个算例上指针网络表现很差，拉高了指针网络的最优相对误差的平均值。

表4 指针网络与NEH算法结果

3.3 PT-HGA算法结果

为了验证PN-HGA算法求解PFSP问题的性能，选择PFSP问题常用的Rec测试算例，并将PN-HGA与求解PFSP的混合遗传算法（HGA）[3]、变参数量子进化算法（VP-QEA）[11]、混合差分进化算法（L-HDE）[12]、混合共生生物搜索算法（HSOS）[4]的求解结果进行比较，比较结果如表5所示。从表5可以看出，PN-HGA算法求解的21个算例有19个算例的最优相对误差和15个算例的平均相对误差等于或优于所比较的几种算法。而从整体上来看，PN-HGA的最优相对误差的平均值为0.375，平均相对误差的平均值为0.630，均优于其他4种算法，证明了PN-HGA算法的有效性。

表5 测试结果比较

4 结束语

本文提出了求解置换流水车间调度问题的一种指针网络与遗传算法结合的框架，创新之处：首先，根据PFSP问题与指针网络的特点对算例进行预处理，使得训练的指针网络可以适用于不同规模的算例，通过与NEH算法比较，验证了指针网络的性能；其次，将指针网络生成的解并结合NEH算法用来初始化遗传算法的初始种群，以提高种群质量，提升算法性能，并利用重启机制来提高算法的全局搜索能力。通过对Reeves标准测试集进行仿真测试，并与4种智能优化算法相比较，验证了本文算法的有效性。未来的研究着重于优化模型的训练，以提供更高质量的解，提升算法的性能，并将算法应用于其他类型的调度问题。