基于改进NSGA-III算法的电阻片车间多目标调度模型

Research on Flexible Scheduling Problem of Resistor Sheet Processing and Scheduling Based on Multi-Objective Neighborhood NSGA-III Algorithm

摘要: 氧化锌电阻片是轨道交通用避雷器的核心部件，其生产制造过程面临规格型号多、工艺流程复杂，人员换班频繁等问题。本研究以提高电阻片制造车间的订单交付率和能源利用率为目标，提出了一种针对电阻片制造车间排产调度的基于多目标邻域的NSGA-III调度优化算法(DLNSGA-III)。首先，构建了包含完工时间、总能耗和总负载的多目标柔性车间调度模型；通过结合变邻域搜索算法、弱非支配排序和精英保留策略，加强了算法的局部搜索能力、多样性和收敛性，通过算例验证了所提算法的有效性和可行性。

Abstract: Zinc oxide resistors are the core component of lightning arresters for rail transit. The production and manufacturing process faces problems such as multiple specifications and models, complex process flows, and frequent personnel changes. This study aims to improve the order delivery rate and energy utilization rate of the resistor sheet manufacturing workshop, and proposes a multi-objective neighborhood-based NSGA-III scheduling optimization algorithm (DLNSGA-III) for the production scheduling of the resistor sheet manufacturing workshop. First, a multi-objective flexible workshop scheduling model including completion time, total energy consumption and total load is constructed; by combining the variable neighborhood search algorithm, weak non-domi- nated sorting and elite retention strategy, the algorithm’s local search capability, diversity and Convergence, the effectiveness and feasibility of the proposed algorithm are verified through numerical examples.

1. 引言

电阻片制造包括混料、造粒、成型、排胶与烧结、绝缘层喷涂、磨片、铝电极喷涂、电性能检测等多道工序，是一种典型的多作业车间协作生产。在实际生产中，由于电阻片制造设备不便停机的特性，电阻片制造车间采用24小时轮班工作制，在车间复杂的工作环境下，班组的轮替，设备的突发故障，在订单逐渐增多的情况下，迟缓的处理过程对生产效率的影响越来越大，由此导致的能源利用率降低，订单延迟对企业的效益带来了巨大的负面影响。因此，根据实际的生产情况，及时制定合理的动态调度方案，减少负面事件对生产效率的影响，已经成为制造业和学术界关注的研究方向。

Achmad P. Rifai等 [1] 通过应用改进的非支配排序生物地理优化算法(NSBBO)建立了双目标车间调度模型，提出了三种迁移模型(正弦、二次和梯形)，并将非支配排序和拥挤距离排序特性引入到NSBBO中，通过对不同组合的作业数量、操作数量和机器数量的实例进行测试，研究评估了算法的性能，并分析了其效果、效率、鲁棒性和解的多样性，研究结果表明该模型是一种有效且有潜力的方法，可用于解决多目标优化问题。裴小兵等 [2] 提出了基于博弈理论的改进GA算法的多目标柔性车间调度模型，通过将问题转化为动态博弈论模型，并应用改进混合遗传算法求解子博弈完美纳什均衡解，从而得到高质量的调度方案。实现了对多目标的快速优化部署。Guiliang Gong等 [3] 以最小化最大完工时间和最小总能耗为目标，提出了一种分布式调度算法，研究采用了两个关键的改进方法：基于改进的初始化机制(BIM)和基于局部搜索优化(LSO)的改进，BIM利用了模拟仿真来生成高质量的初始种群，以便更好地探索解空间。通过使用BIM，可以更快地找到较优的解决方案，LSO通过在遗传算法的迭代过程中应用局部搜索操作来改进当前种群的解决方案，加速了算法的收敛速度，并提高解的质量。Qianwang Deng等 [4] 提出了以机器总负荷、制造工期和加工成本为目标的柔性车间调度模型，研究提出了一种新的蜂群进化引导策略，通过引入蜜蜂的觅食行为来指导算法的搜索过程。这种策略可以帮助算法更好地探索搜索空间，并提高算法的全局搜索能力。Himanshu Jain等 [5] 基于NSGA-III算法，通过将Deb约束比较准则引入环境选择进行非支配排序提出了C-NSGA-III，研究提出了一种基于参考点的非支配排序方法的进化多目标优化算法，并优化了约束条件，并将其扩展为自适应方法。耿焕同等 [6] 提出了基于参考点的约束支配函数改进的NSGA-III算法，用来提升NSGA-III算法的收敛性，研究根据种群在决策空间的分布特征，计算相邻两代种群的熵差，判定种群的进化阶段。并且计算种群在目标空间的分布特征，评估参考点的重要性。王俊艳等 [7] 提出了基于惩罚函数的进化算法，该算法在基本NSGA-Ⅱ算法的基础上引入了惩罚机制，通过降低个体的优先级来减少其被选中的概率。欧阳洪才等 [8] 研究采用了两段式编码和基于参考点的小生境选择策略。提高了对多目标柔性作业车间求解效率，通过两段式编码将染色体分为工序编码和机器编码两部分，然后利用插入式贪婪解码将工序安排在最早可行的位置。通过基于参考点的小生境选择策略，修剪合并的种群，以保持种群的多样性和均匀分布。

