基于改进的NSGA2算法求解锻件装炉组合问题多目标优化

Multi-Objective Optimization of Forging Furnace Loading Combination Problem Based on Improved NSGA2 Algorithm

摘要: 锻件加热工序是锻造车间生产线的重要一环。本文将针对不同类型锻件同时到达下的共同装炉问题，考虑装炉的重量、尺寸约束以及同炉加工工艺的约束，并且建立多个优化目标包括最小炉批次数量、最小装炉尺寸差、最大平均装炉量以及最小平均加热保温时间为能耗优化的评价体系从而建立模型，并进行仿真实验，本文用通过优先级策略改进NSGA-II算法对所提出的算例进行求解，从而验证了算法模型的良好寻优效果，为不同类型的锻件共同装炉问题提供参考。

Abstract: The forging heating process is an important part of the production line of the forging workshop. This paper will focus on the problem of common furnace loading when different types of forgings arrive at the same time, considering the weight of the furnace, the size constraints and the constraints of the same furnace processing technology, and establish multiple optimization objectives including the minimum number of furnace batches and the minimum furnace size difference. The maximum average furnace load and the minimum average heating and holding time are the evaluation systems for energy consumption optimization to establish a model and conduct simulation experiments. In this paper, the proposed example is solved by improving the NSGA-II algorithm through the priority strategy. The good optimization effect of the algorithm model provides a reference for the problem of common furnace loading of different types of forgings.

1. 引言

自由锻造车间主要工序为利用加热炉对锻件进行加热，接着在锻压机上完成镦粗、拔长、芯棒拔长、冲孔、扩孔、马架扩孔、弯曲、剁切等工步，其中根据加工工艺要求可能会存在多次的锻件重入加热炉加热，在锻造达到工艺标准后再进行热处理、粗精加工等工序。在此诸多工序中锻前加热为锻造加工工艺中的重要一环，在实际生产中经常会面临不同类型的锻件生产订单，因此涉及到不同类型锻件的共同装炉加工问题，这是要将锻件按照一定的组批方式同时装炉进行加热，因而属于一种经典的组合优化问题，该问题的求解直接关系到加热工序的能耗目标以及整体锻造生产调度的效率。

2. 文献概述

目前，锻件装炉问题已经得到了广泛的研究。何非等 [1] 给考虑锻坯形状和尺寸对加热时间的影响，采用遗传算法求解以目标函数为锻坯装炉容量差率来建立的装炉节能调度模型。最后通过实验算例验证了锻件装炉节能调度模型以及其求解算法的有效性。韦勇等 [2] 针对单层并排式装炉方式的装炉问题进行研究，以装炉容量差最小化为目标建立模型，最后通过举出算例并用遗传算法进行求解得出最节能化装炉方案。Jaklic等 [3] 通过研究锻坯之间的间隙大小对加热炉生产效率的影响，并针对多种不同规格的坯料进行了仿真实验模拟，根据对流传热以及辐射传热效率进一步优化了步进连续炉的加热效率。沈康等 [4] 针对不同锻坯混合装炉形式进行了分别建模，两种不同模型都以锻件装炉体积、数量最大化为优化目标进行求解。朱柏青等 [5] 基于动态聚类方法先对待加工锻件进行聚类分析，建立多背包模型，运用离散混合蛙跳算法对加热炉装炉多背包模型进行求解并通过算例验证。柳晶 [6] 等从锻件装炉、锻件出炉、锻件锻打和热处理过程等多个方面以节能优化为目标对调度方案进行了研究。

本文将针对不同类型的锻件的分批装炉问题进行研究，在各类型锻件的数量、尺寸、重量、加热温度区间以及加热时长区间已知的情况下，根据同炉加热规则以及各项约束，建立多目标的锻件装炉组合优化模型，并用基于优先级策略的改进NSGA-II算法求解，优化并得到锻件的最优组批方案。

3. 锻件装炉组合优化模型

3.1. 问题描述

