基于多目标麻雀搜索算法的柔性车间生产排程方法

张富强， 吴 磊， 惠记庄， 邵树军， 杜 超

(1.长安大学道路施工技术与装备教育部重点实验室， 西安 710064；
2.长安大学智能制造系统研究所， 西安 710064；
3.陕西法士特齿轮有限责任公司， 西安 710119)

个性化的客户需求和激烈的市场竞争促使传统的集中代工生产模式向大规模个性化定制生产模式转变[1-2]. 多品种、小批量、高质量、强交货期、低消耗等要求成为当前柔性车间必须面临的问题. 在此背景下，组织协调各类制造资源，并对生产过程进行有效管控来敏捷响应市场多样化和不确定的需求，快速制造出客户产品显得尤为重要.

柔性车间生产排程是当前的研究热点问题. 多数研究仅针对最大完工时间、交货延迟期等单目标进行建模，但是多个目标同时优化更加符合实际生产状况. 部分学者利用MOEAD(multiobjective evolutionary algorithm based on decomposition)[3]将多目标分解为单目标进行求解，但是该方法不适用于优化目标数值规模相差较大的情况，并且权值的均匀性难以保证，权值难以选取，对柔性车间生产排程问题的适用度较低；
利用非支配排序和精英保留策略产生Pareto前沿解的方法更加适用于实际柔性车间生产排程. 在算法求解方面，运筹学、数学等领域方法主要解决小规模排程问题；
而启发于自然界生物群体的集体性行为而设计的群智能算法被众多学者和专家用于解决大规模排程问题. Sassi等[4]提出了一种基于分解的多目标人工蜂群算法，可以高效且稳定地求解多目标生产排程问题；
李益兵等[5]将动态领域搜索引入人工蜂群算法，针对车间生产中的碳排放量、噪声、废弃物等问题进行优化，获得了较好的排程结果；
黄海松等[6]采用轮盘赌机器派选方式等到质量较高的初始化种群，通过离散花朵授粉算法求解多目标调度问题；
陈魁等[7]将小生境技术引入粒子群算法，避免了算法早熟收敛和不稳定性，实现了车间多目标排程；
Nouiri等[8]将粒子群优化算法嵌入到多智能体系统中，为求解动态如机器故障、维护等的柔性生产排程提供了一种途径. 尽管采用群智能算法求解柔性车间生产排程问题是当前求解大规模生产排程的有力工具，部分算法也已被用于求解多目标柔性车间生产排程问题，但是目前并没有任何一种算法可以获取所有问题的最优解，所以学者们还在进行相关研究，以期待获得更加有效的方法.

麻雀搜索算法(sparrow search algorithm,SSA)是薛建凯等于2020年提出的具有高性能的全局搜索能力的新型群智能算法，主要是受麻雀的觅食行为以及反捕食过程启发而设计的算法，相比于灰狼优化算法、粒子群算法、引力搜索算法，它具有更快的求解速度、更高的求解精度、更佳的全局搜索能力[9]. SSA已被成功运用于多个工程优化问题的求解中[10-14]，但是目前没有将其应用于求解柔性车间生产排程问题的研究.

本文将非支配排序引入麻雀搜索算法中，提出了一种多目标麻雀搜索算法(multi-objective sparrow search algorithm, MOSSA)，并将其应用于多目标柔性生产排程问题的求解中. 通过Pareto等级和拥挤度定义最好和最差位置个体，利用SSA进行种群更新，寻找最优解集，实现多目标优化. 采用两段式编码规则生成初始种群，利用MOSSA迭代更新获取Pareto前沿解，求解多目标柔性车间生产排程问题，最后通过仿真实验验证了所提出的MOSSA对于生产排程问题求解的可行性和优越性.

车间生产排程问题可简要概括如下：车间中有n个待加工工件，m台加工机器，每个工件Ji包括ri(ri≥1)道工序，按照指定的工艺路线进行加工,每道工序Oij可在不同的机床上加工，由于不同机器的加工能力不同，工序Oij的加工时间取决于所分配的机器.

为便于模型表达，引入表1数学符号定义.

