麻雀搜索算法解决柔性作业车间调度问题

杨红雄 王惠酩

（天津理工大学管理学院，天津 300384）

随着智能化在制造业中的普及，解决车间生产调度的问题能有效提高车间的工作学习效率，实现车间现场管理的有序化、智能化和高效化。为了合理地协调控制各个机器的生产以实现多方面目标的pareto最优状态，学者们经过多年的研究，使用各种不同的方法来分析和解决生产环节的FJSP。随着研究的逐渐深入，为了更贴近车间生产现场的工作状态，人们将柔性车间这一概念与车间调度问题相融合并提出了FJSP。由于FJSP问题在生产中广泛存在，因此，该问题引起了国内外相关学者的广泛关注与研究[1−5]。Ishibuchi H使用遗传算法求解FJSP问题，但算法的有效性较低[6]。Deng Q W使用NSGA-II算法并考虑分两阶段对多目标FJSP进行求解，并通过一些常用的函数验证算法的准确性[7]。Kaya S等人对相关文献进行了综述研究，并分析了多目标FJSP的最新算法的思想解决以完工时间最大、机器负荷最小和瓶颈工序负荷最小为目标的FJSP问题。陈魁等提出了优化小生境粒子群的算法求解模型，将运输时间这一变量加入FJSP问题，构建以完工时间最大化、机器负载最大化以及机器总负荷最小为目标的模型[8]。

2020年，薛建凯等人受到麻雀寻找食物和躲避天敌的行为启发提出麻雀搜索算法（sparrow search algorithm，SSA）[9]。该算法由于具有搜索精度高、收敛速度快、稳定性强和有效地避免局部最优值等方面的优点，受到了国内外学者广泛关注。毛清华等发现原始的SSA算法容易陷入局部最优问题，提出了将SSA与正弦余弦混合算法相融合的算法(improved sparrow search algorithm,ISSA)。并对算法的结果进行测验，证明 ISSA 具有更高的寻优精度和更快的求解效率[10]。汤安迪等人为了解决规划无人机航迹时方案的求解难度大、方案不容易收敛等一些问题，使用了基于混沌麻雀搜索算法的航迹规划方法，根据算法来规划无人机的航迹方案，证明了SSA算法可以有效地解决这类问题[11]。杨玮等以降低企业冷链物流的成本作为优化目标，考虑到冷链物流企业在货物存储和货物运输等环节会产生成本的现象，并结合我国最近正在实行的碳交易政策，将企业的碳排放代价同其他代价综合考虑，建立以总代价最低为目标的成本模型，设计并改良了麻雀搜索算法进行计算，证明了麻雀搜索算法可以有效地解决冷链物流运输问题[12]。韩统等人提出了一种将对数螺旋策略和自适应步长策略相混合的思想与麻雀搜索算法相结合（logarithmic spiral strategy and adaptive step size strategy of the SSA,LASSA）来解决无人机协同航向规划问题。验证了LASSA可以有效地解决多无人机协同航迹规划问题[13]。

综上所述，就算法的研究现状来说，由于SSA是最近提出的一种算法，具有收敛速度快，不易陷入局部最优等优点。并且目前的研究使用SSA解决的大部分都是无人机领域的问题，将SSA运用于实际车间生产制造中的研究较少。本文首次使用SSA解决柔性作业车间调度方面的问题，提出了基于FJSP的SSA算法，以最大完工时间最小和总能耗最小为优化目标求解FJSP。首先对FJSP问题进行描述并根据其特点分析建模，然后介绍了一种可以求解FJSP问题的SSA算法，利用标准算例进行仿真验证，由于SSA算法具有收敛速度快、结构简单和不易陷于局部最优的特点，解决了传统算法在解决SSA问题时收敛速度慢，易于陷入局部最优的问题，证明了SSA求解FJSP的可行性、高效性和优越性。

1 问题描述与建模

1.1 问题描述

作业车间调度是根据实际车间有限的可用资源和已定的生产计划，在满足工艺约束的基础上合理安排生产路线，均衡生产负荷，完成生产计划的同时实现某种既定目标的问题。FJSP是为了解决作业车间调度如何才能与多台并行机相结合而提出的，主要涉及以下两个问题：

（1）按什么顺序加工工件。

（2）如何合理地分配机器。

FJSP已被证明是更复杂的NP-hard问题，本文的FJSP问题主要是基于解决以上2个问题，并结合车间的实际生产为了达到完成时间最短和总流程时间最短的目标求出的pareto最优解。

