一种改进的和声搜索算法求解FJSP

2022-07-12徐文星梁菁菁高梓森俞奉伶

计算机应用与软件 2022年6期

徐文星梁菁菁高梓森俞奉伶盛沙*

1(北京石油化工学院信息工程学院北京 102617) 2(北京市密云区科学技术委员会北京 101500)

0 引言

柔性作业车间调度问题(FJSP)是传统车间调度的扩展。由于一道工序可以由给定集合中的任何机器处理[1-2]，FJSP增强了生产调度的灵活性，更加贴近实际生产中的制造环境[3]。但因为不仅需要对工序加工顺序进行排序，还需要给工序分配机器，FJSP比传统作业车间调度问题更复杂，同样归为NP-hard类问题[4]。

虽然FJSP的复杂性是众所周知的，但是为了适应当前市场的需要，研究者们还是更多地关注FJSP。目前，FJSP的求解方法分为两种，精确算法和近似算法。精确算法的优化结果虽然精确，但在有限的时间里无法有效解决大规模车间调度问题。另一种方法是近似算法，目前，随着智能算法的发展，应用智能算法求解该问题已经成为最流行的方法，如：Lu等[5]利用遗传算法(GA)求解分布式FJSP；Wang等[6]采用一种改进的蚁群优化算法(IACO)来优化FJSP的最大完工时间；Zarrouk等[7]提出了一种两级粒子群优化算法求解FJSP；Gao等[8]针对具有模糊处理时间的FJSP，提出了一种改进的人工蜂群(IABC)算法；姜天华[9]将混合灰狼优化算法(GWO)用于求解FJSP。虽然智能算法在FJSP上进行了大量研究，但仍然没有一种智能算法能够求得所有FJSP的最优解，所以研究者们还在不断地探索新的、更有效的方法。

近年来，随着智能算法的不断发展，出现了模拟音乐家演奏出完美和声过程的和声搜索算法[10]，该算法具有理论简单和易实现的特点。为了提高和声搜索算法的搜索能力，Zou等[11]将和声搜索算法与遗传算法融合做出改进，以遗传突变替换了随机选择部分，对和声记忆库中的最坏和声进行小概率遗传变异操作，既增强了收敛性，又能有效地防止神经网络陷入局部最优，在解决无约束问题上取得了一定成效。随后，改进的和声搜索算法被尝试用于调度问题。Pan等[12]将和声搜索算法应用于批量流水车间调度。吴龙成等[13]将改进的和声搜索算法应用于硫化车间调度。张敬敏等[14]将差分和声搜索算法应用到作业车间调度问题。Yuan等[15]将基于集成方法的混合和声搜索算法应用到了FJSP。崔喆[16]在和声搜索算法中加入差分进化策略，变异过程中对和声库中的所有和声以一定的变异概率进行插入操作，在解决流水车间调度问题上取得了一定成效。Gao等[17]将离散和声搜索算法应用于多目标FJSP。和声搜索算法应用于车间调度领域求解问题取得了一定的成效，但仍然存在很多不足。虽然和声搜索算法具有很强的全局搜索能力，但是局部搜索能力比较弱，后期进化速度大幅减慢，同时应用在FJSP问题上操作复杂。结合前人的研究与改进思想，本文针对不足之处提出一种适用于柔性作业车间编码方式的改进和声搜索算法。采用两种初始化方式混合应用进行初始化，保证了解的多样性和解的质量；基于两段组合编码方式，结合一种新的创作和声策略来进行和声更新，避免产生无效解；采用一次创作多个和声来充分利用和声库的有用资源，同时应用智能变异算子均衡机器负载，在保证全局搜索效率的同时，加强了局部搜索能力。最后通过实例测试结果证明了改进和声搜索算法对于求解单目标FJSP的有效性。

1 柔性作业车间问题

FJSP是n个工件J(Ji,i∈{1,2,…,n})在m台机器M(Mk,k∈{1,2,…,m})上加工的调度模型。每个工件由一道或者多道操作工序O(Oij,j∈{1,2,…,ni})组成，ni表示当前工件的总工序数。每道工序可选择允许机器集(一台或多台不同机器)中任意一台机器进行加工。FJSP的目的是选择加工每道工序的机器设备，并且对所有工序进行排序，达到优化目标的最优值。此类问题满足的约束条件有：