柔性作业车间中，加工完成时间是生产调度中最直观的优化指标，直接反映车间生产效率，所以在排程中，完工时间应该加以考虑；
另一方面，在新的制造模式下，绿色制造是其中的一个重要理念，因此考虑生产加工过程中的加工能耗指标，是优化车间生产制造过程的一个重要途径，总的加工能耗越小，越符合制造要求，由于车间生产的机器柔性，同一机器可以加工多个不同的工序，应尽可能使车间的总机器负载最小，减小车间的生产消耗；
此外，不同机器的加工成本是不一样的，为最大化车间效益，应降低加工成本. 所以，本文以降低柔性车间的完工时间、机器总负载以及总的加工成本为优化目标. 目标函数表达式为

(1)

(2)

(3)

根据实际生产情况，存在如下约束条件：

1) 工件开始时间与加工时间要小于完成时间，即

(4)

2) 上一道工序的结束时间要小于下一道工序的开始时间，即

CTijk≤STij+1

(5)

3) 每个工件的完工时间都应该在总的完工时间之前，即

(6)

4) 一台机器同一时间只能加工一个工件，即

(7)

本文将非支配排序引入基本麻雀搜索算法中，设计了一种多目标麻雀搜索算法，并将其应用于求解柔性车间生产排程问题.

2.1 基本麻雀搜索算法

圈养家麻雀分为“探索者”和“追随者”2种，探索者主要是为种群提供整个麻雀群觅食的区域和方向，追随者通过探索者来获取食物，麻雀种群中探索者和追随者的身份是动态变化的，可以发生转换. 同时，种群中部分麻雀为“侦察者”，承担侦察预警工作，它们在觅食的过程中时刻注意周围环境，一旦察觉到捕食者威胁，会迅速逃离当前位置. 麻雀搜索算法就是模拟麻雀种群搜索食物的过程设计的启发式算法.

2.1.1 迭代公式

探索者具有较高的能源储备，在种群中负责食物搜索工作，并且在发现捕食者时带领追随者去往安全区域. 在每次迭代的过程中，探索者的位置更新描述为

(8)

式中：t代表当前迭代数；
j=1,2,…,d，d表示麻雀个体具有d个维度信息；
itermax表示最大的迭代次数；
Xi,j表示第i个麻雀在第j维中的位置信息;随机数α介于0与1之间；
预警值R2∈(0,1]和安全值ST∈[0.5,1]；
随机数Q服从正态分布；
L是一个所有元素为1的1×d的矩阵.

当R2R2≥ST时，种群中的部分麻雀察觉到危险，向种群中其他麻雀示警，此时所有麻雀都需要迅速逃离，另寻地方觅食[9].

追随者在觅食过程中时刻监视着探索者，它们会和找到更好食物源的探索者抢夺食物. 除此之外，适应度值较低的部分追随者会飞往其他各处觅食. 在每次迭代的过程中，追随者的位置更新描述为

(9)

式中：Xp是探索者的最佳位置；
Xworst表示当前全局最差位置；
A表示一个1×d的矩阵,其中每个元素随机赋值为1或-1,并且A+=AT(AAT)-1. 当i>n/2时，第i个追随者处于饥饿的状态，它将随机飞往其他地方寻找食物；
i≤n/2时，表示追随者位于当前种群最优位置附近，食物资源充足，可就近觅食[9].

部分麻雀觅食的同时肩负警戒的任务，当察觉到危险时，将发出警示，无论是探索者还是追随者，都将逃离当前位置另寻食物. 位置更新描述为

(10)

式中：Xbest是当前的全局最佳位置；
随机数β～N(0,1),控制步长；
随机数K介于-1～1，控制麻雀个体的移动方向；
fi是麻雀个体i的适应度值；
fg和fw分别是t次迭代后全局最大和最小适应度值；
极小值ε，防止分母为0.fi>fg表示麻雀个体位于种群边缘，察觉到了危险，向最好位置个体移动；
fi=fg表示麻雀个体是最好位置个体，它察觉到危险将飞向种群边缘，逃离当前位置[9].

2.1.2 SSA求解流程

首先设置探索者和侦察者比例、预警值的大小，初始化种群；
其次计算适应度函数并找出最好和最差位置的麻雀个体；
按照式(8)～(10)对探索者、追随者以及侦察者位置进行更新，获取当前种群最优位置，与上一代种群比较，若比之前种群位置更好，则进行更新，否则不更新，再次重新迭代，满足终止条件后停止.

2.2 编码和解码

