改进离散型飞蛾扑火优化算法求解柔性作业车间调度问题

陶婷婷，宋豫川，王建成，郭伟飞

（重庆大学机械传动国家重点实验室，重庆400044）

0 引 言

生产调度是提高制造企业运作效率和服务质量的关键环节，其中作业车间调度问题最为典型，而柔性作业车间调度问题[1]（flexible job shop scheduling，FJSP）是作业车间调度问题的拓展，在工序排序的问题中引入机器选择问题，增加了问题的复杂程度，给其求解带来更大的困难和挑战。

FJSP 问题的求解方法可以分为两大类，精确算法和近似算法。精确算法包括分支定界法、整数规划法和拉格朗日松弛法等。Tamaki[2]建立了FJSP 的混合整数规划模型，并采用枚举法进行FJSP 问题的求解；Rochanaei[3]提出了两种新型的混合整数线性规划模型对FJSP 问题进行求解。精确算法虽然理论上能够求得最优解，但需要消耗大量时间，因此只适用于小规模FJSP 问题。近似算法包括启发式算法和元启发式算法。元启发式算法因能在合理的时间内求得各类不同规模FJSP 问题的优良解而成为目前FJSP 问题求解的主流方法，其中以智能仿生算法为典型代表。进化算法是一类代表性的智能仿生算法，包括遗传算法、进化策略和进化规则。陈成等[4]提出了一种遗传——蚁群算法，它分别采用遗传算法和蚁群算法解决机器分配和工序排序问题。Kacem 等[5]首先利用局部搜索方法求解机器分配问题，再利用基于分配模型的遗传算法求解工序排序问题，最终实现对多目标FJSP 问题的求解。Tay 等[6]设计一种基于遗传规划的组合调度规则生成框架，利用生成的组合调度规则整体解决多目标FJSP问题。赵诗奎等[7]通过对不同解码方式的分析，设计了一种基于空闲时间的邻域搜索方法，并与遗传算法相融入进而整体求解FJSP 问题。庞哈利等[8]从集成化的角度建立了FJSP 问题两层混合整数规划模型，并提出门槛接受、遗传算法与启发式规则相结合的混合求解算法。群体智能算法是另一类代表性的智能仿生算法，包括蚁群优化算法、粒子群优化算法和人工蜂群算法等。夏蔚军等[9]提出一种混合微粒群优化算法求解多目标FJSP 问题，微粒群优化用于向各机器分配工序, 模拟退火用于排序各机器上的工序并对排序结果进行评价。张静等[10]提出一种新的粒子位置更新方式，能实现粒子群算法直接在离散域执行，并引入改进的模拟退火算法来增强算法的邻域搜索能力，使之能更有效地从整体上求解批量FJSP 问题。仲于江等[11]提出一种将小生境技术和粒子群算法相结合整体求多目标的FJSP 优化问题最优解的优化方法。王凌等[12]提出一种结合关键路径的人工蜂群算法用于整体求解FJSP 问题。姜天华[13]将基本的灰狼优化算法进行改进，并结合局部搜索形成混合灰狼优化算法，整体求解包含绿色性指标的多目标的FJSP 问题。

综上所述，目前求解FJSP 问题主要包含分步法和集成法。虽然分步法降低了问题求解的难度，然而它割裂了两个子问题间的复杂耦合关系，因此往往导致算法的求解质量不高，进而目前围绕FJSP 问题求解方法的研究主要集中在集成法。

近些年来，受自然界中各种现象和生物行为的启发，各种新型的智能仿生算法被提出，并被用来求解各种复杂组合优化问题。飞蛾扑火优化算法（moth-flame optimization，MFO）就是其中一种比较新型的智能仿生算法，它模拟了飞蛾夜间飞行时采用的横向定位导航机制，该定位导航机制能维持飞蛾自身相对月亮的固定角度飞行，然而由于受人工和自然点光源的影响，加之与月亮和干扰光的距离不同，导致直线飞行失效，最终呈现近似螺旋的飞行路径。基于上述特性，Seyedali Mirjalili 等[14]于2015年提出了基础的MFO 算法。MFO 算法因具有并行优化能力强、全局性优且跳出局部极值的特点，而被广泛应用于网络入侵检测[15]、电力系统潮流计算[16]、网络规划[17]、图像检测[18]、经济调度[19]、神经网络训练[20]等领域，然而目前仍未见其在生产调度领域的应用。因此，本文尝试对飞蛾扑火优化算法进行改进，使其能适用于柔性作业车间调度问题，为此设计出两段式编码转化机制、新颖的随机更新算子及基于Levy 飞行轨迹的随机游走策略，通过测试标准算例和对比其他算法求解结果，验证本文算法的有效性与优越性，同时为MFO 算法在类似问题上的应用提供了参考。

