混合改进麻雀算法解决柔性车间调度问题-凯发娱乐官网

1. 引言

在制造业飞速发展和全球竞争升级背景下，企业竞争力关键在于生产效率和灵活运营。柔性车间调度作为生产管理核心，直接影响效率、资源优化及客户满意，其复杂性包括多任务、机器协同、多重约束和需求变化，令传统调度方法难以高效应对。鉴于其跨行业应用价值和经济影响力，深入探索柔性车间调度不仅现实意义显著，且潜在经济价值巨大。

近年来，智能优化算法由于其卓越的全局探索能力和自适应特性，在解决柔性作业车间调度问题(fjsp)时展现出了显著的优势。国内外研究者对此领域的探讨与应用日益增多。例如，孔飞等人针对柔性作业车间调度问题，提出了一种改进的双层粒子群优化算法，加入了停滞阻止策略和凹函数递减策略，并通过若干算例验证了该算法的有效性和精确性[1]。王佳怡等人则提出了改进型遗传算法来处理车间调度问题，引入翻转变异和两点随机变异策略，构造出一个多目标混合整数线性规划模型，有效地提升了求解fjsp问题的收敛速度[2]。此外，姜天华针对fjsp，将变邻域搜索算法运用到灰狼优化算法中，提出了一种混合灰狼优化算法，大大提高了灰狼优化算法求解精度[3]。这些研究成果进一步推动了智能优化算法在柔性作业车间调度问题上的实际应用与理论发展。

在众多智能算法中，麻雀算法在解决复杂优化问题时表现出一定的优势，如较快的收敛速度、较高的收敛精度以及较强的鲁棒性等。麻雀搜索算法(sparrow search algorithm, ssa)其设计理念源自于自然界中麻雀群体觅食行为的模拟[4]。刘丽娜等人率先尝试将改进后的麻雀算法应用于车间调度场景，鉴于ssa在后期搜索过程中可能陷入局部最优的问题，他们引入了量子计算原理，并结合多邻域搜索和高斯扰动技术，以弥补ssa在解决离散型问题时深度探索能力的不足[5]。毛清华团队则提出了另一种经过改良的麻雀算法，该算法结合了柯西变异原理与反向学习机制，有效增强了算法跳出局部极小点的能力，从而在求解复杂优化问题时取得更为优异的表现[6]。

现有麻雀搜索算法可能因搜索局限性而难以逃离局部最优，导致在处理柔性车间调度问题时收敛缓慢、解质不佳。本文针对此，基于ssa并融入极限调度最小化编码、自适应levy飞行、鲸鱼优化、数量递减及柯西扰动策略，设计了一种混合遗传算子改进算法，有效提升了求解质量和收敛速度，实例验证了算法的优越性。

2. 问题描述及数学模型

2.1. 柔性作业车间调度模型描述

本文探讨的柔性作业车间调度问题[7]模型可表述为这样一个场景：在具有m台机器的车间环境中，需将n个工序有序关联的工件分配至这些机器进行加工处理。值得注意的是，并非所有机器都具备加工每个工件的能力，且对于每个工件而言，在其候选机器上的各个工序加工时间是已知的。研究的核心目标在于构建一个灵活有效的调度方案，确保每个工件都能被恰当的机器按既定工序顺序完成加工，并据此确定各个工序开始和结束的具体时间点，从而最大程度地减小整个生产流程中的最大完工时间。

2.2. 柔性作业车间调度数学模型

符号描述：

m：机器总数；

n：工件总数；

v：总的机器集；

i，e：机器序号，i,e=1,2,3,⋯,m ；

j，k：工件序号，j,k=1,2,3,⋯,n ；

h j ：第j个工件的工序总数；

l：工序序号，l=1,2,3,⋯, h j ；

v jh ：第j个工件的第h道工序的可选加工机器集；

m jh ：第j个工件的第h道工序的可选加工机器数；

o jh ：第j个工件的第h道工序；

m ijh ：第j个工件的第h道工序在机器i上加工；

p ijh ：第j个工件的第h道工序在机器i上的加工时间；

s jh ：第j个工件的第h道工序加工开始时间；

c jh ：第j个工件的第h道工序加工完成时间；

l：一个足够大的正数；

d j ：第j个工件的交货期；