NSGA-III从NSGA-II的框架上发展而来，针对NSGA-II中高维难以收敛及前沿解集均匀分布问题，NSGA-III引入了参考点机制取代NSGA-II中的拥挤度机制，从而获取了种群个体与响应参考点之间的映射关系，进而使得种群更接近参考点的方向进化，使得参考点的分布更加均匀。其中设定参考点数量为H，迭代t代的父代种群和子代种群 $Q_t$ 的种群数量均为N，将父代和子代的种群进行合并得 $U_t\left(U_t=P_t\cup Q_t\right)$ ，在 $U_t$ 中再选出N个体进入下代种群 $P_{t+1}$ 。

本文以电阻片制造车间为对象，创建了一个多目标柔性车间调度模型，包含完工时间、总能耗和总负载。为了提高算法局部搜索能力引入了变邻域搜索算法。改进原有的非支配选择算法，通过引入容忍参数实现弱非支配排序，使其如果在其他目标上的性能明显更好，就允许一个解在某个目标上的性能稍差，从而提高了算法的多样性。

2. 问题描述及目标函数构建

2.1. 问题描述

在实际生产过程中，电阻片制造车间会面临班组交替等常规干扰事件和机器故障等突发干扰时间，从而导致生产效率降低，生产成本提高。因此需要一个能够快速调整的生产调度计划能够在上述情况发生时快速生成最优方案，保证生产的持续性和稳定性。

电阻片制造车间调度问题描述如下：电阻片车间的工件总数为n，机器总数为m，集合描述为 $J=\left\{J_1,J_2,\cdots ,J_n\right\}$ ， $Z=\left\{Z_1,Z_2,\cdots ,Z_m\right\}$ 。对于每个工件 $j_i$ 的工序集合为 $\left\{O_{i1},O_{i2},\cdots ,O_{ij}\right\}$ ，每道工序都有至少一台以上的可选机器进行加工。参数模型如表1所示。

Table 1. Model parameters

表1. 模型参数

2.2. 目标函数

在车间生产过程中，不同的部门存在不同的考核指标，这就需要模型具备多目标的处理能力，从而最大限度的满足不同部门的实际需求。综合电阻片车间的实际需求，在本模型中，设置了三个目标函数分别是完工时间、总负载和总能耗。目标函数如下。

其中式(4)指开工后电阻片车间工序不能中断，式(5)指任意电阻片车间工序在机器上只加工 1次式(6)指任意电阻片车间工序的开工时间小于等于完工时间，式(7)指任意工序完工时间小于等于最大完工时间，式(8)指了每台机器在同一时刻只能加工一道电阻片车间工序，式(9)指任意工件的上一道电阻片车间工序的完工时间不大于下一道电阻片车间工序的开工时间，指任意电阻片车间工序的开工、加工、完工时间都非负。

1) 最小完工时间

$makespan=\min \left\{\max makespa{n}_i\right\}$ (1)

2) 总负载

$Load\_all={\displaystyle \sum Load\_z}$ (2)

3) 总能耗

$E\_all={\displaystyle \sum Load\_z{P}_z}+\left(F_z-Load\_z\right)R_z$ (3)

多目标柔性作业车间调度数学模型为：