(1) 在同一工件中，工序具有优先级，前一道工序加工后才可以开始加工下一道。

(2) 不同工件的加工优先级相同。不同工件的工序加工优先级也是相同的。

(3) 在0时刻，假设所有机器都是空闲的,并且在机器加工完成到下一道工序没有开始时进行空载运行。

(4) 同一个工件上的同一道工序只能在一台机器上加工。同一时刻每台机器上也只能加工一道工序。

(5) 任何工序一旦开始加工，就不可间断。

(6) 工件的准备时间以及转移时间都算在加工时间内。

本文在求解FJSP时，考虑优化调度系统最大完工时间这一优化目标。即在满足上述所有约束条件后，达到机器最大完工时间值最小化。用MT(k)表示在第k台机器上的完工时间，则数学模型表示为：

(1)

如表1所示的3×5 FJSP实例，有3个工件，每个工件对应3道工序，每道工序有多台机可供选择，在可选择机器上的加工时间分别给出，“—”表示对应该道工序不能在对应此台机器上加工。本文后续均以这一实例为例对改进和声搜索算法求解FJSP过程进行说明。

表1 3×5 FJSP实例描述

2 基本和声搜索算法

和声搜索就是把音乐家弹奏乐曲的过程转化为数学表示。首先按照和声记忆库大小(Harmony Memory Size, HMS)初始化和声记忆库，并且对和声库内的和声按照目标解由优到差的次序排出最优解和最差解，存放解向量的HM矩阵如式(2)所示。然后每次创作一个新和声进行迭代。创造的新和声就是产生的一个新的解向量，创造方式由考虑从和声库中学习、考虑是否调整和声音调、随机创作一个新的音调三部分组成。最后更新和声库，将创作的新和声与和声记忆库内的最差和声进行比较，如果新和声的解优于和声库内的最差解，则将新和声放入和声库内，否则保留原和声库的和声。

(2)

3 改进和声搜索算法求解FJSP

3.1 编码与解码

柔性作业车间要解决的主要问题分为两部分：(1) 对加工每道工序的机器集里的机器进行选择；(2) 对工序的加工顺序进行排序。故本文采用两段组合编码方式对和声搜索算法进行编码，将一组和声分为机器选择部分(Machine Selection Section， MSS)和工序排序部分(Operational Sequencing Section， OSS)两段。每段编码长度为工序数L，总编码长度为2L。

(1) 和声的机器选择部分编码：按照工件工序的顺序依次选择机器，这部分每一个音符代表机器在可选机器集中的位置号，如图1所示，和声的第一个音符“4”为第一个工件第一道工序所对应机器集{M1，M2，M3，M5}中的第四台机器M5。

图1 MSS/OSS编码说明

(2) 和声的工序排序部分编码：每个音符代表的都是它的工件数，相同音符出现的次序就是这个工件的工序数。第一个音符“2”就表示为第二个工件的第一道工序，即O21。

解码是编码的逆过程，是将一组和声工序排序部分解码成对应机器选择部分的活动调度的过程。依据工序顺序对应的机器编码选择每道工序的加工机器和加工时间，按照工序部分编码确定的顺序依次进行解码，并且采用插入法在不改变已安排工序的情况下，将新工序尽可能地插入对应机器上的空闲位置进行加工，缩短在这台机器上加工的完成时间。

3.2 和声记忆库初始化

同其他智能算法类似，和声搜索算法的和声记忆库初始化也直接影响和声搜索的最终解。对于和声记忆库的初始化要达到两个要求：(1) 要保持和声记忆库的多样性，扩大搜索范围，提高搜索到全局最优解的概率；(2) 要保证和声记忆库初始化的解的质量，解的质量影响着收敛速率。为了更好地达到以上两点要求，本文对和声记忆库中和声的机器选择部分和工序排序部分采用不同的初始化方式，具体方案如下：

(1) 和声的工序排序部分则采用随机生成方式，这样能使解的分布更广，达到扩大解的搜索范围的目的。

(2) 和声的工序排序部分则采用优先对关键工序进行机器选择的全局初始化方式[18]，全面考虑到关键工序对机器负荷和工件加工时间产生的重要影响，提高初始解的质量。

3.3 创作新和声