由于柔性作业车间同时拥有工序柔性和机器柔性，编码方式采用两段式编码. 第一段基于工序进行，根据染色体中工件的序号出现的次序编码，第k次出现的工件序号表示该工件的第k道工序. 第二段基于机器进行，根据工件可用机器编码，依次为工件Ji(i=1,2,…，n)的每道工序可用机器之一，标号代表相应工序的加工机器. 例如工序基因链[32111434]表示加工工序为O31O21O11O12O13O41O32O42；
若此时的机器基因链为[34142434]，表示O11使用3号机器，O12使用4号机器，O13使用1号机器，O21使用4号机器，O31使用2号机器，O32使用4号机器，O41使用3号机器，O42使用4号机器，解码结果如图1所示.

图1 示例的解码结果Fig.1 Decoding result of the example

为了使算法更加适用于实际生产车间，定义每个工件开始加工时间不一定相同，以每个工件的到达时间为开始时间. 工件的每道工序开始加工时间可分为以下4种情况：

1) 若为第一道工序，且机器未曾使用过，则该工序的开始时间为工件到达时间.

2) 若为第一道工序，且机器曾使用过，则开始时间为工件到达时间与机器上一次使用时间中的较大者.

3) 若不是第一道工序，机器未曾使用过，则开始时间为上一道工序的结束时间.

4) 若不是第一道工序，且机器曾使用过，则开始时间为上一道工序结束时间和机器上一次加工时间中的较大者.

2.3 Pareto排序与选择策略

为减少计算复杂度，采用Konak等[15]提出的一种快速非支配排序方法进行排序. 本文优先选择Pareto等级低的个体，相同等级中选取拥挤度值大的个体，并在选取出的种群中将Pareto等级为1、拥挤度值最大的个体定义为位置最佳个体，等级最高、拥挤度值最小的个体定义为位置最差个体.

2.4 种群的更新

由编码方式可知，柔性作业车间问题的解是离散化的，而基于麻雀搜索算法的求解的位置向量是连续的，因此二者之间需要转换机制. 本文利用工序染色体的总长度作为第t次迭代的位置，利用公式(8)～(10)计算得到的值与工序染色体总长度比较，选取更小的值作为t+1次迭代中染色体需要变更位置的数量s.更新种群时，工序段染色体随机交换s个节点的位置，机器段染色体随机选取s个节点，更新为其他的可用机器之一.

算法步骤如下，流程图见图2.

图2 MOSSA流程图Fig.2 Flow chart of MOSSA

步骤1输入参数：最大迭代次数G，探索者数量PD,侦察者数量SD，安全值ST.

步骤2初始化种群P0,t=0.

步骤3生成子一代种群.

步骤3.1 非支配排序，选出当前种群的最好位置个体和最差位置个体.

步骤3.2 基于SSA的麻雀种群更新.

步骤4父、子代合并.

步骤5快速非支配排序选取新的子代种群.

步骤6基于SSA的麻雀种群更新.

步骤6.1 fori=1:PD

使用式(8)更新麻雀种群位置；

End for

步骤6.2 fori=(PD+1):N

使用公式(9)更新麻雀种群位置；

End for

步骤6.3 forj=1:SD

使用公式(10)更新麻雀种群位置；

End for

步骤7如果t否则算法终止.

2.5 收敛性分析

MOSSA将非支配排序引入麻雀搜索算法，麻雀搜索算法具有较好的全局收敛性，由于非支配排序的支配特性， MOSSA每次迭代过程中，都在向Pareto等级为1的方向趋近，因此MOSSA具有较好的收敛性.

为了验证MOSSA求解多目标生产排程问题有效性，以文献[16]中的完全柔性的车间调度问题为算例进行了仿真实验，算例工艺路线数据如表2所示，8个批次的零件可在7个机器上加工，每台机器的加工时间不一样，表3所示为每台设备的单位时间加工成本. 仿真软件为matlab2018a，硬件如下：处理器为Intel(R) Core(TM) i5-4200H CPU @ 2.80 GHz，运行内存为8 GB.

3.1 参数灵敏度分析

麻雀种群由探索者与追随者组成，二者比例之和为1，同时部分麻雀还承担着侦察预警的作用，因此，仿真实验中对实验结果可能有较大影响的参数是探索者比例和侦察者比例，二者决定每次迭代中式(8)～(10)的循环次数，影响寻优能力以及跳出局部最优的能力. 采用控制变量法进行实验，研究探索者和侦查者比例的影响，实验中选取迭代次数为200，麻雀种群为100，为消除实验中可能存在的

表2 算例中工艺路线数据[16]

表3 算例中机器加工成本[16]