c j ：每个工件的完工时间；

c max ：最大完工时间。

x ijh ={ 1,如果工序 o jh 选择机器i 0,否则

x ijhkl ={ 1,如果工序 o ijh 先于 o ikl 加工 0,否则

本文的柔性作业车间调度问题受到以下假设约束：

s jh x ijh ×p≤ c jh (1)

c jh ≤ s j( h 1 ) (2)

c jh ≤ c max (3)

s jh p ijh ≤ s kl l( 1− y ijhkl ) (4)

c jh ≤ s j( h 1 ) l( 1− y iklj( h 1 ) ) (5)

∑ i=1 m jh x ijh =1 (6)

∑ j=1 n ∑ h=1 h j y ijhkl = x ikl (7)

∑ k=1 n ∑ l=1 h k y ijhkl = x ijh (8)

s jh ≥0 , c jh ≥0 (9)

本文的目标函数为最小化最大完工时间：

min∫=min( max( c j ) ) (10)

公式(1)和(2)体现了每一个工件内各工序间必须遵循的严格先后顺序。公式(3)设定了对每个工件完工时间的限制，即任何工件的完工时间都不能超过整个生产流程的最大完工时间。(4)和(5)公式强调了在任意时刻，同一台机器只能执行一道工序，不可同时处理多个任务。(6)公式明确了对于每一道工序，在同一时刻只能由一台机器进行加工，且仅此一台。(7)和(8)公式描述了车间中每一台机器在调度过程中存在着循环作业和连续操作的特点。(9)公式则规定了所有参数变量必须为正数，确保了模型中的各项数值的有效性和合理性。

3. glvssa求解fjsp

3.1. 编码与解码

3.1.1. 基于极限调度完工时间最小化的机器编码

在zhang [8]的研究成果——全局选择编码方法的基础上，本文采用了进一步改进的climit_min的机器选择优化策略[9]。此策略旨在两个层面提升调度决策质量：一方面通过在工件工序集中随机抽取工序来拓宽机器的选择范围；另一方面对工序如何更优地匹配相应机器的具体步骤进行了改良。这种双层编码机制在后续的matlab仿真验证中证实了其在混合改进麻雀搜索算法(genetic levy sparrow search algorithm, glvssa)，一种改进麻雀算法中的有效性。以一个2 × 5的fjsp问题实例(表1)为例，详细阐述了运用climit_min策略构建的全局机器链编码方案的实际编制情况，见图1，局部和随机编码不再赘述。

table 1. example of 2 × 5 fjsp instance

表1. 2 × 5的fjsp实例

figure 1. diagram of double-layer coding scheme

图1. 双层编码图

3.1.2. 工序编码转换机制

fjsp是一个典型的离散优化问题，而ssa主要用于解决连续优化问题，个体每次更新都须将个体位置转换为工序编码，故本文采用如下方法实现连续解空间中个体位置和离散工序编码转换，其转换步骤为：先将种群个体位置随机编码，将编码中的实数按从大到小排序，只获得其变换位置后的索引，将排序后的索引对应事先排好的工件号，获得与个体位置对应的工序编码。

31.3. 解码方式

解码采用二段插入式解码方式，插入式解码允许数据在被接收和存储的同时进行解码，这使得系统能够实时地处理和理解接收到的信息，同时可以减少整体处理时间，提高系统的运行效率，特别是在处理大量数据或实时性要求高的应用中。分别对机器链和工序链进行解码。

3.2. glvssa

麻雀算法其具体位置更新方式在这里不再赘述，详细公式见文献[10]。

3.2.1. 探索者阶段融入自适应levy飞行

探索者在整个族群起引领作用，在探索者阶段加入自适应加权数，设定随迭代次数增加而自适应变化，算法初期由于优化速度快，设置权值较小，后期加大权值，使得个体移动更快，更好地平衡算法的收敛性，加快收敛速度。在此一定程度上减弱初始化的影响，并减少陷入局部最优的可能性，增强算法的全局搜索能力。

z( i )=0.3cos( π 2 ( 1− i inter max ) ) (11)

此外，为了增强算法解的随机探索能力并促进种群位置分布的多样性，融入levy飞行策略(12) [10]。这一策略的运用能够有效地提升算法整体的搜索效率和问题求解的质量。

levy飞行策略的位置更新公式如下：

x i,j t ′ = x i,j t l⊕levy( w ) (12)

levy飞行的路径轨迹采用mantegna算法(13) [11]对其进行模拟：

f= s | v | 1/γ (13)

σ= { γ( 1 γ )sin( pi∗γ/2 ) γ∗γ[ ( γ 1 )/2 ∗ 2 ( γ 1 )/2 ] } 1/γ (14)

l=0.01( x i,j t − x p ) (15)

式中：levy(w)表示levy飞行的路径，s∈n( 0,σ ) ，v∈n( 0,1 ) ，l是步长控制参数，γ 一般为1.5，⊕ 是表示点对点乘法的算术符号。

探索者位置更新公式如下：

x i,j t 1 ={ z( i )∗ x i,j t ′ ∗exp( − i α∗ inter max ), r 2 <st z( i )∗ x i,j t ′ q∗l, r 2 ≥st (16)

引入levy飞行策略后，麻雀搜索过程中的灵活性得以增强，并有助于引导其他个体发现更优解，不受局部极端的约束。通过将levy飞行机制与自适应权值相结合，优化了搜索方法的均衡性，进而提升了每一代产生的解的质量，这一结合显著增强了算法的全局探索能力。

3.2.2. 跟随者阶段融入鲸鱼螺旋狩猎行为

由文献[4]知，加入者向发现者所占据的最优位置进行跳跃式移动，因此容易导致种群个体在短时间内集群，使算法陷入局部最优。为进一步提高算法的寻优能力，在跟随者阶段引入座头鲸螺旋狩猎行为，其公式见(17) [12]：

y i,j t 1 = d ′ ∗ e bl ∗cos( 2π∗l ) x best (17)

式中：d ′ =| x best − x i,j t | ，b是定义对数螺旋线形状的常量，x best 为当前最优位置，l是[−1, 1]之间的随机量。

座头鲸利用螺旋式上升的动作制造气泡网来捕捉猎物，其螺旋形路径可以帮助算法在局部区域进行精细搜索，通过逐渐减小搜索半径，靠近最优解(猎物)，这样有利于在已发现的较优区域进行深度探索，避免过早陷入局部最优。这样可以在保证麻雀算法寻优能力的同时又保证了种群的多样性，引入鲸鱼优化算法的跟随者位置更新(18)如下：

y i,j t 1 ={ q∗exp( − x worst − x i,j t i 2 ), i> n 2 d ′ ∗ e bl ∗cos( 2π∗l ) x best , 其他 (18)

3.2.3. 警戒者位置更新改进

z i,j t 1 ={ x best β∗ | x i,j t − x best |, f i > f g x best β∗ | x worst − x best |, f i = f g (19)

改进后的公式(19) [6]表示若该麻雀是最优位置的麻雀，它会逃到最优位置和最差位置间的随机位置，否则，它会逃到自己和最优位置之间的随机位置。

3.2.4. 警戒者数量递减策略

警戒者搜索阶段的存在有助于提高算法全局寻优能力。但设置警戒者数量为定值，则不利于算法后期收敛，因此采用警戒者数量递减策略调节警戒者在迭代过程中的数量。警戒者在迭代初期数量多，迭代后期数量减少，整个变化过程在保证了算法全局搜索能力的同时，又提高了算法收敛速度。警戒者数量递减公式(20)如下：

num( t )=round[ ( 1− t num )∗m_d ] 1 (20)

式中，num为当前迭代中警戒者的数量，m_d为初始化警戒者的数量，做一个递减的变换。

3.2.5. 柯西扰动贪婪规则

如果求解的fjsp问题规模很大，每次迭代中对全局最优的麻雀进行柯西扰动[13]，可以提高获得更优解的概率，柯西扰动更新公式(21)如下：

x best ′​′ = x best ∗( 1 cauthy( 0,1 ) ) (21)

式中：x best 为目前全局最有个体，x best ′ 为柯西扰动后的新个体。

柯西变异为连续的分布概率，其逼近零速率较慢，可以产生较大的扰动，提升算法跳出局部最优能力。但上述柯西扰动可以增强算法跃出局部最优的能力，但是无法确定新的位置的适应度值是否优于原来的适应度值，因此引入贪婪规则，比较新旧位置的适应度值，择优选择。

贪婪规则更新公式(22)如下：

x best ={ x best , f x best ≥ f x best ′​′ x best ′​′ , f x best < f x best ′​′ (22)

3.3. 引入遗传算子

3.3.1. 锦标赛选择策略

锦标赛选择是一种用于从当前种群中选择较优个体以繁衍下一代的方法，在结束麻雀算法运行后的区段链中，随机选择三个区段链，并竞赛抉择出适应度值最优的个体加入新的种群。重复上述操作，直到选择出足够数量的个体来组成新的种群。

3.3.2. 混合交叉操作

针对柔性车间调度中的遗传交叉操作，分别基于工序链和机器链采用优先工序交叉(pox)和多点交叉操作，以此对已结束glvssa操作的编码的进一步混合交叉操作，从而提升寻优概率。

(1) 基于工序链的优先工序交叉[14]

以文献[15]的实际调度为例，随机选择两条区段链作为父代p₁、p₂进行交叉操作，并初始化两条空的子代链记为c₁、c₂，针对工序链执行pox交叉操作，具体步骤如下(图2)：

步骤1：将工序随机分为两非空集合v₁、v₂，使得v 1 ∪ v 2 =j ，v 1 ∩ v 2 =∅ 。

步骤2：将p₁中包含在v₁中的工件复制到c₁，p₂中包含在v₂中的工件复制到c₂。

步骤3：互换p₁和p₂的角色，生成c₂。

(2) 基于机器链的多点交叉

通过随机初始化一条和区段链长度一样的二进制串，来决定父代子代在基因串上的继承关系，仍记父代子代为p₁p₂，c₁，c₂，具体操作如下(图3)：

步骤一：随机初始化一条二进制串，长度与区段链相同。

步骤二：若二进制串上编码为0，则子代继承父代基因座上的基因；若二进制串上的编码为1，则c₁继承p₂基因座上对应的基因，c₂继承p₁基因座上对应的基因。

figure 2. diagram of operation chain intersections

图2. 工序链交叉图

figure 3. diagram of machine chain intersections

图3. 机器链交叉图

3.3.3. 智能变异操作

在本文算法中，按照变异率随机选择染色体，对变异算子执行智能变异操作，从负荷最大的机器上随机选择一道工序，执行平衡负载操作，具体操作如下(图4)：

步骤一：在已选择染色体机器负荷最大的机器上随机选择一道工序o_ij；

步骤二：从工序o_ij的候选机器中选择加工时间最少的机器，并将工序o_ij放到该机器上运作。

figure 4. diagram of intelligent mutation operations

图4. 智能变异操作图

3.4. glvssa求解fjsp算法步骤

step1：设置fjsp相关参数，如机器数和工件数等；设置glvssa、ga相关参数，如种群大小，最大迭代次数，警戒者比例，交叉、变异概率等。

step2：以climit_min为基础初始化种群，产生初始区段集。

step3：左移插入式主动解码，计算适应度值，找出最优和最劣的麻雀位置。

step4：根据16更新探索者位置，(18)更新跟随者位置，(19)和(20)更新警戒者位置。

step5：若fjsp规模大于80，对最优个体执行(21)和(22)更新公式

step6：锦标赛选出精英个体。

step7：执行工序链机器链交叉操作及平衡负载变异操作。

step8：判断当前迭代次数是否达到结束条件，若不满足，跳转step3，若满足则进行下一步。

step9：输出最优适应度值和最佳位置，算法结束，详细流程图见下：(图5)。

figure 5. flowchart of the algorithm process

图5. 算法流程图

4. 仿真实验与分析

4.1. fjsp标准算例测试

ssa、gwo、混合灰狼优化算法hgwo [3]和glvssa求解标准算例mk01-mk10 [16]的结果如表2所示。

table 2. comparison of test results between ssa, gwo, hgwo, and glvssa

表2. ssa、gwo、hgwo和glvssa测试结果对比

续表

由表2可知，glvssa在10个标准算例里全部取得相对最优解，最小值和平均值均优于或持平于其它对比算法，对比原始ssa在寻优性能方面取得一个较大的提升。而整体的一个rpd均值则是相较于对比函数里最优的。以上实验分析说明，glvssa在解决fjsp时，能够有效克服求解陷入局部最优的不足，具有良好的寻优性能，证明了改进ssa的有效性。

同时选取混合灰狼优化算法(hgwo)、改进蚁狮优化算法(ialo) [17]、改进多邻域候鸟优化算法(immbo) [18]、改进离散麻雀搜素算法(idssa) [19]等较新群智能优化算法求解mk01-mk10的结果如下表3所示：

table 3. comparison of test results among hgwo, ialo, immbo, idssa, and glvssa

表3. hgwo、ialo、immbo、idssa和glvssa测试结果对比

由表3可知，相比较于其它改进智能算法，除了求解mk05时略差于改进多邻域候鸟优化算法，在求解其它9个算例时的结果均优于其它算法。因此，该改进麻雀算法在求解柔性车间调度问题时具有一定优势。

选出具有代表性的mk02和mk09，其测试结果甘特图和迭代曲线如图6~图9所示：

figure 6. gantt chart of test results for mk04

图6. mk04测试结果甘特图

figure 7. iteration curve for mk04

图7. mk04迭代曲线

figure 8. gantt chart of test results for mk09

图8. mk09测试结果甘特图

figure 9. iteration curve for mk09

图9. mk09迭代曲线

4.2. fjsp实例测试

利用文献[1]和[15]中两个应用实例对glvssa在实际应用中的寻优性能进行检验。将ssa、glvssa及其它参数统一设置，设置种群规模为200，最大迭代次数为150，算法独立运行30次，得到如表4和表5所示结果(表中δmin和δavg的含义分别为最优值提升率和平均值提升率)，同时得出其对应甘特图和迭代曲线图，见图10~图13。

table 4. examples of 6 × 6 instances

表4. 6 × 6实例

table 5. examples of 6 × 8 instances

表5. 6 × 8实例

figure 10. gantt chart for 6 × 6 instances

图10. 6 × 6实例测试结果甘特图

figure 11. gantt chart for 6 × 8 instances

图11. 6 × 8实例测试结果甘特图

figure 12. iteration curves for 6 × 6 instances

图12. 6 × 6实例迭代曲线对比

figure 13. iteration curves for 6 × 8 instances

图13. 6 × 8实例迭代曲线

由上述两表(表4、表5)可知，求解6 × 6作业车间调度问题时，glvssa取得的最优时间为9，相对于ce-mofjsp、ga、hgba和ssa的最小值提升率分别为18.2%、18.2%、10.0%和18.2%，平均值对ga、hgba和ssa提升率分别为14.0%、7.5%和17.6%。由表5可知，求解6 × 8作业车间调度问题时，glvssa取得的最优时间为54，相对于itlpso、ga、hgba和ssa的最小值提升率分别为11.7%、7.0%、3.6%和5.4%，平均值提升率分别为18.0%、10.2%、2.5%和12.4%。以上结果表明，相较于对比算法，glvssa在求解fjsp时寻优精度和稳定性更好。

5. 结论

针对柔性车间调度问题，提出了基于climit_min初始化，结合levy飞行策略、自适应参数调整、鲸鱼优化算法、数量递减策略及柯西扰动改进的麻雀搜索算法，再混入遗传算子，能够有效地避免陷入局部最优解，提高了算法的全局搜索能力，可以解决fjsp这类较复杂的离散型组合优化问题。同时，在mk系列的10个标准算例以及2个实例的测试结果中表明，混合改进麻雀算法在寻优能力具有较好的综合性能。证明了改进后的混合麻雀算法显著提高了搜索能力和跳出局部最优的能力，与传统麻雀搜索算法相比，能够更好更快地收敛至更优解，优化了生产调度的效率和效果，为解决柔性车间调度问题提供了一个高效、稳定且适应性强的方法。伴随工业4.0和智能制造的发展，未来的麻雀算法将有可能结合实时数据采集和处理技术，实现在动态、不确定环境下车间调度问题的实时优化，增强工厂对突发情况的快速响应能力。随着算法本身的不断发展和完善，相信将在解决实际生产调度问题上发挥更大作用。

基金项目

国家自然科学基金项目(编号72071130)。

notes

^*通讯作者。

参考文献