基本的和声算法在每次迭代时，只创造一个新和声，没有最大可能地利用和声库里积累下来的信息，因此本文提出改进策略，在每次迭代时同时产生多个新和声，然后用多个新和声进行迭代，以此提高搜索速度。在创作新和声的机器选择部分和工序排序部分时结合了FJSP的特征采用了有效的创作方式[19]，创作步骤如下。

(1) 新和声的机器选择部分：生成新和声机器选择部分的策略是当rand1

图2 创作MSS示例

(2) 新和声的工序排序部分：按照传统的和声搜索去创作新和声的工序排序部分可能会生成非法解，故结合FJSP特性对生成策略做了调整，加入了一个转化矩阵，将生成新和声工序排序部分分为两个模块。第一模块是生成转换矩阵，首先将n个工件号置乱，对每一个工件进行判断，当rand1

图3 创作OSS示例

3.4 和声智能变异

为了提高算法的搜索能力，本文在生成的多个新和声中进行智能变异操作，并且在变异操作过程中结合FJSP的特点考虑到平衡机器负载，增加搜索到最优和声的概率，提高搜索最优和声速率，可以更有效求解FJSP。智能变异操作的步骤：(1) 当rand3

图4 和声智能变异示例

3.5 更新和声库

对每一步迭代产生的多个新和声进行目标函数评价，将创作的新和声解与和声记忆库中保留下来的和声解进行比较。即对HMS+NHM(NHM为每次产生新和声的数量)个和声按照解从优到差的顺序排序，选出前HMS个和声作为和声记忆库继续进行迭代更新。

3.6 算法流程

改进和声搜索算法的总体流程如下。

Step1初始化算法参数。初始化实验案例数据、和声记忆库大小HMS、考虑在和声记忆库中取值的概率HMCR、考虑是否调整和声音调PAR、每次产生新和声的数量NHM、智能变异概率PIM、和迭代次数NI。

Step2初始化和声记忆库。采用两段组合的编码方式初始化HM，评估和声记忆库中的每一个和声，找到最优和声和最差和声。

Step3创作新和声。对NHM个和声进行新和声的机器选择部分和新和声的工序排序部分的创作。

Step4和声智能变异。利用PIM创作的新和声中需要进行智能变异的和声进行智能变异操作。

Step5更新和声记忆库。评估创作的新和声，用优于和声记忆库中和声的新和声替换和声记忆库中的和声，更新和声库的最优和声和最差和声。

Step6重复Step 3、Step 4和Step 5直到迭代次数等于NI，停止创作和更新。

Step7输出最优和声和最优和声解，即最佳机器选择与工序排序的操作和最小的最大完工时间。

4 仿真实验与分析

4.1 性能分析实验

4.1.1和声记忆库初始化方式

以Brandimarte[20]提出的MK02实例为例，以最大完工时间最小值为目标函数值研究不同初始化方式对改进和声搜索算法性能的影响，随机全局混合初始化和随机初始化实验设置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=500 000，COT=1(运行1次)。图5给出了不同初始化方式产生的初始值以及收敛情况。

图5 不同初始化方式对比结果

可以看出两种初始化方式求解MK02实例时，全局随机混合初始化方式产生的初始解的最优解要优于随机初始化方式所得解，并保证了初始解的质量。另外全局随机混合初始化方式求得的解的多样性也要优于随机初始化方式所得，因此后续收敛速度更快，即提高了搜索全局最优解的概率和收敛速度。这体现出了采用全局随机混合初始化方式求解FJSP的优越性。

4.1.2一次创作多个新和声

以Brandimarte[20]提出的MK04实例为例，以最大完工时间最小值为目标函数值研究一次创作多个和声对改进和声搜索算法性能的影响。由于更新机制不同，为保证生成新和声的总数相同，设置了不同的迭代次数。一次创作单个新和声实验设置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=500 000，COT=1。参考文献[21]并且通过实验验证，一次创作的多个新和声的数量为和声记忆库大小的一半时能够取得良好的算法性能，故一次创作多个新和声实验设置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=10 000，NHM=50，COT=1。图6对比了不同单次新和声创作数量下的收敛情况。

图6 不同单次新和声创作数量的对比结果