锻造车间现有M种锻件类型，总共有N个锻件，每种类型锻件的数量、重量、尺寸已知，允许保温的温度区间以及允许保温的时间区间也均已知。实际生产中制定方案需要将待加工锻件分为多个炉批次，并且每个炉批次就是作为一个加热炉的一次加工任务进行加热保温工序。加热炉的最大承重能力以及最大横向尺寸均已知，在进行加热保温工序前要先对加热炉进行加热到的使其温度必须满足加热炉内所有待加工锻件的保温温度要求，一个加工任务最终的保温时间也必须满足炉内所有锻件的保温时间工艺要求。通过总炉批次数量、平均装载量、平均加热保温时间以及平均装炉尺寸差为衡量能耗情况的综合评价指标，因此优化的目标为多目标包括最小炉批次数量、最小平均装炉尺寸差、最大平均装炉量以及最小平均加热保温时间。

锻件组批同炉加热 [7]：如果待加工锻件之间能够同时满足保温温度以及保温时间有交集(即交叉集合不是空集)，则可以称锻件之间满足同炉加热规则，即在分批组合时可以放入同一炉批次进行加热；否则如果至少有一个锻件无法满足同炉加热的要求，那么在分批组合时这些待加工锻件不能放入同一任务批次进行加热保温工序。

3.2. 模型建立

3.2.1. 基本假设

假设：

1) 每个锻件只能被分到一个炉批次中。

2) 锻件的工艺要求可能会有若干火次，即加工工艺要求在锻压工序后重新入炉进行加热工序，多次反复，然而锻件的加工工艺温度区间、加热时间以及锻件的出炉温度始终保持不变，因此我们假设它是一个连续加热的过程，忽略多火次影响；

3) 一个炉批次同时入炉并同时加热，在未达到工艺要求前不允许中断，即锻件在达到最终的加工工艺要求之前，不能从加热炉中取出，也不允许向炉中加入新的加工任务。

4) 后道工序加工能力充裕。

5) 待加工锻件的最大重量不会超过加热炉的最大承载重量。

6) 锻件组批装炉采取二维并排装炉方式，加热炉的高度以及内深均能满足所有锻件的要求。

7) 加热炉加热保温能力足以满足所有锻件的工艺要求。

3.2.2. 主要参数及定义

n：锻件数量；

k：炉批次数量；

J：锻件集合， $J=1,2,\cdots ,n$ ；

B：炉批次集合， $B=1,2,\cdots ,k$ ；

J：件序号， $j\in J$ ；

B：炉批次序号， $b\in B$ ；

$J_b$ ：炉批次b里的锻件集合；

$Z_j$ ：锻件j的重量；

$Z_b$ ：炉批次b的重量；

S：加热炉最大承重；

$O_j$ ：锻件j的横向最大尺寸；

$O_b$ ：炉批次b的累积横向最大尺寸；

M：加热炉所允许装炉的最大横向尺寸；

$T_{j\max }$ ：锻件j的保温温度区间的上限；

$T_{j\min }$ ：锻件j的保温温度区间的下限；

$T_b$ ：炉次b在加热炉里的保温温度；

$C_{j\max }$ ：锻件j的保温时间上界；

$C_{j\min }$ ：锻件j的保温时间下界；

$C_b$ ：炉次b在加热炉里的保温时间；

$K_{lb}$ ：炉批次总数量的下界；

$x_{jb}$ ：决策变量，锻件j是否属于炉批次b。

3.2.3. 数学模型

$\min \left(k\right)$ (1)

$\min \left(y\right)=\min \left(\frac{1}{k}{\displaystyle {\sum }_{b=1}^k\left(M-O_b\right)}\right)$ (2)

$\min \left(p\right)=\min \left(\frac{1}{k}{\displaystyle {\sum }_{b=1}^k\left(S-Z_b\right)}\right)$ (3)

$\min \left(C\right)=\min \left(\frac{1}{k}{\displaystyle {\sum }_{b=1}^k{C}_b}\right)$ (4)

${\displaystyle {\sum }_{b\in B}{x}_{jb}}=1,j\in J$ (5)