1 柔性作业车间调度问题

1.1 问题描述

FJSP问题可描述为：有n个待加工工件和m个机器，每个工件的工序数为nini≥1（ ），每道工序可以在多台机器上进行加工，且每个工序在每台可加工的机器上的加工时间已知。FJSP需要解决两个问题：机器选择和工序排序。机器选择是需要为每道工序确定其加工机器，工序排序是需要为在同一个机器上加工的工序确定其加工的先后顺序。本文的优化目标是最大完工时间最小。此外，它往往满足以下假设条件：1）所有工件和机器在零时刻均处于就绪状态；2）同一时刻一个机器最多只可加工一个工件；3）不允许抢占情况发生，即工件加工过程不可中断；4）同一个工件的工序之间具有优先级关系，而不同工件的工序之间相互独立；5）各工件加工优先级相同；6）忽略工序加工前机器所需的准备时间。

1.2 模型建立

为便于模型建立，定义各符号如下：Ci为工件i的完工时间；n为工件数量；m为机器数量；ni为工件i的工序数；Oij为工件i的第j道工序；Mij为工序Oij的加工机器集；mij为工序Oij的可加工机器数；xijk为工序Oij在机器k上进行加工；tijk为工序Oij在机器k上的加工时间；stijk为工序Oij在机器k上加工的开始时间；etijk为工序Oij在机器k上加工的结束时间；Cmax为整个加工过程的完工时间。

其中：式（1）为目标函数；式（2）为工艺约束；式（3）为机器约束，一个工序只能在一个机器上加工；式（4）也为机器约束，一个机器在同一个时刻最多只能加工一道工序；R为一充分大的正数。

2 基本飞蛾扑火优化算法

基本MFO算法采用了基于火焰种群的位置更新机制。火焰种群代表飞蛾种群的优良个体，按照优良个体的适应度值大小排序生成，然后将火焰种群的位置向量作为参考更新飞蛾种群的位置，在更新过程中，飞蛾种群的个体与火焰种群的个体一一对应进行位置的更新。由于对优良个体的完全保留，火焰种群极易陷入局部最优位置。为了平衡全局搜索和局部开发能力，MFO算法设定火焰种群的数量随着迭代的进行线性减少，到最后只剩下最优的个体。在飞蛾种群位置更新时，超过火焰种群数量的飞蛾个体围绕最差的火焰个体进行位置更新。飞蛾位置更新的公式如下所示：

式中：t为当前迭代次数；Mi为飞蛾个体；Fj为火焰个体；S为飞蛾围绕火焰的飞行机制；Di为飞蛾与火焰之间的绝对距离；a为[r,1]之间的随机向量，其大小表示飞蛾接近火焰的程度（a=-1表示最接近，a=1表示最远离）；r为收敛常数，在算法迭代过程中，r是从-1线性递减到-2；b为螺旋方程参数。

具体的基本MFO算法的步骤可参考文献[14]。

3 改进离散型飞蛾扑火优化算法

3.1 两段式编码

FJSP包含机器选择和工序排序两个问题，为了采用集成法的求解思路对问题进行求解，所以采用两段式编码方法。两部分编码的长度均为工序的总数目，假设工序总数目为l，则编码的总长度为2l。假设编码方案为P=｛p1,p2,…,pl,pl+1,pl+2,…,p2l｝，则pi的取值范围为［-δ,δ］内的实数值，一般δ取1。若有2个工件，3个机器，每个工件有3道工序，每道工序的可加工机器和加工时间如表1所示，表中数字表示工序在对应机器上的加工时间，“-”表示工序不能在对应机器上加工。则一条两段式编码的染色体如图1所示。

表1 示例数据

图1 示例编码

3.2 编码转换机制

由于基本MFO算法最初设计是为了解决连续优化问题而提出的，而FJSP问题为离散型的组合优化问题，为了适应FJSP问题的特性，还需要对上述两段式编码的染色体进行变换，建立起染色体连续空间与问题离散决策空间的映射关系。由于机器选择和工序排序的约束及要求不同，故需要分别采取不同的转换机制，同时，由于进化机制的原因，染色体部分位置的连续实数值可能会超出范围，因此也需要设计相应的调整机制。

3.2.1 机器选择转换方法

