基于改进原子轨道搜索算法的多工艺路线柔性作业车间问题研究

李佳蓉，晁永生，李纯艳，袁逸萍

（新疆大学智能制造现代产业学院，新疆乌鲁木齐 830017）

0 前言

在“中国制造2025” 的背景下，我国制造产业的生产模式正逐步由大批量单一产品向多品种、小批量定制化产品方向转变。定制化产品在生产过程中，由于其结构复杂、多变等原因，通常有多条不同的生产加工路线。同时，日益多样化的订单需求，迫使制造单元更具柔性。

在传统作业车间问题中，各工件的工序、加工机器以及对应的加工时间是固定的，而柔性作业车间问题（Flexible Job Shop Problem，FJSP）是在作业车间问题的基础上兼顾考虑工件各工序机器选择的不确定以及机器加工不同工序的时间不确定，这更符合实际生产的情况。

近年来，FJSP 已被国内外诸多学者广泛研究，如，在模型搭建和求解方面，JALILVAND-NEJAD、FATTAHI［1］基于加工循环下的FJSP 问题提出一种混合整数线性规划模型，并采用遗传算法进行求解验证。WU 等［2］研究了考虑夹具装卸时间的双资源约束FJSP 并建立了数学模型。VITAL-SOTO 等［3］建立了具有排序灵活性的FJSP 的数学模型，并提出一种混合细菌觅食优化算法求解该问题。PENG 等［4］构建了以加工时间、能耗和噪声为优化目标的双约束多目标的FJSP 模型，并提出一种混合离散多目标帝国竞争算法来进行求解。NOURI 等［5］提出一种基于混合元启发式算法的聚类整体多智能体方法来求解FJSP。张宇嘉、宋威［6］以完工时间最优为目标，采用构建精英档案和进步档案的方法，提出一种双档案粒子群算法对FJSP 进行求解。虽然他们从模型和求解方法上对FJSP 进行了深入研究，但目前绝大多数的研究只考虑了工件的单个工艺方案，即工件的每道工序只考虑机器的可替代性。而在实际生产过程中工件可以有多条工艺路线，前人对考虑多工艺路线FJSP 的研究相当有限。

在柔性作业车间的综合调度过程中，往往忽略多工艺路线这一关键因素，造成设备利用率较低、零件在某一机器堆积、单件产品加工时间过长等问题。因此，将多工艺路线下的柔性作业车间调度应用于产品制造对提高企业综合竞争能力尤为重要。同时，由于加入多约束，模型在求解时的搜索空间范围增大，一般算法容易在求解过程中陷入局部最优，导致搜索鲁棒性差、效率低下。因此，本文作者建立一种多工艺路线柔性作业车间问题（Multiprocess Route Flexible Job Shop Problem，MRFJSP）模型，并提出一种改进原子轨道搜索（Improved Atomic Orbital Search，IAOS）算法，用于避免模型求解过程中效率低下的问题。

1 多工艺路线柔性作业车间调度问题

1.1 问题描述

MRFJSP 模型作为企业在生产过程中为各工件选择合理加工路线、工序排序和机器分配，以实现调度目标的有效手段，可描述如下：有多个工件需要加工，每个工件的加工特征不同，不同特征可由多种加工方式实现，不同的加工方式可组合出多条加工路线，各路线包含的工序数不同，各工序可选的机器柔性，各机器加工同道工序的时间不同。由于在生产调度过程中会出现一种产品可按照不同工艺路线进行加工、一台机器同一时刻只能加工一件产品等情况，为明确MRFJSP 模型中的约束关系，做出如下假设：

（1）零件可选择不同工艺路线且不同工艺路线下的工序之间不存在优先级关系；

（2）禁止关闭闲置机器且不考虑机器故障；

（3）工序一旦开始就不允许中断；

（4）零件的一道工序完成后即可到达加工的下一个机器。

文中模型相关参数及其含义见表1。

表1 相关参数及其含义Tab.1 Relevant parameters and their meanings

1.2 问题模型搭建

为提高多工艺路线柔性作业车间效率，以完工时间最小为调度优化目标函数，表示为式（1）：

根据基准先行、先主后次、先面后孔的工艺规则，在保证有效和完整的前提下满足以下约束：

（1）工艺路线约束。每个工件每次只能选择一条工艺路线，表示为式（2）：

（2）机器选择约束。各工序只允许被一台机器进行加工，表示为式（3）：