$C_{ij}-S_{ij}=T_{ijz}\forall i,j,z$ (4)

${\displaystyle {\sum }_{z=1}^n{X}_{ijz}=1}\forall i,j$ (5)

$S_{ij}+X_{ijz}{T}_{ijz}\le C_{ij}\forall i,j,z$ (6)

$C_{ij}\le makespan\forall i,j$ (7)

$X_{hks}{C}_{hk}+M\left(G_{hkij}-1\right)\le X_{ijz}{S}_{ij}\forall i,j,z,h,k$ (8)

$C_{ij}\le S_{\left(j+1\right)}\forall i,j$ (9)

$S_{ij}\ge 0,T_{ijz}\ge 0,C_{ij}\ge 0\forall i,j,z$ (10)

3. 改进NSGA-III算法

Ded [9] 提出的NSGA-III算法在多目标优化问题中有比较好的效果，但仍有很多提升空间。

单一的种群初始化方式使得算法多样性大大降低，会使算法更容易陷入局部最优解，DLNSGA-III算法通过在种群初始化过程中引入混合初始化，可以有效的提升算法多样性。

NSGA-III算法中的交叉和变异操作可以让算法具有较强的全局搜索能力，但同时也削弱了算法的局部搜索能力。DLNSGA-III通过引入变邻域搜索算法，提高了算法局部搜索能力。其中在车间调度优化的局部搜索研究中，变邻域搜索算法得到了较为显著的提升 [10] 。为此，根据氧化锌电阻片车间调度问题的特点，本文采用了四种邻域结构：1) 交换，随机交换两个染色体解的位置；2) 插入，从染色体解中取出一个元素，并将其插入到另一位置；3) 反转逆序随机产生两个基因位置，将两点间的片段反转；4) 窗口式滑动，选择一个由多个染色体构成的任务子集并将其向前或向后滑动一定数量的位置，而不改变子集内的任务顺序。

在氧化锌电阻片多目标柔性车间调度过程中，由于该车间调度的产品较为单一，所以解的变化并不大，本文设计了一种弱非支配排序替代原有的非支配排序，对于小范围内变化的解提供了更广泛的解集。

在NSGA-III中，直接选取子代种群为最优解集可能导致遗失迭代中的最优解。为了维护种群的多样性并确保收敛性，引入了一个精英记忆库。

3.1. 算法流程

算法流程如图1所示。

DLNSGA-III算法的具体步骤如下：

步骤1：参数设置：令种群大小为N；迭代总次数为gen；最大迭代次数MAXGEN；交叉概率为 $p_c$ ；变异概率为 $P_m$ 。

步骤2：初始化种群：生成初始种群 $P_t$ ，将迭代总次数设置为0。

步骤3：根据优化目标及分段数，生成均匀分布的参考点。

步骤4：当迭代总次数达到最大迭代次数时(gen > MAXGEN)，则输出Pareto非劣解；当迭代总次数小于最大迭代次数时(gen < MAXGEN)，则记录当前最优解。

步骤5：对种群进行交叉和变异操作。

步骤6：完成交叉和变异操作后，合并子代与父代个体。

步骤7：对合并后的种群进行变邻域搜索，输出最优个体。

步骤8：用变邻域搜索的最优个体代替原种群的最差个体后，对其使用弱非支配排序进行分层。

步骤9：对每一层进行基于参考点的小生境选择，直到选取个数到N，转到步骤4。

步骤10：若满足迭代要求，则输出Pareto非劣解。否则继续步骤5。

Figure 1. DLNAGA-III algorithm flow chart

图1. DLNAGA-III算法流程图

3.2. 混合初始化

种群的初始设置在FJSP中是关键，因为初始解的优劣会影响到求解的速度和效果。其中，机器的选择相较于工序的顺序更为核心。此处，采用混合初始化方式来决策机器的选择，具体包括全局选择(GS)、局部选择(LS)以及随机选择(RS) [11] 。GS的目标依次安排每个工件的加工，每道工序选择最小负荷的机器。LS依次安排每个工件的加工，每次安排完一个工件加工后，各个机器的负荷清0，每道工序选择最小负荷的机器。相对地，RS依次安排每个工件的加工，每道工序随机选择可加工机器，这样可以确保调度解在目标空间中的分布更为分散，同时也保证了种群的多样性。