本文设计的机器选择转换方法具体操作步骤如下：1）按照公式（9）将每个位置的连续编码转化为对应工序的机器集序号；2）将编（序）号映射为对应的机器集中的机器号。根据上述转换方法则可获得所有工件的每道工序的加工机器，即工序的机器选择方案：式中：m(i)为第i个位置的实数值编码；z(i)为第i个位置对应工序的可加工机器集中的机器数量；round为四舍五入函数，保证转化后的每个序号均为正整数。

图1中所示染色体对应的机器选择转换过程如图2所示。其中，机器编码按照工件编号和工序的顺序约束顺序排列，第一个位置为工件1的第一道工序O11，第二个位置为O12，依次为O13、O21、O22、O23。准换后的编码分别为1、1、0、0、1、0，则O11选择加工机器集中的第二个机器，即机器2，O12选择第二个机器，为机器3，O13选择第一个机器，为机器1，O21选择第一个机器，为机器1，O22选择机器2，O23选择机器1。

3.2.2 工序排序转换方法

图2 机器选择编码

本文设计的工序排序转换方法具体操作步骤如下：1）将工序编码中的每个元素从左到右按照顺序分配一个固定ID；2）按照从大到小的顺序将各元素重新排列，并将之前分配的ID放到其对应元素的位置，形成一个新的排列；3）根据排列结果构造出工序的排序方案。以图1中的编码为例，其工序编码为0.34、0.26、-0.21、0.75、-0.54、0.88，则其每个位置对应的ID为1、2、3、4、5、6，再按照LPV规则排序，得到新的排列为0.88、0.75、0.34、0.26、-0.21、-0.54，则其ID映射为6、4、1、2、3、5，由于工件1有3道工序，则ID在1～3的元素为工件1的工序，ID在4～6的元素为工件2的工序，形成的工序排序方案为2、2、1、1、1、2，转化为调 度 方 案O21、O22、O11、O12、O13、O23。具体的转换过程如图3所示。

3.2.3 调整规则

按照MFO算法中飞蛾个体的螺旋飞行机制，两段式编码染色体位置元素更新后可能出现位置的值超出范围，因此，需要设计相应的调整规则。本文采用的调整规则为：

图3 工序排序编码

3.3 主动式解码

目前针对作业车间调度问题的解码方式主要有两种，分别为半主动解码和主动解码。业已证明，以最大完工时间为优化目标时，最优解必在主动调度集中[21]。本文采用一种基于贪婪解码[22]的主动解码方法。它首先根据通过机器选择转化机制获得的工序机器选择方案来确定每道工序的加工机器及相应的加工时间，然后按照通过工序排序转化机制获得的工序排序方案确定工序加工顺序，依次进行解码，在不推迟其他已安排工序开工时间的条件下，将工序插入到对应机器上最早可行的时刻加工[23]。

3.4 种群初始化

在FJSP问题中，机器的选择对于个体的质量非常重要，若在生成初始解的考虑选择加工时间较短或者使机床负荷比较均衡的策略，则可以提高初始解的质量，进而提高算法的求解效率。因此，在随机生成50%个体的基础上，本文引入两种初始解生成方案：局部选择和全局选择。其中，局部选择是指为每道工序选择加工时间最短的机器，30%个体由此方式产生；全局选择是指随机选择工序，使得工序选择完成后，根据工序选择对应机床，使得每个机床的加工时间波动最小，其整体负荷尽量均衡，剩下的20%个体由全局选择生成。

3.5 随机更新算子

在基本的MFO中，飞蛾种群作为搜索的主体，在更新过程中，与火焰种群数量相当的飞蛾个体按照顺序围绕着飞蛾个体进行一一更新，超出火焰种群数量的飞蛾个体围绕着最差的火焰个体进行螺旋飞行，这样导致在后期由于火焰个体数量的减少，最差的火焰与最优的火焰个体相差较小，使得整个飞蛾种群丧失多样性，算法易陷入局部最优解。因此，本文设计了一种随机更新算子。它将实现在整个飞蛾种群围绕火焰种群更新的过程中，将原来的顺序更新变为随机选择更新，即按照顺序选择飞蛾个体围绕随机选择的火焰个体进行螺旋飞行，实现对飞蛾位置的更新，达到跳出局部最优解的目的。

3.6 Levy飞行策略

Levy飞行策略是一种由法国数学家Paul Pierre Levy提出的重尾分布的随机游走策略，它模仿动物在搜寻食物过程中的一种具有Markov链特征的随机行走方式，在行走路径的形成过程中，下一步的移动方向基于当前的状态和状态转移概率。大量的研究已证明许多动物和昆虫都具有这种典型的Levy飞行特征，能够显著地提高种群的多样性，提高算法的全局搜索能力。Levy大多用于连续优化问题中，还未见有在FJSP问题上的应用。因此，本文尝试将Levy策略引入到IDMFO中，探究此策略在FJSP问题中的适用性。