（3）机器约束。在任意时刻每台机器只能加工一道工序，表示为式（4）：

（4）先序关系约束。各工件的不同工序不允许同时加工，表示为式（5）：

（5）工件加工时间约束。加工工件的完成时间非负，表示为式（6）：

（6）工序时间约束。工序的开始时间均不大于工序的完工时间，表示为式（7）：

（7）加工路线决策变量约束。工件在第l条加工路线被选中，表示为式（8）：

（8）机器决策变量约束。工件的第l条路线的第j道工序是否在机床k上加工，表示为式（9）：

2 改进原子轨道搜索算法

原子轨道搜索（Atomic Orbital Search，AOS）算法是由AZIZI［7］在2021 年提出的一种高效的元启发式算法，其设计源于量子力学原理和量子原子模型。AZIZI 等［8］结合AOS 研究了多个领域著名工程问题，验证了AOS 适用于求解不同规模组合优化问题，具有较优的鲁棒性、群体性。但考虑加入加工路线柔性和机器柔性等约束，问题的复杂性指数式增长，搜索空间急速扩大，此时若使用AOS 进行求解，反而会降低算法的搜索效率，影响全局最优值的获得，因而本文作者提出一种改进原子轨道搜索（Improved Atomic Orbital Search，IAOS）算法。

2.1 原子轨道搜索算法基本原理

AOS 算法通过效仿原子核外部电子密度变化、电子能量状态以及受各类因素干扰电子发生跃迁，从电子的选择、搜索和更新这3 个方面建立数学模型，模拟算法的寻优过程［7］。

AOS 将原子核外的电子云模拟成薄的、同心的层作为算法的搜索空间，如图1 所示。电子层表示为Xk，k表示电子层数。搜索空间中的电子用候选解Xi表示，候选解为电子在原子轨道模型中的映射，Xi的位置用一组决策变量［，，…，］表示，电子层Xk中的一组候选解如式（10）所示。候选解在搜索空间中的层数是由电子的概率密度确定的，在数学模型中使用概率密度函数进行确定。

图1 电子跃迁示意Fig.1 Electron transition schematics

候选解在搜索空间中的初始位置由式（11）随机确定，候选解的能量值表示为，即函数值。在求解最小化优化问题时，将候选解的能量值升序排序，能量值越小，候选解的概率密度值越高，以代表具有较低能量值的电子。

其中：i表示电子层中的第i个候选解，i∈｛1，2，…，m｝；d表示维度，j∈｛1，2，…，d｝。

候选解进行位置更新时需考虑光或其他影响因素，如粒子、磁场等对电子的作用。电子受这些因素影响时会从基态跃迁至激发态，离开所在电子层，电子位置随之变化，即候选解位置发生更新。候选解位置更新的方式如下：

（1）当光对电子产生作用（ϕ≥PR）时：

①当电子吸收光子时（≥BE），电子能量升高，电子从低能级向高能级跃迁，电子位置更新，即候选解位置更新，可用式（12）表示：

②当电子发射光子时（＜BE），电子能量降低，电子从高能级向低能级跃迁，电子位置更新，即候选解位置更新，可用式（13）表示：

（2）除了受光子的影响外，电子的能量还受其他因素作用（ϕ＜PR），此时电子位置也会更新，可用式（14）表示：

其中：ϕ表示电子受影响的概率；PR表示光对电子作用的概率；分别表示更新前、后的候选解位置；LE表示所在层最低能量的电子位置；BS表示候选解所对应的结合态，用平均候选解位置向量表示；BE表示候选解所在层所对应的结合能，用层最低能量表示；ri表示一个随机生成的电子位置；αi、βi和γi均为随机数。

2.2 改进算法的编码与解码

基于建立的MRFJSP 模型，将候选解位置向量设为三段式向量，三段向量分别对应路线选择、工序排序与机器分配。候选解位置向量维度d＝N＋2G，第一段向量长度为N，第二段、第三段向量长度均为G，N为工件数，G为加工所有工件的总工序数。候选解位置向量中各元素值均使用随机函数均匀生成实现全局初始化，候选解位置向量中各元素取值范围均为［-ε，ε］，ε＝N。