可以看出求解MK04实例时，在初始方式相同的情况下，以最大完工时间最小为目标，一次创作多个新和声在搜索到最优解时生成的总和声数要少于一次创作单个新和声搜索到最优解时生成的总和声数。体现出一次创作多个新和声的求解效率高于一次创作单个新和声的求解效率，能够充分利用和声库中的优良资源，以更快的收敛速度更有效地求解FJSP。

4.1.3加入智能变异的改进和声搜索算法

为了研究加入智能变异前后对改进和声搜索算法性能的影响，本文针对Cmax和AVCmax两个指标对文献[20]中的10个Brandimarte标准算例进行实验,并与文献[15]提出的HHM和文献[17]中提出的同类算法作对比。Cmax为案例求解COT次后取到的最大完工时间的最优值；AVCmax为案例运行COT次所得最优最大完工时间的平均值。加入智能变异前(改进前HS)实验设置如下：HMS=100，HMCR=0.97，PAR=0.01，NI=10 000，NHM=50，COT=10。加入智能变异后(改进HS)其他设置不变，增加参数PIM=0.8。表2给出了实验的对比结果。由表2可以看出，对于AVCmax指标，改进HS在10组标准算例中的结果全部不弱于改进前HS，其中7组结果更优。对于Cmax指标，加入改进HS在10组标准算例中求得的最优解全部不弱于改进前HS，其中4组结果更优。体现出加入智能变异后的改进HS增加了搜索到最优和声的概率。同时对比同类算法，对比文献[17]，Cmax指标有8组不弱于文献[17]，其中4组优于文献[17]。针对Cmax指标对比文献[15]的实验结果，改进HS有3组稍弱于文献[15]，其余均能达到相同水平。但是，文献[15]提出的HHM采用连续和声向量转化为离散和声向量的编码转换技术与基于关键路径的局部搜索技术，应用在FJSP问题上操作复杂，而本文提出的改进HS则简单易操作。通过实验结果与分析表明，改进HS用于求解FJSP实现简单且结果较优。

表2 加入智能变异前后及同类算法实验结果对比

4.2 算法对比

为了进一步验证本文提出改进和声搜索算法的有效性，针对Cmax和AVCmax两个指标对文献[20]中的10个Brandimarte标准算例进行实验。同时将算法与文献[9]提出的HGWO、文献[18]提出的改进GA、文献[22]中提出BBO和文献[23]中提出的PSO作比较。与其他算法具有可比较和可接受的计算效率时，实验设置如下：HMS=100，HMCR=0.97，PAR=0.01，NI=10 000，NHM=50，COT=10，PIM=0.8。改进HS与文献[9，18，22-23]中算法对比实验结果如表3所示，加粗标记的数据表示以下对比实验中实验结果最优解，10组实验中9组Cmax指标取得了最优解，证明了改进和声搜索算法在不同算法中的优越性。对于AVCmax指标，改进HS在10组标准算例中的值均不高于文献[9]，其中9组更低，证明了本文算法求解FJSP的稳定性高。

表3 改进HS与其他算法在基准算例上的对比结果

4.3 工程案例测试

为了进一步验证改进和声搜索算法的实用性和有效性，本文针对以下两个工程实例进行实验求解。

案例一数据来源于文献[24]中的数据，是某航空发动机公司加工过程提出的FJSP实例，共有6个工件，10台机器可供选择加工，每个工件有6道加工工序。利用提出的改进和声搜索算法对实例进行求解，以Cmax、AVCmax、MAXCmax为计算指标与其他算法进行比较，MAXCmax为案例求解COT次得到的最大完工时间的最差值。改进和声搜索算法参数设置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=10 000，NHM=50，COT=10。根据表4计算结果所示，改进和声搜索算法求解这三项指标的结果均优于其他算法，证明改进和声搜索算法能够更有效地解决FJSP。

表4 案例一对比结果统计

案例二数据来源于文献[25-26]中的数据，是某工厂柔性作业车间调度实例，共有6个工件、8台机器、26道加工工序。利用提出的改进和声搜索算法对实例进行求解，以Cmax和AVCmax为计算指标。改进和声搜索算法参数设置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=10 000，NHM=50，COT=10。得到的计算结果如表5所示，可见改进和声搜索算法求得这两项指标的结果优于其他两个文献中求得的结果，提高了计算精度。