FJSP可以用以下例子来描述：设车间有m台机器，需要加工n个工件，每台机器表示为M1,M2,···,Mn。每个工件表示为N1,N2,···,Nn。每个工件在机器上一次性完成的工艺过程叫工序，Oij表示工件i的第j道工序。最终的目标是使完成这批工件所用的时间最短和消耗的能源最少。相关的约束条件有：

（1）一台机器在某一时刻只加工一个工件。

（2）每个工件加工生产的工序相同，工序的加工顺序相同，根据算例的不同，不同工件在不同机器上加工消耗的时间不同。

（3）相同工件在某一时刻不能被不同的两台机器加工。

（4）工件在加工过程中不能更换机器加工。经典的FJSP如下所示。以5台机器加工3个工件，每个工件有3个加工工序的情况为例，加工的时间表如表1所示。

1.2 数学模型

数学模型可以清晰直观地表达FJSP，我们将定义以下几个参数变量：

r：工件总数，共有r个需要加工的工件，每个工件表示为N1,N2,···,Nr。

n：工序总数，工件Ni共有n道工序(i=1,2,···,r)。

k：机器总数，共有k个可以加工的机器，每台机器表示为M1,M2,···,Mk。

Oij：工件Ni的第j道工序(j=1,2,···,n)。

Ωk：所有机器的集合{M1,M2,···,Mk}。

Ωik：工件Ni的第j道工序所有可选加工机器的集合，是机器集合Ωk的子集，Ωik∈{M1,M2,···,Mk}。

表13×5的完全柔性作业车间加工时间表

mik：工件Ni的第j道工序所有可以选择的加工机器数。

Mijh：工件Ni的第j道工序(Oij)选择在机器Mh上加工(h=1,2,···,k)。

Pijh：工序Oij在机器Mh上的加工时间。

Sij：工件Ni的第j道工序(Oij)的开始加工的时间。

Cij：工序Oij的完成加工时间。

Ci：工件Ni的完成加工的时间。

Cmax：所有工序完工时最大的完工时间。

Wt：所有机器加工完成最大工作负荷。

FJSP的约束条件有：约束条件是限制操作的可能分配的规则。FJSP问题主要有以下几个有数条件：

式（1）表示加工第i个工件的第j道工序（Oij）只能在该道工序可以选择的机器集合（Ωik）中选择一台机器进行加工。式（2）表示加工第Ni个工件的第j道工序（Oij）的完工时间应大于等于其在该机器上的开始加工时间与加工时间之和。式（3）表示一个零件的不同工序间需要满足先后顺序。式（4）表示机器上相邻工件之间前一工件工序的完成加工时间应小于等于下一工件工序的开始加工时间。式（5）表示所有工件最后一道工序的完工时间都小于等于最大完工时间。

本文考虑生产现场的时间生产情况，以最大完工时间（Cmax）和机器最大工作负荷（Wt）为目标，建立最小化数学模型。目标函数如式（6）和式（7）。

1.3 双目标优化

对于2个目标的FJSP问题目前主流的解决方法主要有3种：

（1）目标规划法：该方法主要用于解决参数和约束较少的优化问题，首先需求出各子目标的最优值，然后将各子目标的最优值作为初始问题的约束。最后，将每个子目标的值与其最优值做差，最终的结果就是初始问题的最优解。

（2）功效系数法：该方法对每个目标函数进行赋值，通过每个目标对于整体结果的重要性来决定赋值的大小，综合函数值最优的结果及为函数的最优解。

（3）动态权重法：该方法对每个目标函数进行动态赋值，与功效系数法不同的是，在算法迭代过程中，每迭代一次权重系数就变化一次，直到得到最优解为止。