假设有一个MRFJSP，问题中有2 个工件，每个工件分别有2 条加工路线，每个工件的1、2 条路线分别有2、3 道工序。该问题的候选解由3 段向量构成，第一段向量长为2，后两段的长度需根据第一段向量中的信息进行计算。若候选解第一段随机位置向量为［1.8，-1.4］，则通过编码操作得到第一段向量为［2，1］，即工件1 选择路线2，工件2 选择路线1。此时可知该加工任务的总工序数为5，则该候选解位置向量总长为12，图2 为满足第一段位置向量［1.8，-1.4］的一个候选解。

图2 候选解位置向量Fig.2 Candidate solution position vector

2.2.1 编码

候选解位置向量的编码包含路线选择、工序排序和机器分配3 个部分。对第一段路线选择位置向量进行编码时，编码的长度对应总工件数，向量中的每个位置依次与工件号对应。根据各工件的可选路线数将候选解位置元素的取值范围［-ε，ε］均匀分区，判断候选解位置元素值所属的分区，得到候选解位置元素对应的路线。以图2 为例，候选解位置元素的取值范围是［-2，2］，工件1 的可选路线两条，将范围均匀分区为［-2，0）和［0，2］，判断元素所属区间，则工件1 选择路线2，工件2 选择路线1。完成路线选择位置向量的编码、获得总工序数后，采用最大位置规则对工序排序位置向量进行编码［9］，首先对工序排序位置向量进行降序排序，再依照所得的排序位置对工序顺序进行重排列，得到编码结果。编码转换过程如图3所示。

图3 工序排序位置向量编码过程Fig.3 Process sorting position vector encoding process

完成前两段编码后才可开始第三段机器分配位置向量编码。在该编码过程中需考虑候选解位置元素与对应工件的可选机器之间的关系。文中采用文献［10］的编码方式，如公式（15），它将候选解位置向量映射到对应可选机器的机器序号，实现机器分配编码，即公式对应计算出的值就是选择的机器号，当计算的机器号不存在时，设置该机器号为1。

其中：为机器分配编码；为候选解位置元素；s（d）为可选择的机器集合；ε为总工件数。

由式（15）可对机器分配位置向量进行编码，编码的转换过程如图4 所示。

图4 机器分配位置向量编码过程Fig.4 Machine allocation position vector encoding process

2.2.2 解码

解码也包含路线选择、工序排序和机器分配3 个部分。第一段路线选择解码需根据各工件的可选路线数将候选解位置元素的取值范围［-ε，ε］均匀分区，判断候选解编码元素值所属的分区范围，在该范围内随机取值，从而实现路线选择解码。

完成第一段解码后采用最大位置规则中的转换公式（16），获得第二段工序排序位置向量对应的解码向量［9］，然后将原工序排序位置向量进行升序排序，根据升序排序后的位置值对解码向量重新排序，最终完成工序排序位置向量解码。

完成第二段解码后对第三段机器分配向量解码，该解码过程相当于机器分配编码过程的逆转换，转换公式如式（17）所示，通过该公式可直接计算出对应的机器分配位置向量。若计算时出现可选机器数为1，则随机生成该位置的解码元素。

2.2.3 候选解位置向量的增码与减码

求解时候选解位置向量元素值会随位置更新变化，当路线选择位置向量中的某个元素值改变时，可能会导致工件加工路线变化，任务的总工序数随之变化，候选解维度改变。当总工序数变化时，原始编码长度将不符合编码规则，无法求解，所以在解码时要考虑候选解位置向量的增码与减码。

增码与减码的操作方法为：每次编码前测量候选解原始维度对应的工序总数以及候选解路线选择段对应的实际工序总数。若原始工序总数小于实际工序总数，则进行补码，补码数为实际工序总数与原始工序总数之差，使用随机函数生成相应数量的位置元素补码。反之，采用位置向量末端减码，减码数为实际工序总数与原始工序总数之差。

2.3 自体交叉

在作业车间调度方案中，由于工序在不同机器上的排布顺序不同，完成加工任务的时间也不同，所以工件在机器上的排布往往有较多空闲时间，造成时间上的浪费。因此可以调整工序在机器上的排布，实现完工时间的优化。

自体交叉的操作过程如图5 所示。自体交叉操作通过选取候选解单个个体工序排序段上的两个随机位置进行元素值互换，搜索排布中的空闲时间进行插补，缩短完工时间。

图5 候选解自体交叉过程Fig.5 Candidate solution self-crossover process

2.4 变邻域变异

