基于多重邻域交换的离散人工蜂群算法，用于处理具有不确定加工阶段的混合流水线调度问题

《Swarm and Evolutionary Computation》：Discrete artificial bee colony algorithm based on multiple neighborhood swaps for the hybrid flowshop scheduling problem with uncertain processing stages

钢连铸混合流车间调度问题中不确定加工阶段的研究，提出混合整数规划模型、启发式算法和DABC-MNS算法，实验验证算法在平均逗留时间等指标上优于其他六种元启发式方法。

　　

杨宇|宋新波|李子翔|孙亮亮|韩玉燕|庞新福|王竹军|娜塔莉娅·M·马特斯韦丘克|尤里·N·索茨科夫

沈阳航空航天大学自动化学院，中国沈阳110136

摘要

本文研究了一个实际的混合流水车间调度问题，该问题源于钢铁连续铸造（SCC）过程，并且存在处理阶段的不确定性。首先，建立了一个考虑处理阶段不确定性的SCC调度问题的混合整数数学模型（SCCSP_UPS），并分析了其特点。其次，设计了一种基于处理阶段不确定性的新颖启发式方法，从而获得了更好的解决方案。第三，提出了一种基于多邻域交换的二维离散人工蜂群算法（DABC_MNS）来解决SCCSP_UPS问题，其中开发了一种用于表示解的二维编码方案，探索了一种四维锦标赛选择策略，并设计了多邻域交换操作符来进行更优个体的搜索。最后，将DABC_MNS算法与其他六种著名的元启发式算法进行了比较，结果表明DABC_MNS算法的性能优于其他元启发式方法。

引言

钢铁连续铸造（SCC）是钢铁生产过程中的一个关键环节，它将液态钢转化为板坯。SCC的生产过程包括三个主要阶段：炼钢、精炼和连续铸造。每个阶段中的机器都是并行运行的。合理的SCC调度有助于提高生产效率并提升板坯的质量。如[[1]]、[2]]、[3]]所述，SCC调度问题（SCCSP）是一个复杂的混合流水车间调度问题（HFSP），其中需要连续不断地进行铸造。由于[4,5]的研究表明HFSP属于NP难问题，因此SCCSP也被认为是NP难问题，近年来受到了研究人员的广泛关注。

在SCC车间中，由于订单要求的变化或生产条件的变化，可能会出现一些不确定事件，例如处理冲突、处理时间不确定等。为了满足连续铸造机的温度和熔钢成分要求，一些坯料需要进一步处理以达到所需的温度并去除杂质。因此，一些坯料需要经过初次精炼，而另一些则需要进一步精炼以满足质量要求。在这种操作模式下，所有坯料都经过三个阶段的处理，即炼钢、初次精炼和连续铸造阶段；但部分坯料需要经过四个阶段的处理，即双重精炼以满足生产技术的要求。这就是具有处理阶段不确定性的SCCSP（SCCSP_UPS），它被归类为混合柔性流水车间调度问题（HFFSP）。SCCSP_UPS比SCCSP更为复杂，因此也是一个NP难问题。

目前，HFFSP问题受到了广泛关注，特别是在机器故障[6]、无等待调度[7]和综合运输[8]等领域。在SCC研究中，[9,10]分别探讨了带有操作跳过的HFSSP问题，并提出了有效的解决方法。关于SCCSP_UPS，该领域的研究较少。因此，本文重点研究了部分坯料需要经过双重精炼的SCCSP_UPS问题。离散人工蜂群（DABC）算法已广泛应用于HFSP问题，尤其是在钢铁连续铸造调度问题（SCCSP）中，并显示出强大的鲁棒性和计算效率[[11]]、[12]]、[13]]。鉴于DABC框架在解决复杂SCCSP问题方面的能力，本研究设计了DABC_MNS算法来解决SCCSP_UPS问题。

主要贡献如下：

(1)

本文为SCCSP_UPS开发了一个混合整数规划模型。

(2)

提出了一种新颖的启发式方法，该方法利用炼钢阶段的开始时间对坯料进行排序，并设计了一种右移策略。

(3)

通过分析SCCSP_UPS的特点，提出了DABC_MNS算法，该算法设计了用于表示解的二维编码方案，在使用的蜜蜂和观察蜜蜂阶段探索了四维锦标赛选择策略来选择更优个体，并在观察蜜蜂阶段设计了多邻域交换操作符来进行更优个体的搜索。

剩余内容的布局如下：第2节回顾相关文献；第3节建立SCCSP_UPS的混合整数数学模型；第4节描述了基于SCCSP_UPS特点的新颖启发式方法；第5节介绍了DABC_MNS算法，包括初始化、使用的蜜蜂阶段、观察蜜蜂阶段、侦察蜜蜂阶段和多邻域交换操作符；第6节通过实验验证了所提算法的性能；第7节总结了本文的主要研究成果，并对未来研究进行了展望。

节选内容

文献综述

鉴于关于SCCSP_UPS的文献较少，本文对现有研究进行了全面回顾。基于上述分析，本文的相关工作包括SCC中的调度问题和混合柔性流水车间调度问题（HFFSP）。以下是针对这两个方面的具体文献综述。

SCC调度问题

首先介绍了SCC的生产过程，描述了工业过程和研究场景，并基于研究场景建立了SCCSP_UPS的数学模型。然后给出了一个SCCSP_UPS的示例，以进一步明确研究问题和场景。详细内容如下。

新颖启发式算法

提出了一种基于问题特性的新颖启发式方法，用于生成高质量的初始解。通过扩展Pan的启发式方法[20]并结合SCCSP_UPS的特点，本文设计了一种新颖的启发式方法，通过按非递减顺序对炼钢阶段所有坯料的开始时间进行排序来生成初始序列。新颖启发式的步骤如下。

步骤1：连续铸造阶段所有坯料的开始时间

DABC_mns算法

标准的DABC算法[1,7,20]包括使用的蜜蜂阶段、观察蜜蜂阶段和侦察蜜蜂阶段，这些阶段在处理SCCSP问题时表现出较高的性能。因此，本文通过扩展DABC算法，引入了一对用于表示解的向量、一种用于种群初始化的新颖启发式方法、一种用于观察蜜蜂的MNS操作符以及一种用于选择个体的四维锦标赛方法，从而开发了DABC_MNS算法。DABC_MNS算法的组成部分如下

测试实例

为了评估和分析所提方法的性能，根据参考文献[20]设计了一些测试实例，这些实例来自某钢铁企业的实际场景。在该实验中，炼钢车间配备了三个转炉、五个初次精炼炉和四个连续铸造机。在实验框架内，我们划分了三种不同的处理规模：小规模、中等规模和

结论

本文研究了SCCSP_UPS问题，目标函数包括平均停留时间、提前惩罚、延迟惩罚和最大完成时间，并开发了一种新颖的启发式方法和DABC_MNS算法。首先建立了SCCSP_UPS的数学模型，并分析了其关键特点。其次，提出了一种新颖的启发式方法来解决SCCSP_UPS问题，该方法根据预定义的规则计算炼钢阶段每个坯料的开始时间

CRediT作者贡献声明

杨宇：撰写——审阅与编辑、概念化。宋新波：撰写——审阅与编辑、撰写——初稿、方法论、数据整理、概念化。李子翔：概念化。孙亮亮：概念化。韩玉燕：概念化。庞新福：概念化。王竹军：概念化。娜塔莉娅·M·马特斯韦丘克：概念化。尤里·N·索茨科夫：概念化。