3.3. 变邻域搜索算法

根据电阻片车间柔性调度问题，采用了4种产生最优解邻域的方法。

两点交换：随机交换两个染色体解的位置，例如，对于一个排列1，2，3，4，5，交换第2个和第4个元素的位置得到1，4，3，2，5。

插入：从染色体解中取出一个元素，并将其插入到另一位置，例如，对于同样的排列1，2，3，4，5，将第3个元素取出并插入到第5个元素之后，得到1，2，4，5，3。

反转逆序：选择序列中的两个位置i和j，其中i < j，然后反转从位置i到位置j的所有元素。例如，对于序列：1，2，3，4，5如果选择位置2和4，则执行反转逆序操作后的序列为：1，4，3，2，5。

窗口式滑动：基本原理是在给定解的某个子序列或“窗口”上进行局部修改，而不是对整个解进行全局修改。包括以下步骤：

窗口选择：从当前解中随机选择一个连续的子序列，也称为“窗口”。窗口的大小可以是预定义的，或可以从一个给定的范围内随机选择。

滑动操作：一旦选择了窗口，就将这个子序列向前或向后“滑动”一定数量的位置。滑动的方向和距离可以是预定义的，或可以随机决定。例如，通过将上述的3个任务的窗口向前滑动2个位置。

调整其他任务：滑动窗口后，原来窗口的位置会空出来，或者新的位置可能已经被其他任务占用。因此，需要对那些被影响的任务进行相应的调整。最简单的方法是将被滑动窗口“推出”的任务移到原来窗口的位置，以保持所有任务的连续性。

例如，考虑一个简化的调度问题，其中任务序列为：A，B，C，D，E，F。如果选择了一个包含B和C的窗口，并将其向前滑动1个位置，那么新的任务序列将是：B，C，A，D，E，F。

窗口式滑动的优点是它允许在解的局部区域进行精细的修改，而不是进行全局的大范围修改。这有助于在搜索空间中进行更深入、更具针对性的探索。

基于上述4种邻域结构，变邻域搜索算法流程如图2所示：

Figure 2. Variable neighborhood search algorithm flow chart

图2. 变邻域搜索算法流程图

具体步骤如下：

步骤1：定义邻域结构，设定邻域结构的集合为 $N_i\left\{i|1,2,3,4\right\}$ 。

步骤2：初始化，选择一个初始解x。

步骤3：设置当前邻域索引 $i=1$ ，并设定终止条件 $i\le 4$ 。

步骤4：在当前邻域结构 $N_i$ 中随机选择一个邻居 $x^{\prime }$ 。

步骤5：在 $x^{\prime }$ 为起始解的情况下进行局部搜索，得到 $x^{″}$ 。

步骤6：如果 $x^{″}$ 比 $x^{\prime }$ 更好，更新 $x=x^{″}$ 并重新设置 $i=1$ ，否则 $i+1$ 。

步骤7：输出最优解x。

本文考虑NSGA-III和VNS算法的各自优势以及电阻片车间柔性调度问题的特点，提出了使用弱非支配排序的混合变邻域改进NSGA-III。

3.4. 弱非支配排序

本文设计了一种弱非支配排序，与传统的非支配排序相比，弱非支配排序在处理解的等级分配时更为宽松，因为它允许解在某些目标上与其他解相同，而不被其他解支配

为了明确地描述这个关系，设有两个解x₁和x₂，并且有m个目标函数 $f_1,f_2,\cdots ,f_m$ 。

对于每一个目标函数 $f_i$ ，可以得到其在解x₁和x₂上的取值，即 $f_i\left(x_1\right)$ 和 $f_i\left(x_2\right)$ 。

弱非支配关系可以定义如下：

解x₁弱支配解x₂当且仅当满足以下两个条件：

1) 对于所有的 $i\in \left\{1,2,\cdots ,m\right\}$ ，有 $f_i\left(x_1\right)\le f_i\left(x_2\right)$ ；

2) 至少对于一个 $j\in \left\{1,2,\cdots ,m\right\}$ ，有 $f_j\left(x_1\right)\le f_j\left(x_2\right)$ 。