作业车间调度问题中的邻域结构直接影响局部最优解、全局最优解的获得。变邻域搜索不但能避免大量无效搜索过程，还能扩展当前的搜索空间，避免陷入局部最优，所以对MRFJSP 采用变邻域搜索方法对候选解进行变异搜索。根据变邻域搜索方法中邻域范围特性（范围介于［2，4］时搜索效率和稳定性较好，范围上限超过5 时搜索效率逐渐降低）［11］，结合问题需要，合理设置邻域范围为［2，4］。

变邻域变异的操作过程。先判断候选解是否发生变邻域变异；若发生变异，在邻域范围内随机搜索得到一组工件位置；对工件位置数据全排列获得多个可行候选解；计算出这些候选解的能量值再与原候选解进行比较；将最优候选解作为变邻域变异后的新候选解。变邻域变异的操作过程如图6所示。

图6 候选解变邻域变异过程Fig.6 Candidate solution variation neighborhood mutation process

2.5 变工序数候选解精英保留策略

由于MRFJSP 中各工件有多条加工路线且生成的候选解维度不同，需考虑维度变化对搜索空间的影响，简单地保留能量值较优的个体是不合理的。为保证子代搜索空间中候选解的多样性以及避免算法陷入局部搜索空间，提出一种变工序数候选解精英保留策略。在算法生成初始候选解时对候选解标记维度，在候选解进行位置更新、自体交叉和变邻域变异时更新维度标签，完成每次迭代时保留能量值较优的候选解和各维度标签中最优候选解，作为下一次迭代的初始搜索空间。

2.6 算法流程

具体算法流程如图7 所示。

图7 改进原子轨道搜索算法流程Fig.7 Improved atomic orbital search algorithm process

改进原子轨道搜索算法首先对候选解位置进行初始化并计算能量值，然后确定当前原子的结合态、结合能及最低能级，并使用概率密度函数分配候选解到各虚拟层，计算虚拟层的结合态、结合能及层能级，更新对应层候选解位置，使用自体交叉、变邻域变异策略进行增强搜索，通过变工序数精英保留策略保留最优个体，重复上述过程直至满足结束条件。

3 案例验证与分析

本文作者在Windows 10、CPU 2.40 GHz、内存8 GB 的系统上采用MATLAB 2020b 编程实现IAOS 算法运行。IAOS 算法参数设置为：迭代次数为300，候选解个数为200，原子轨道数为5；光子对电子的作用率0.1；交叉概率0.8；变异概率0.2。

为能够合理验证前期建立的MRFJSP 模型，选取3 种规模的实例数据验证，以文献［12］中某内燃机车柔性生产作业车间的部分数据作为基础数据［13］。这3 组 数据 分别 对应3、6、10 工 件在小、中、大规模问题上的加工任务且工艺路线可选。其中六工件六机器中规模问题的工艺路线信息如表2所示。

表2 中规模问题的工艺路线信息Tab.2 Process route information for medium scale problems

表中Ril和Oij分别表示工件的可选工艺路线和工序，i（i＝1，2，…，6）表示工件号，l（l＝1，2，…，6）表示路线号，j（j＝1，2，…，6）表示工序号。表2 中工序Oij对应的可选机器和加工时间如表3 所示。

表3 表2 中工序Oij对应的加工信息Tab.3 Processing information corresponding to process Oij in Tab.2

3.1 模型求解

在FJSP 中各工件的加工路线固定、机器选择柔性，无需考虑多个加工路线。在MRFJSP 中需要考虑加工路线柔性和机器选择柔性，两个模型的求解目标均为完工时间最小化。为避免随机性，采用3 种不同规模问题对FJSP 模型和MRFJSP 模型进行测试，各运行10 次。中规模问题中FJSP 模型选择各工件的原始车间加工路线进行求解，即参照表2 中的Ri1所对应的6 条加工路线，其中i＝1，2，…，6。

经典FJSP 模型和MRFJSP 模型对3 种不同规模问题数据对进行求解，解得的最优调度结果如表4 所示，tbest、tavg和t分别表示最优完工时间、平均完工时间和算法求解的平均运行时间。两模型中规模问题调度甘特图如图8、9 所示。

图8 FJSP 中规模问题的最优调度甘特图Fig.8 The optimal scheduling Gantt chart for scale problems in FJSP

表4 模型对比实验结果Tab.4 Model comparison test results

3.2 求解结果对比分析