根据上文的介绍可知，随着火焰种群线性减少，在迭代后期，火焰数量也随着减少，种群存在容易丧失多样性而陷入局部最优解的风险，所以考虑引入Levy飞行策略来增强算法的寻优能力。

其中：Mti为当代的飞蛾个体；Mt+1i为Levy飞行后的新的飞蛾个体；Fbest为最优的火焰个体；c为[0,1]内的随机数；F为标准的伽马函数；βi∈(0,2］。

3.7 IDMFO算法步骤

步骤1：设置算法参数，根据种群初始化方法生成初始种群。步骤2：评价种群的适应度值，选出火焰种群。步骤3：根据式（5）～式（8）更新飞蛾种群的位置向量、火焰种群的数量及螺旋参数。步骤4：根据式（11）～式（14）产生新的飞蛾种群。步骤5：评价新的种群，更新火焰种群。步骤6：判断算法是否满足终止条件，若是，则转到步骤6，否则转到步骤3。步骤7：终止算法并输出结果。整个IDMFO算法的流程如图4所示。

图4 IDMFO算法流程图

4 实验分析

实验运行环境为Intel Core i3-8100 CPU 3.6 GHz，RAM 8.00 GB，Windows10，64 位 操 作 系 统 和Pycharm 2018.2.4。为了测试算法的性能，采用FJSP国际标准算例中Kacem8×8，10×10，15×10算例[23]和Brandimare[25]算例Mk01-10进行试验，各算法对每个算例独立运行求解10次，获得解的情况如表2所示，其中MFO表示基本MFO算法，MFO1表示结合种群初始化方法的MFO算法，MFO2为结合种群初始化方法和随机更新算子的MFO算法，IDMFO为本文改进离散MFO算法，加粗结果表示上述4种算法求得问题的最优解。上述算法中相关参数取值如下：种群规模为100，最大迭代次数为300，螺旋参数为1，收敛常数为-1。

表2 算法求解结果

从表2中数据可以看出，IDMFO在所有算例上均取得最佳的结果，最优解的平均值也明显优于其他的几种MFO算法，在算法运行时间上，与其他算法相比无太大的差别。因此，本实验验证了本文所提算法能在保证时间效率的同时，又能够提高算法的全局搜索能力，有效避免陷入局部最优解。此外，相比于未采用Levy策略的MFO算法，融入Levy策略的MFO算法明显具有更强的求解能力，验证了引入Levy策略确实能够起到增强算法全局搜索能力的效果，扩展了Levy策略的应用领域。

为了进一步证明本文算法的求解效果，与文献［26］～［28］中算法的求解结果进行对比，如表3所示，其中加粗结果表示所有算法求得问题的最优解。

表3 算例求解结果的对比

从表3数据中可以看出，在上述13个标准算例中，IDMFO算法分别能在Kacem02、Mk01、Mk03、Mk04、Mk07、Mk08和MK10的7个算例上都获得了最优解，尤其是在Mk04、Mk07和Mk10上能获得唯一的最优解，其中求得Mk07的最优结果甘特图如图5所示。相较而言，文献［26］、［27］和［28］中算法获得最优解算例的个数分别为3、5和5，因此，本文算法在求解柔性作业车间调度问题的有效性与优越性得以进一步验证。

图5 IDMFO求解Mk07的最优结果甘特图

5 结 论

本文将飞蛾扑火优化算法用于柔性作业车间调度问题中，针对该问题的离散特性，设计出一种两段式编码转化机制，建立了染色体连续空间与问题离散决策空间的映射关系；同时，采用随机、局部选择和全局选择相结合的初始化方法来提高初始解的质量及种群的多样性；在算法运行过程中，设计了随机更新算子和Levy随机游走策略来加强算法的全局搜索能力，使其跳出局部最优解。最后，采用标准算例进行仿真试验，并与其他文献中算法求解结果进行对比，有力地验证了本文所提算法的有效性与优越性。

在后续的研究过程中，可以将IDMFO算法与其他局部搜索算法结合形成混合算法，或者与其他群体智能优化算法结合形成协同进化机制，进一步提高算法搜索能力。此外，可以将多目标优化方法与IDMFO算法进行有效结合形成多目标飞蛾扑火优化算法，求解更加复杂的多目标组合优化问题。