误差，每一组参数运行10次取平均值；
为消除由目标函数数量级不同带来的影响，对运行结果进行z-score规范化，并将规范化后的数值取绝对值后求和，将所得值作为评价标准，得到表4所示结果；
从中可知，不同参数情况下，数值变化不大，说明在该

表4 探索者和侦察者比例灵敏度分析值

模型算例中，探索者比例和侦察者比例对MOSSA的影响不大.

3.2 算法对比

为了验证MOSSA求解多目标柔性车间规划问题的性能，将算法运行参数设置为：种群大小为100，迭代次数为200，探索者比例为20%，追随者比例为80%，负责侦察的麻雀比例为10%，安全值为0.8，运行20次后得到的各目标函数均值与其他算法结果[16]对比，结果如表5所示. 由表5中可知，3个目标函数均寻找到更佳的结果，MOSSA相对于其他3种算法具有更好的收敛性能，具有更好的寻优能力，尤其是相比于GA算法有较大程度的提升，相比于多目标粒子群算法(multi-objective particle swarm optimization, MOPSO)和多目标教学优化算法(multi-objective teaching-learning based optimazation algorithm, MOTLBO)提升较小. 运行速度方面，MOSSA相对于其余三者均有提升，相对于GA、MOPSO和MOTLBO平均运行时间分别缩短了10.53、4.53、3.83 s.

表5 算法结果对比

3.3 仿真结果与分析

为了验证了MOSSA在求解多目标生产排程问题的可行性，选取种群大小为100、迭代次数为200、探索者比例为20%、负责侦察的麻雀比例为10%、安全值为0.8进行仿真实验. MOSSA随机运行一次后产生的Pareto解集如表6所示，相应的Pareto前沿如图3所示，随机选取其中的一组解绘制甘特图如图4所示. 在图4所示排程安排下，车间完工时间为12 h，加工成本为664元，机器总负载为53 h，调度结果满足算例要求.

算法运行过程中发现，Pareto等级为1的解集中有目标函数值完全相等的个体，甚至是存在所有等级为1的解都为同一值的现象，即算法收敛到一个点上，但是比较相应的工序编码与机器编码发现二者之间存在差异. 如表7所示的为一个Pareto解集，其中只有8个解的目标函数值是不一样的，图5中(a)和(b)分别是解集中的第3个解和第6个解的排程甘特图，可知，相同目标函数值的甘特图是不相同的，说明二者的编码是不一样的，比较其他几个解发现，编码结果也不相同，说明解集中的解是不同的个体. 上述实验结果表明，在该模型中，多目标麻雀搜索算法具有较好的收敛性. 另一方面，该种情况下，如果生产过程中存在某台机器故障，或者某毛坯到达车间时间延迟等动态扰动时可以快速替换为另一种排程方式，达到完全相同的效果，提高生产效率，实现动态高效的排程；
如图5所示，假设生产过程中工件3的毛坯无法在开机时间送达车间，则可选择图5(b)的排程方式，工件3的毛坯只需在12 h之前送达即可. 这在一定程度上反映了MOSSA对于多目标柔性车间排程的有效性以及MOSSA高效的搜索性能.

表6 Patero解集

图3 柔性车间Pareto前沿Fig.3 Pareto front of flexible workshop

图4 柔性车间排程甘特图Fig.4 Gantt chart of flexible workshop scheduling

表7 存在相同值的Pareto解集

图5 相同目标值的不同排程方式Fig.5 Different scheduling methods with the same target value

对于迭代优化获取的Pareto解集中相同目标函数值的排序结果，首先根据工厂状况，如机器状况、工件毛坯的到达时间等进行选择，选取最适应当前工厂状况的排序结果；
其次，若工厂状况良好，正常运行，以最小化单机总负载为二次优化目标，对排序结果进行再次选择，尽可能减少单机工作负载过大的情况，避免出现瓶颈机器，合理分配机器的利用率，提高机器使用寿命.

1) 以最小化完工时间、最低车间总负载和最小化车间生产成本建立多目标柔性车间生产排程数学模型.

2) 提出了一种融合非支配排序和麻雀搜索算法的多目标算法MOSSA；
通过两段式编码以及连续化转变实现对柔性车间生产排程问题的求解.

3) 通过控制变量法进行实验，结果表明，在该模型下，探索者比例和侦察者比例对MOSSA的影响较小，二者的灵敏度不高.

4) 通过算例对比MOSSA与其他算法的性能，结果表明MOSSA解决多目标柔性车间生产排程的可行性、有效性和优越性.