文献[14]认为产品的加工时间越小对于制造商降本增效的影响越突出，在车间调度的实施过程中，Cmax越小说明总生产周期越短，有助于提高企业的生产效率与资源利用率，Wt越小说明生产消耗的能耗越小，有助于降低企业生产成本。功效系数法相较其他两种方法更适用于子目标之间不均衡、具有主导性的多目标问题，因此，本文考虑使用功效系数法求解FJSP问题。用dj(0

因此，目标函数可以表示为

其中：ω1+ω2=1。

本文根据文献[15]中的Delfi调查法得到ω1和ω2，对应权重分别为0.7、0.3，在实际生产调度问题中该权重值应根据车间生产需求情况进行调整。

2 求解FJSP的SSA流程设计

SSA中每一只麻雀都代表一组可行的调度方案，麻雀的适应度值表示调度方案的合理程度，适应度值越高则表示方案越可行。麻雀寻找食物的过程可以被想象为“发现者-追随者”模型，SSA将群内个体分为发现者、追随者和侦察者3种类型，为了提高个体的捕食几率，当追随者通过发现者获取食物时，种群中的一些个体为了增加自己的捕食量会与其他同类争抢食物，同时，以安全第一为原则按比例将一部分麻雀作为侦察者进行侦察和预警，当侦察者发现危险时及时警告其他麻雀如果发现危险则停止进食，由发现者重新寻找食物。通过不断地捕食和反捕食行为迭代更新进行寻优进化。

下面将介绍一种适合解决FJSP的SSA并解决一个以最大完工时间最小和总能耗最小为优化目标的FJSP。

2.1 编码与解码

SSA通过不断地更新自身的位置和寻找食物源的方式对优化的目标进行搜索，FJSP主要是解决工件排序和机器指派这2个问题，因此，本文使用两阶段向量编码方法，前一段确定工序的加工顺序，后一段确定机器的指派问题，保证了编码后个体的有效性。

以3个工件每个工件包含两道工序的问题为例，编码链前半段（第1位−第6位编码）为工序随机排序的方案。例如，编码中第二位的“3”表示工件3的第一道工序；后半段（第7位−第12位编码）为机器的随机分配方案，每个编码表示工序在机器上的加工顺序。例如，编码中第七位的“2”表示工序O12即第一个工件的第二道工序在机器2上加工。随机生成的编码链按图1的方式进行存储。

图1 编码方式

在解码的过程中，首先根据工序排序编码链确定一个工件在机器上的加工顺序，然后机器分配编码确定各个机器上加工的工序顺序，即转化为一个工序表，根据工序表将所有工序安排在适当的加工机器和加工位置上，最后生成可行的调度方案。

2.2 SSA算法步骤

2.2.1 种群初始化

设定算法的各部分参数如最大迭代次数、种群数量、发现者比例和安全阈值等。

本文随机生成编码产生初始调度解，每一只麻雀表示一个调度方案，由n只麻雀组成的种群可以表示为

其中：d为问题的维数；n为麻雀的数量。那么，每个方案的适应度表示为

其中：f是适应度值，根据适应度值的大小对麻雀个体进行排序，进而选择出最优个体和最差个体，得到全局最优位置，然后根据设定的警报值进入迭代循环。

2.2.2 发现者的位置更新

在SSA中，麻雀个体相对种群的位置表示可行的调度方案。假设在D维空间中存在N只麻雀，每只麻雀可以表示为一个矩阵

则麻雀i的位置可以记作

式（8）中：n是麻雀的数量。式（9）中：i表示第i只麻雀。i=1,2,3,···,n。D代表变量的维数。Xi,1表示问题维数为1维时，第i只麻雀的位置。

每个个体的适应度值表示为

Fx表示每个个体的适应度值，根据适应度对麻雀进行排序，选出适应度好的麻雀个体作为发现者寻找食物源并优先获得食物，带领其他麻雀向食物源靠近。在种群中，发现者和追寻者数量在每次迭代循环中一般都保持一致，占麻雀种群数量的10%～20%。发现者的位置更新公式为

其中：t为算法当前的迭代次数，i表示第i只麻雀，j表示问题的维数，表示第t+1次迭代时第i只麻雀在第j维的位置；µ是范围在（0,1）之间的随机数；Tmax是最大迭代次数；R2∈[0,1]、ST∈[0.5,1]分别代表预警值和安全值；Q是一个遵从[0,1]正态分布的随机数；L是一个所有元素都是1的1×d维矩阵。当R2

2.2.3 追随者的位置更新

追随者的位置更新公式为

2.2.4 侦察预警行为

当种群中的侦察者发现危险或捕食者时，就会向种群发出警报信号，此时，无论是寻找食物的发现者还是正在进食的追随者都会放弃当前食物并改变其位置向安全的位置移动。发现者到达安全位置后才会继续寻找新的食物源，继续迭代更新其位置。一般种群都会选取SD（种群数量的10%～20%）只麻雀作为侦察者对周围位置的安全侦察预警。侦察者的位置更新公式为

式（14）中：β是步长控制参数，服从均值为0，方差为1的正态分布随机数。fi是第i只麻雀的适应度值；fg是当前麻雀的全局最优适应度值；K是步长控制参数服从[−1,1]的均匀随机分布，用于表示麻雀的移动方向；fw是当前适应度值最低的个体；ε是常数，为了防止出现分母为0的情况，一般 ε的值极小。当fi≠fg时表明，麻雀i的位置处于种群的边缘，极易受捕食者的攻击；当fi=fg时表明，麻雀i正处于种群中间的位置，意识到了来自捕食者的危险，需要靠近其他麻雀个体来减少自己被捕食的危险并调整搜索策略。

算法的具体步骤如下：

Step1：输入算例的数据。

Step2：初始化种群，如设定麻雀种群中发现者的数量、意识到危险的麻雀所占种群的比例。

Step3：初始化算法参数并对数据进行编码，生成初始调度方案，找到种群中最好和最差的个体。

Step4：根据式（13）、（14）更新发现者、追随者位置。

Step5：判断新位置的适应度值是否好于当前位置，如果没有则保持当前位置不变继续下一步操作；如果有则更新当前位置。

Step6：直至收敛或达到最大迭代次数算法结束并得到优化目标的最优解。

根据以上对于数学模型的描述和算法的步骤，设计基于FJSP问题的流程如图2所示。

图2 算法流程图

3 仿真测试

本文使用MATLAB编程语言并使用MATLAB 2017a运行程序。运行环境为：WinXP操作系统下内存为8 GB的Intel Core(TM) i5-7200U CPU 2.50 GHz的计算机上运行。

文献[9]中认为发现者比例应占种群数量的10%–20%；安全阈值ST∈[0.5,1]；种群大小和迭代次数应与对比试验保持相同设置，因此，SSA算法参数设定如下：工件总数为r，机器总数为k，种群大小为200，迭代次数为300，发现者比例为20%，追随者比例80%，安全阈值为0.5，目标权重ω1=0.7，ω2=0.3。如表2所示。

表2 算法参数

为了检验算法的寻优性能和证明算法在解决FJSP问题的可行性，使用实例一证明算法的可行性，使用实例二和实例三对SSA的性能进行比较。实例一是文献[16]中同样以最大完工时间和总负荷最小为目标函数的6×6实际案例；实例二和实例三是Kacem测试集中的3×4和4×5算例。

为验证SSA在解决实际FJSP问题的可行性，使用文献[16]中的实际生产车间的原始数据。文献[16]中数据来自于某汽车公司总装车间的生产数据，经过取整处理后得到规模为6×6的实验数据。将实例一数据代入本文算法中运算，结果与文献[16]中tsPSO和CMABC算法得出的结果进行对比。表3为示例一实际案例的试验结果。其中，加粗的结果表示同一算例下使用各算法得到的最优值，“N/A”表示相关文献中没有给出这一算例的结果。

表3 实际案例实验结果

结果表明，SSA算法仿真模拟的结果明显好于其他两种算法，还给出了与其他两种算法完全不同的调度方案，增加了企业生产调度时的选择方案。从单目标最优值来看，SSA算法在Cmax、Wt两个目标都得到了最优解，使企业在选择上更加灵活。将实例一的生产数据通过SSA运行，得到最优解为：Cmax=12、Wt=41，证明了SSA在实际生产的可行性。图3为实际生产数据最优解的甘特图。

图3 实际案例甘特图

采用Kacem I[17]设计的测试算例来验证算法的有效性。将SSA算法与分布估计算法[18]、基于正态云的状态转移算法[19]及混合人工蜂群算法[20]的文献中所提及的算例结果进行比较，证明SSA解决柔性车间调度问题的优越性。测试结果如表4所示。其中，加粗的结果表示同一算例下使用各算法得到的最优值，“N/A”表示相关文献中没有给出这一算例的结果。

表4 实际案例实验结果

结果表明，对于Kacem1问题，SSA得到的3组解除了均优于EDA得到的两组解。从单目标最优来看，SSA在Cmax、Wt两个问题的最优解分别为6和15，较其他算法具有较强的求解优势。对于Kacem2问题，虽然CSTA和SSA都得到了（11，32，17.3）的最优解，但在解的数量上，SSA明显优于其他两种算法，为实际调度的方案提供了更多选择方式。从单目标最优来看，SSA在Cmax、Wt两个问题的最优解分别为11和32，说明SSA具有较强的寻优能力，能够向组合后的单目标最优解提供较多的选择，证明了SSA在可行解数量和单目标可行解上的优势。图4和图5分别给出了Kacem1的最优解（6，15，8.7）和Kacem2的最优解（11，32，17.3）的最优解的甘特图。

图4 Kacem1最优解的甘特图

图5 Kacem2最优解的甘特图

4 结语

针对目前元启发式算法在解决FJSP问题时存在收敛速度慢，易于陷入局部最优的问题。由于SSA算法具有收敛速度快，寻优能力强的特点，本文结合SSA算法提出了一种可以解决FJSP问题的SSA方法。以最大完工时间和总能耗为指标构建了作业车间调度模型，为了适应FJSP改变了SSA的编码和解码方式。最后，使用几种FJSP的经典算例验证SSA解决FJSP的可行性，说明了SSA在求解FJSP的可行性和高效性。下一步将考虑将SSA应用于更多约束的车间调度问题上，解决更多实际生产问题。