根据这个定义，如果x₁弱支配x₂，那么x₁在所有目标上都不劣于x₂，并且x₁在至少一个目标上优于x₂。

3.5. 精英保留策略

由于在迭代过程中会出现丢失最优解的问题，于是在变邻域操作产生子代种群后，建立了精英种群库 [12] ，种群库的容量为N，将子代种群与当前精英库合并，并进行去重；再利用弱非支配原则对其进行分层，随后选取非支配层中的F₁存入精英库，设记忆库的最大容量为N。在每一轮的迭代结束时，都要更新这个记忆库。若当前非支配层F₁中的个体数少于或等于N，记忆库的容量N₀就被定义为F₁中的个体数和N中的较小值，即 $N_0=\min \left\{\left|F_1\right|N\right\}$ 。

4. 实验例证

4.1. 实验构造及参数设置

DLNSGA-III算法开发基于Python 3.11.1，主要依赖以下几个关键的第三方库，包括NumPy 1.24.3和Matplotlib 3.7.1。该算法在Windows 11操作系统上运行，配备了Intel i5-12600K处理器和16GB的RAM。在进行实验时，采用了如下命名方式——j*c*a [13] ，其中“*”代表一个正整数。例如，j10c6a1代表的是一个涉及10个工件和6个加工步骤的案例，数字1指的是它是第一个案例。这些数据是通过Python脚本随机生成的，其中包括每台机器的加工时间(介于15到40分钟之间)、每个步骤涉及的机器数量(2到5台之间)以及每台机器的能耗(5到10 kw之间)。

为了测试算法的有效性，随机生成了20个不同的案例，并在以下几个特定场景中进行了测试：j10c5a1至j10c5a5、j20c6a1至j20c6a5、j30c7a1至j30c7a5、j50c8a1至j50c8a5。在这些案例中，分别应用了NSGA-II、NSGA-III以及DLNSGA-III算法进行求解，并对这三种算法的性能进行了比较分析。这种比较旨在评估DLNSGA-III算法在处理不同规模和复杂性任务时的效率和准确性。

3种算法参数设置为：种群规模为50，迭代次数为200，交叉概率为0.7，交叉概率为0.3。

4.1.1. 评价指标

欧式距离(Generational distance, GD) [14] ，通过求取帕累托前沿上每个点到最近的真实帕累托上的欧式距离，并取平均，从而对算法的收敛性进行评价。

反转世代距离(Inverted generational distance, IGD) [14] ，通过将真实帕累托前沿上每个点到算得的帕累托前沿上距离最近的点相加取平均，从而对算法的多样性和收敛性进行评价。

非支配解(Non⁃dominated solution, NDS) [15] ，通过统计非支配解的个数，从而对算法的多样性进行评价。

4.1.2. 结果对比

表2~4展示了三种算法——DLNSGA-III、NSGA-II和NSGA-III——独立运行10次所得到的性能指标GD、IGD和NDS的结果。表1详细记录了20组实验中每个指标的最小值、最大值和平均值，其中最优值以加粗形式标出。图3~5分别展示了三种算法在GD、IGD和NDS的平均值。图6~8则分别展示了这三种算法在GD、IGD和NDS的箱线图。

Table 2. GD

表2. 欧式距离

Table 3. IGD

表3. 反转世代距离

Table 4. NDS

表4. 非支配解

从图3的数据分析来看，经过10次独立运行，DLNSGA-III算法在GD指标上表现出显著优势，其最小值、最大值和平均值的平均数分别为0.0128、0.0351、0.0231，这一结果明显优于NSGA-II算法的0.0840、0.1600、0.1210，以及NSGA-III算法的0.0971、0.1217、0.0973。此外，从图4的结果中可见，DLNSGA-III在IGD指标上同样表现优异，其最小值、最大值和平均值的平均数分别是0.0069、0.0134、0.0103，远优于NSGA-II的0.0204、0.0305、0.0247和NSGA-III的0.0171、0.0265、0.0222。然而，在图5中，DLNSGA-III的NDS指标表现出色，其最小值、最大值和平均值的平均数分别为30.9、45.57、34.775，显著高于NSGA-II的13.95、25.25、18.37和NSGA-III的15.05、23.695、19.105。这一结果表明，DLNSGA-III算法在收敛性和多样性方面优于其他两种算法。

