基于机器空隙的自适应改进金枪鱼群算法在生产排程调度中的研究

张东方 常万军 张洁 郭智 张芊芊 王晓雷

关键词：生产排程调度；金枪鱼群优化算法；机器空隙；自适应算子

0 引言

在工业领域，学者们积极提出了各种排程优化方法，这些方法主要分为精确方法和近似方法。精确方法在理论上容易实现，能够得到最优解，但在大规模和复杂背景下往往受到限制，研究表明，当总工序超过250小时，精确方法的计算效率明显受到限制[1-2]。而近似方法可以在相对短的时间内解决较大规模的问题，使其成为处理实际工业生产中大规模任务的可行选择。智能优化算法将排程调度问题转换为通过人工智能技术对问题进行动态演化的过程。例如，Umam等[3]将禁忌搜索过程与遗传算法相结合，采用基于部分对立的种群初始化技术来最小化最大完工时间。Ali等[4]提出了一种基于虚拟交叉算子的进化遗传算法，并将其应用到动态作业车间调度问题。黄宇等[5]为求解高复杂排程调度问题，提出基于差分量子粒子群优化算法。然而，每种智能算法都具有独特的特性，智能算法的挑战主要体现在计算量大、编码解码频繁等方面，需要在综合考虑其优缺点的基础上，为实际应用场景选择合适的智能方法。

1 基于自适应改进金枪鱼群算法的生产调度模型

1.1 基于机器空隙的工序机器选择

本文提出了一种基于操作的解码方法，该方法在解码过程中能够为工序选择适当的加工机器。机器的选择规则取决于当前加工机器m的空闲时刻之前是否存在可插入的空隙[6]。对（?1）′≤&&（+T）≤ 和 ≤（?1）′&&（（?1）′ + T） ≤两种情况，空隙均是可插的。

解码的工序插入方式包括两种情况，如图1所示。本文选择与当前解码工序所需加工时间大小最为接近的空隙。如果机器均无可插入空隙，则根据当前最小最大完工时间为当前解码工序选择机器。

1.2 混沌映射初始化种群

本文选用logistic混沌映射作为初始化种群的手段，以改进解的质量，初始化公式如式（1） 所示。

式（1） 中Xi代表初始种群中第i 个个体的向量位置，为由logistic 混沌映射生成的随机数，ubD 和lbD为搜索空间的边界。引入logistic混沌映射的设定有助于实现更为均匀的种群分布，增强算法在整个空间的搜索能力。

1.3 自适应更新与解浓度的扰动处理

更新位置向量时，相同概率的更新方式存在可能会导致迭代周期的增长、收敛速度的减缓[7-8]。为解决金枪鱼群算法两种位置更新方式在解空间搜索能力的差异，本文引入自适应参数，并引入Levy飞行策略，螺旋位置更新的公式如式（2） 所示。

1.4 基于工件工序的变邻域搜索机制

为提升对解空间的全面探索，本研究引入了变邻域搜索机制，以通过改变工件工序序列的基因位值生成新的可行解。本文构建了三种不同类型的邻域搜索结构NS，用于增强算法的邻域探索能力，使其能够更为灵活地遍历搜索空间。

1） 邻域搜索结构NS1。为改变工件工序编码基因段中基因的相对位置，本文采用基因交换的移动邻域结构，变换过程如下：

步骤1：在工件工序编码基因段范围内随机生成两个不等随机数1、2，1≠2 且1<2。

步骤2：判断1、2 的基因位在工件工序编码中是否相同，不同则将基因位中的工序进行交换；相同则1=1+1，并重新执行步骤2。

2） 邻域搜索结构NS2按以下过程进行结构变换：

步骤1：在工件的工序序列编码基因段范围内，生成两个不同的随机数：rand1、rand2，且rand1

步骤2：将以rand1为首，rand2为尾的基因段进行逆转形成新的工件工序序列编码基因段，以产生邻域解。

3） 邻域搜索结构NS3随机选择两种不同类型的工件并将其对应基因位互换，以下为结构变换的具体过程描述：

步骤1：在工件工序序列编码的基因段中，随机抽取两种不同的工件编号；

步骤2：将两个工件号在基因段中基因位进行交换，若两种工件的工序数量相等，则按照工件在工件工序序列中的基因位置，从左至右逐一交换生成新的邻域解；若两种工件的工序数量不等，则以工序数小的工件为主，按照从左至右的顺序逐一交换这两种工件工序所对应的基因位，完成交换后生成新的邻域解。

以图2中的工件工序序列编码S3为例，假设在随机过程中选中了J2和J3这两个工件，按照NS3邻域变换规则变换后得到新的工件工序序列编码如图2中所示。

2 实验结果与分析

本小节选择金枪鱼群算法（Tuna swarm optimiza?tion， TSO） 、陈亮等[9] 提出的自学习遗传算法（Selflearninggenetic algorithm， SLGA） 、黄宇等[5]提出的差分量子粒子群算法（Differential evolution quantum par?ticle swarm optimization， DEQPSO）、张景淘[10]提出的自学习蜂群算法（Self-learning artificial bee colony algo?rithm， SLABC） 、杨草原[11]提出的鲸鱼优化算法（WhaleOptimization Algorithm， WOA） 与本文提出的TSOAMG 算法作比较。为保证公平，所有实验均在相同环境下进行。设置种群数为30，最大迭代数为500，各对比算法均在各文献提供的最优参数下进行。本文的TSOAMG算法实验中z=0.05，a=0.7，与文献11中TSO 算法一致。所有算法对每个数据案例均运行10次，实验结果如表1所示。为比较算法的收敛性，图3展示了20×10规模下的算法的收敛情况。

由图3可知，实验中在前100代收敛速度最快，本文改进的TSOMG算法与黄宇等改进的IPSO算法在100代后达到其最优函数值，其余4种算法均在150代后达到最优函数值。由此可知，本文改进TSOMG算法在排成调度问题中有较好的收敛性。

3 结束语

针对当下离散制造业生产中存在的排程调度不准确问题，本文提出了一种基于机器空隙的自适应改进金枪鱼群算法，通过自适应更新来提高寻优能力和收敛精度。为保证流程初始化阵列的多样性，本文采用混沌映射初始化阵列，设计自适应阵列算子情况选择不同的更新策略，并结合Levy飞行策略来增强算法的搜索范围。通过对排程经典案例的实验验证，证明了TSOMG算法在排程结果和收敛性优于当下其他流行算法，解决了多样化订单排程困难的问题，为传统制造业实现智能化生产提供了解决思路。