由表4 中两模型实验结果可看出，对于不同规模问题MRFJSP 模型求解得到的完工时间总体小于FJSP 模型。从小、中、大3 个规模问题上进行分析，使用MRFJSP 模型相较于FJSP 模型在完工时间上分别缩短了25.95%、25.6%和29.53%。对比图8 和图9 所示的最优调度方案甘特图可看出MRFJSP 模型的调度方案相较于FJSP 模型的排程时间更紧凑，排布更合理。结合实验结果和甘特图综合分析验证了MRFJSP 模型求解方法能有效求解多工艺路线的FJSP，相对于经典的FJSP，文中提出的模型能有效缩短完工时间，提高生产效率。

图9 MRFJSP 中规模问题的最优调度甘特图Fig.9 The optimal scheduling Gantt chart for scale problems in MRFJSP

3.3 算法评价

将IAOS 与其他的元启发式算法进行实验对比，对比算法包括原子轨道搜索算法（AOS）［7］、遗传算法（GA）［14］、变邻域遗传算法（GA-VNS）［12］。为避免随机性，算法各运行10 次，参考文献［15］的对比方法加入提升率R，用来表示IAOS 相较于其他元启发式算法的提升水平，其计算公式为（tIAOS，Best-tAOS，Best）／tIAOS，Best。各算法在不同规模下的求解结果如表5 所示，各算法求解中规模问题的迭代曲线如图10 所示。

图10 中规模问题算法迭代曲线Fig.10 Algorithm iteration curves for medium scale problems

表5 算法实验结果Tab.5 Algorithm experiment results

由表5 可知：从求解效果来看，对于小规模问题，除GA 算法的求解结果不佳外，其他3 种算法都取得了较好的解，IAOS 算法相较于AOS、GA 和GA-VNS算法的平均提升率分别提升了1.23%、1.64%和0.81%；对于中规模问题的求解，IAOS 搜索到的结果最好且与其他搜索算法的最优解拉开了一定的差距，相较于AOS、GA 和GA-VNS 算法的平均提升率分别提升了16.2%、27.12%和13.79%，由此体现出IAOS 改进的有效性以及在求解多工艺路线FJSP 上的优越性；对于大规模问题，AOS 和GA 算法的求解结果不理想，求解能力明显下降，GA-VNS算法虽然在大规模问题上仍有一定的求解能力，但求解结果不如IAOS 优秀，证明了IAOS 算法在求解复杂度较高问题时的高效性。

由图10 可知：对于中规模问题各算法在运算初期就能快速寻优，但在迭代50 次后明显能看出AOS、GA 和GA-VNS 算法寻优能力均有所下降，IAOS 算法在迭代50 次后虽寻优速度减慢，但仍然具有一定的搜索能力。从收敛性上分析，IAOS、AOS、GA 和GA-VNS 算法分别在迭代175、38、57 和206 次时收敛。IAOS 虽然收敛速度较慢，但求得了优于其他算法的解；AOS 收敛最快，获得了比较好的求解结果；GA 收敛也较快，但求得的结果最差；GA-VNS 收敛速度最慢，但其对GA 的改进有效，也取得了比较好的解。综上可看出：虽然IAOS 收敛速度慢于AOS 和GA，时间复杂度略高于其他算法，但IAOS 的改进措施有效，在算法搜索的开始阶段就能快速找到优于其他算法的解，能有效跳出局部最优，找到更好的解。

综合来看，IAOS 算法在整体求解过程中寻优能力较好，应用于不同规模问题时的适用性较强，尤其是在求解复杂度较高的大规模问题时IAOS 算法比其他算法表现出更好的寻优能力。因此采用IAOS 算法进行多工艺路线柔性作业车间调度优化是可行的。

4 结论

（1）本文作者分析了工件的多工艺路线与柔性作业车间调度之间的联系以及特点，建立了多工艺路线柔性作业车间调度模型，通过实验验证了多工艺路线柔性作业车间调度模型的有效性。

（2）设计了一种改进原子轨道搜索算法，引入一种三层编码方式使其适用于求解MRFJSP；引入自体交叉和变邻域变异增强局部搜索并避免陷入局部最优；迭代过程中设计了变工序数精英保留策略，扩大了搜索空间，使算法的求解质量和效率得到提高。

（3）采用3 组不同规模MRFJSP 对改进原子轨道搜索算法和其他3 种元启发式算法的求解结果进行比较分析，验证了改进原子轨道搜索算法的可行性和适用性。