Figure 3. GD average

图3. GD平均值

Figure 4. IGD average

图4. IGD平均值

Figure 5. NDS average

图5. NDS平均值

通过对比表2~4中的GD值和IGD值，可以看出随着案例数据规模的增大，三种算法间的性能差距也逐渐扩大。例如，在j10c5a1案例中，DLNSGA-III的GD和IGD平均值分别为0.0230和0.0175，而NSGA-II和NSGA-III的对应的值分别为0.0855和0.0226，以及0.0623和0.0203。在j50c7a1案例中，DLNSGA-III的GD和IGD平均值分别为0.0221和0.0175，而NSGA-II和NSGA-III的对应的值分别为0.1482和0.0255，以及0.1298和0.0228。这表明随着案例规模的增加，DLNSGA-III在非劣解和非支配解集上的表现更加接近理想状态，而NSGA-II和NSGA-III在这方面的差距则更加显著。

图6和图7显示，DLNSGA-III的箱线图相比于其他两种算法更加扁平，这表明其在各项指标上的方差更小，具有更好的稳定性。而图8中显示的中位线更高，表明DLNSGA-III在非劣解质量上更为优秀。

Figure 6. GD boxplot

图6. GD箱线图

Figure 7. IGD boxplot

图7. IGD箱线图

Figure 8. NDS boxplot

图8. NDS箱线图

4.2. 实例应用

某电气制造企业，其生产的避雷器设备已经广泛用于高铁输电线。本文针对避雷器中氧化锌电阻片的生产；氧化锌电阻片制造一般有9道工序：混料，造粒，成型，排胶与烧结，绝缘层喷涂，磨片，铝电极喷涂，电性能检测 [16] 。在车间的生产周期中，需要在25台机器上生产10种电阻片订单。加工能耗，加工时间，工序可选择设备等实例数据详见表5。其中混料机为M1、M2，造粒机为M3、M4，成型机为M5、M6、M7、M8、M9，排胶炉为M10、M11，烧结炉为M12、M13，侧面喷涂机为M14、M15、M16，绝缘层喷涂机为：M17、M18、M19，磨片机为M20、M21，铝电极喷涂机为M22、M23、M24，电性能检测机M25。

Table 5. Machine processing time and processing energy consumption

表5. 机器加工时间和加工消耗

由上述实验可知DLNSGA-III算法优于NSGA-II和NSGA-III，表6是三种算法的实例对比数据表，从表中可知DLNSGA-III在完工时间、机器总负荷、总能耗三项指标的对比中均优于NSGA-II和NSGA-III，进一步验证了上述实验的结果。订单经过基于DLNSGA-III算法的排产优化后，最大完工时间为14.2 h，机器总负荷为3892 KW，总能耗为186 KW/h，根据原本日产8000片电阻片的人工排产调度计划相比，订单交付率和能源利用率获得大幅提升。图9为根据DLNSGA-III所得到的调度排产甘特图。

Figure 9. Scheduling plan gantt chart

图9. 调度计划甘特图

Table 6. Example comparison experimental data table

表6. 实例对比试验数据表

5. 结论

建立以完工时间、总负载和总能耗为求解目标的问题模型，提出DLNSGA-II算法求解此问题。

基于NSGA-II算法的缺陷，结合变邻域搜索算法、弱非支配排序和精英保留策略，加强了算法的局部搜索能力、多样性和收敛性。

研究选取了20组具有不同规模的案例，采用NSGA-II、NSGA-III以及DLNSGA-III三种多目标优化算法进行求解。为了更直观、准确地对比这三种算法的性能，绘制了详细的试验结果数据表格，并通过箱线图形式展现了每种算法在各个案例中的表现。经过综合比较，可以明确观察到DLNSGA-III在求解非支配解集方面的表现优于其他两种算法。实例数据对比也验证了DLNSGA-III在电阻片车间调度排产中优于NSGA-II和NSGA-III。

从DLNSGA-III所得到的调度排产甘特图所呈现的结果说明，与原本的人工调度排产方法相比，基于DLNSGA-III算法的调度排产方法有效的提高了订单交付率和能源利用率。