$\left|{\displaystyle {\sum }_{j=1}^n{Z}_j/S}\right|\le K\le n$ (6)

$Z_b={\displaystyle {\sum }_{j\in J}{x}_{jb}{Z}_j}\le S,b\in B$ (7)

$O_b={\displaystyle {\sum }_{j\in J}{x}_{jb}{O}_j}\le M,b\in B$ (8)

${\displaystyle {\cap }_{j\in J_b}\left[T_{j\min },T_{j\max }\right]}=\varnothing ,b\in B$ (9)

$T_b=\max \left\{T_{j\min }\right\},j\in J_b,b\in B$ (10)

${\displaystyle {\cap }_{j\in J_b}\left[C_{j\min },C_{j\max }\right]}=\varnothing ,b\in B$ (11)

$C_b=\max \left\{C_{j\min }\right\},j\in J_b,b\in B$ (12)

$x_{jb}=\{\begin{array}{l}1,锻件j属于批次b\\ 0,否则\end{array},j\in J,b\in B$ (13)

其中：

式(1)~(4)为目标函数，分别表示为最小装炉批次数、最小平均横向尺寸差、最小平均装炉差值以及最小平均保温时间；

式(5)~(6)为装炉分批约束，分别表示为每个锻件j只能被分配到一个炉批次b中以及炉批次数量的范围；

式(7)表示一个加工批次的锻件总重量不能超过加热炉的最大承载量；

式(8)表示一个加工批次的锻件总的横向尺寸不能超过加热炉的最大允许装炉横向尺寸；

式(9)表示一个加工批次中的所有锻件的保温温度区间必须有交集，且不能为空；

式(10)表示一个加工批次在加热炉中的最终温度为满足炉内所有锻件保温温度区间工艺要求下的最低值；

式(11)表示一个加工批次中的所有锻件件的保温时间区间必须有交集，且不能为空；

式(12)表示一个炉批次在加热炉中的最终保温时间为满足炉内所有锻件保温时间区间工艺要求下的最低值；

式(13)为决策变量。

4. 基于优先级策略改进NSGA-II算法

多目标优化问题是车间调度常见的研究问题，有许多学者对多目标优化问题进行了研究，并且运用了多种不同的多目标优化算法，例如张守京 [8] 等通过分析柔性车间调度问题特点提出了改进的遗传算法(Non-Dominated Sorted Genetic Algorithm-II, NSGA2)的调度方法求解该问题。袁帅鹏 [9] 等为了克服传统帕累托支配法的择优策略的缺陷，其中特别是在解决离散问题时容易忽略掉有用信息，针对该缺陷提出了基于自适应网格法的择优策略去改进带精英策略的快速非支配排序遗传算法。本文借鉴参考文献 [10] 所提出一种基于优先级策略来改进NSGA2算法来对模型进行求解。

4.1. 目标优先级策略

结合实际生产要求，本文共提出了4个优化调度目标：用 $f_1$ 表示最小装炉批次数；用 $f_2$ 表示平均保温时间最小；用 $f_3$ 表示平均装炉差值最小；用 $f_4$ 表示平均装炉横向尺寸差值最小。并且根据各目标函数的重要性不同，按优先级等级从高到低排序为： $f_1$， $f_2$， $f_3$， $f_4$。

4.2. 算法步骤

步骤1：参数初始化，初始化编码随机产生初始种群 $Q_0$，最优个体best从中任选一个出来。

步骤2：进入迭代，对种群 $Q_0$ 进行非支配排序并计算个体的拥挤度。

步骤3：从种群中选择相应数量的个体分别进行遗传操作得到的新种群 $p_{it}$ 与原种群形成二倍种群 $R_{it}$。

步骤4：从二倍种群 $R_{it}$ 中挑选出重复的个体，进行交叉操作，并用用新的个体代替重复个体。

步骤5：通过优先级策略的比较排序方法对种群 $R_{it}$ 个体进行排序，挑选出排在前面的个体组成下一代种群 $Q_{it+1}$，记最优个体为 $bes{t}_0$。

步骤6：将两个种群间的最优个体进行比较，如果 $bes{t}_0$ 优于当前的最优个体best，那么 $bes{t}_0$ 就为当前的最优个体。

步骤7：通过判断最大迭代次数是否已达到来进行下一道步骤，若达到则执行步骤8否则执行步骤2。

步骤8：最终输出最优个体。

5. 实验分析

5.1. 算例参数设计

我们以某锻造厂的某实际生产计划中针对多订单任务锻件装炉分批组合为例。已知待加工锻件信息表中总共有15种不同的待加工锻件类型，并且且每个锻件类型的数量、尺寸、质量均已知、加工工艺标准所要求的保温温度区间以及保温时间区间也已知。在制定分批组合方案时要充分考虑不同类型的锻件能否同炉加热，即遵循上述所提到同炉加热规则，除此之外要考虑的约束有炉批次重量不能超过加热炉的最大承重，炉批次最大横向尺寸不能超过加热炉规格。已知加热炉最大承载重量为8000 kg，最大允许横向装炉尺寸为5000 mm。本文采用基于优先级策略的改进NSGA2进行优化求解对算例进行求解。其算法参数设置为：交叉概率为0.8，变异概率0.2，迭代次数为1000，种群大小为80。当迭代次数达到最大迭代次数时，算法结束并输出最优解。已知待加工锻件信息表如表1所示：

Table 1. Information table of forgings to be processed

表1. 待加工锻件信息表

5.2. 实验结果

运行结果包含各炉批次的锻件数量、总装载重量、总横向尺寸数值、各炉批次的炉内温度和保温时间以及各类型锻件的具体组批方案。组批方案包括各类型待加工锻件的数量。本文分别用传统的NSGA-II算法以及基于目标优先级策略改进的NSGA-II算法对算例进行求解，最终优化前后的NSGA-II算法运行结果如表2、表3所示，改进前后算法运算结果目标值的对比如表4、表5所示。

从实验结果的目标值对比可以看出改进后的NSGA-II算法求解所得到的运行结果的总炉批次数比优化前求解结果更小，同时平均装载量差值以及横向尺寸差值都得到了更优结果，改进后的NSGA-II算法求解所得到的平均加热保温时长虽然有所增大，但因为炉批次数有所降低，由平均加热保温时长与炉批次数进行相乘计算可以得出总加热保温时长，通过对比我们发现总的加热保温时长还是缩短的，因此通过这四类综合评价指标可以得出优化后求解出的组合方案总能耗更低。另一方面也验证了基于优先级策略优化的NSGA-II算法对所提出的模型以及算例求解的有效性。

Table 2. Calculation results based on NSGA-II

表2. 基于NSGA-II的运算结果

Table 3. Calculation results based on improved NSGA-II

表3. 基于优先级策略的NSGA-II的运算结果

Table 4. Comparison of the target value of the algorithm calculation result before and after the improvement

表4. 改进前后算法运算结果目标值的对比

Table 5. Comparison of the total heating and holding time of all heating furnaces

表5. 所有加热炉总的加热保温时长的对比

6. 结束语

本文结合实际讨论了在锻造车间生产中面临的多种不同类型的锻件在同一时间段到达下的组批装炉问题，并且为了更贴合实际，在建立模型时充分考虑了装炉的重量约束、尺寸约束以及共同装炉下的温度区间以及时间区间工艺要求的多约束情况，并以装炉批次数、平均装炉尺寸差、平均装炉量以及平均加热保温时间作为综合评价指标建立了多目标优化模型，采用通过优先级策略改进的NSGA-II算法对算例进行求解，得到了多类型锻件共同装炉的最优组批方案，并将改进前后算法的运行结果进行了求解目标值上的对比，验证了改进优化策略后算法的有效性。本研究为锻造车间调度中的多类型锻件共同装炉问题提供理论指导，在实际应用方面决策者可以基于不同的锻件类型数据得到装炉问题的最优组批方案，因而也具有实际意义。