考虑丢单的改进热轧调度问题研究

吴曈 谭园园

摘要：本文对热轧调度问题进行研究，在热轧调度的研究中，加入了丢单的考虑。问题为三目标优化问题，采用人工蜂群算法（ABC）进行问题的求解。在文中给出了人工蜂群算法解决问题的三个改进方案，通过丢单优化、重构优化和禁忌搜索优化来提升算法的性能，以提获得精度更高，更加优质的优质解。在此基础上，设计了两组对比仿真实验，分别为：丢单未丢单对比仿真实验和人工蜂群算法改进前后的对比实验。借此验证了丢单的有效性和改进的有效性。

关键词：热轧调度;订单丢单;改进人工蜂群算法;多目标问题;组合优化

中图分类号：U692.4+3  文献标识码：A

文章编号：1009-3044（2021）29-0174-04

Research on the Improved Hot Rolling Scheduling Problem with Lost Orders

WU Tong， TAN Yuan-yuan

（College of Artificial Intelligence， Shenyang University of Technology， Shenyang 110870， China）

Abstract： In this paper， the hot rolling scheduling problem is studied. In the hot rolling scheduling research， the consideration of losing orders is added. The problem is a three ective optimization problem， which is solved by artificial bee colony algorithm （ABC）. In this paper， three improved schemes of artificial bee colony algorithm are given to solve the problem， which can improve the performance of the algorithm through order loss optimization， reconstruction optimization and tabu search optimization， so as to obtain higher accuracy and better quality solutions. On this basis， two groups of contrast simulation experiments are designed， which are： the contrast simulation experiment before and after the improvement of artificial bee colony algorithm. The effectiveness of the lost order and the effectiveness of the improvement are verified.

Key words： hot rolling scheduling; lost orders; mproved artificial bee colony algorithm; multi-ective problem; combinatorial opti?mization

1背景

进入新时代以来，我国对于钢铁的需求也不断提升，包括钢铁的产量和钢铁的质量。对我国钢铁企业来说，钢铁行业的现状既是机遇，也是挑战。钢铁行业的重要产业之一是钢铁炼制，炼制过程是否能够有序顺利的进行，会对钢铁炼制企业的盈亏产生巨大的影响[1]。钢铁的加工主要包括三个过程，分别为炼钢、连铸和热轧[2]。热轧是整个加工的最后过程，合理的热轧调度能够有效提高生产效率和资源利用率，其重要程度也可想而知。

虽然目前存在大量对热轧调度进行的研究，但对于考虑丢单问题的热轧调度十分匮乏[3]。文献[4]研究了钢铁一体化的调度问题，研究内容中包含热轧调度问题，设计了遗传算法来求解热轧调度问题，未考虑丢单问题。文献[5]同样采用了遗传算法作为主算法，该文献以宝钢某生产线为背景，进行了热轧调度优化尝试，同样未考虑订单丢单问题。文献[6]研究了开放车间的调度问题，目标为最大化利润，采用了改进人工鱼群算法。文献进行建模时，加入了订单丢单约束，对满足特定要求的工件进行丢单处理，通过实验验证了加入丢单处理后，能够获得更大利润。文献[7]说明了有些丢单并不是一个明智的做法，该文献系统地分析和阐述了有些丢单操作不仅不能提高所获得的利润，还会让企业利润下滑。因此，盲目丢单并不可取，只有合理的丢单，才能达到预期的效果。本文提出了在热轧调度中加入了丢单的考虑，使钢铁企业能够通过合理丢单获得更高的经济效益和时间效益。同时还设计了改进人工蜂群算法进行问题的求解，三种改进的加入也大幅度地提高了算法的性能，增加了求解的精度。

2问题描述

考虑一批包含n个工件 J ={1， 2， 3， ...， n}的订单集合，加工机器为一台，每个工件在加工期内仅需进行一次加工，机器同一时刻只能加工单一工件。每个工件的加工有各自的要求，分别包括宽度要求、厚度要求和硬度要求，其中的宽度、厚度以及硬度表示每个工件在加工后需要达到的外形标准。每个工件也有各自的属性，分别为所需加工时间属性、工件价值属性和工件信誉度属性，其中加工时间表示工件加工所需的时间，工件价值表示加工工件能获得的经济效益，工件信誉度表示工件丢单后损失的信誉值。本文包括如下假设：每个工件之间相互独立;任一工件加工均不可中断;工件加工无需准备时间，且均可在零时刻开始加工。

机器加工过程中轧辊会产生相应的磨损，轧辊产生磨损会对工件的质量产生影响。未更换轧辊情况下，连续加工时间越长，工件质量越差，工件价值越低，为了降低这种影响，机器需要进行更换轧辊。另外，机器加工过程中会存在惰化效应和机器坏损，这也会对机器的加工效率产生影响。未进行维护情况下，连续加工时间越长，机器惰化效应越明显，机器加工效率越低，工件所需加工时间越长。为了降低这种影响，机器需要进行预防性维护。本文研究的问题考虑如下优化目标：经济成本目标、时间成本目标和信誉成本目标。

3数学模型

引入以下符号：n表示总工件订单数量;F为经济指标;tj和cj分别为工件j加工的起始时间和结束时间;Xi为工件信誉度; gj1，j2表示工件j1是否在工件j2前加工;tw表示单次更换轧辊所需时间; cv表示单次机器维护所需时间;m 为轧制单元个数;o 为

维护区间个数; w表示工件j加工后是否进行第k 次更换轧辊;vqj表示工件j加工后是否进行第q次维护;pj表示工件j加工时间;dhj表示工件订单j加工前最近的机器维护结束时间;Sf为丢单工件订单集合;So表示未丢单工件集合;Xj表示工件信誉度;dmj为丢单决策变量，为0表示工件不丢单，为1表示工件丢单;pd表示丢单比率最大值;tzk为更换轧辊起始时间;dzk为更换轧辊结束时间;tcp为机器维护起始时间;dcp为机器维护结束时间。

针对本问题，建立如下数学模型：

式（1）为最小化经济成本;式（2）为最小化最大完工时间;式（3）为最小化信誉成本;式（4）为最大丢单数限制;式（5）为工件j 的加工起始时间;式（6）为工件j 的加工结束时间;式（7）为更换轧辊起始时间;式（8）为更换轧辊结束时间;式（9）为机器维护起始时间;式（10）为机器维护结束时间。

4算法及改进

算法流程主要包括以下九个部分，分别为编码方式、解码方式、丢单设计、初始解生成、重构设计、机器惰化效应设计、求解目标及优势蜜源选择、深度搜索设计以及最优解保留策略，主要进行编码方式和机器惰化效应设计的介绍。改进方式分别为：丢单优化、重构优化以及禁忌搜索优化。

4.1编码方式

本文的编码包含两类，分别为：丢单工件编码和加工信息编码。丢单信息编码采用实数编码，丢单信息编码采用实数编码结合0-1编码方式。

其中加工信息编码如下：

加工信息编码为三位一组，三位按照顺序分别为：加工顺序位、更换轧辊位和机器维护位。图1 中的编码则表示加工顺序为1-5，且在工件5后进行更换轧辊，工件1后机器维护。

4.2机器惰化效应设计

本文中的机器会随着连续加工时长而产生惰化问题，即机器连续加工时长越长，机器加工效率越低，如图2所示。

4.3丢单优化

在标准算法中，设定丢单选择是无向随机的，即任一工件订单被选中丢单的概率都是相同的。然而在实际生产中，每个订单都有自身独特的属性，这种属性的不同使得每个订单所带来的净效益也不相同。在丢单的选择上，可以通过计算为每个订单设计一个丢单值，再据此来设计每个订单被选中丢单的概率。

设定工件丢单值符号表示为DDZ，DDZ值越高工件越容易被丢单，为了计算DDZ值，可以将其拆分为三类指标分别进行计算，这三类指标分别为时间指标、经济指标和信誉指标，符号表示分别为SD、XD和JD。

时间指标 SD 以及信誉指标XD 可以分别用式（11）和式（12）進行计算，式中的SJi和XYi分别表示工件i的加工时间和信誉值，So表示进行加工的工件集合。

经济指标JD 内包含三个子指标，分别为工件价值指标、工件硬度指标和工件宽度厚度联合指标，符号表示分别为JZD、 YDD 和KHD。其中工件价值越大，工件丢单值应越低，所以首先需要对工件价值做反向处理，如式（13）所示，式中的JZj表示工件j 的价值：

其中FJZ表示反向价值，JZ表示工件价值，为防止出现0的情况，在尾端进行加一处理。在此基础上，工件价值指标可以由式（14）计算得出：

工件硬度指标在计算中，首先将工件硬度根据表3.2进行量化处理，工件硬度指标反映测算工件在全部工件中硬度的差别度，需要计算测算工件到其他所有工件的距离之和同所有工件到其他工件距离之和占比，随后由式（15）来进行计算，式中的YDi表示工件i的硬度量化值：

工件宽度厚度联合指标可以由式（16）进行计算，式中的KDi和HDi分别表示工件i的宽度值和厚度值：

最后将这些指标按照式（17）融合并进行归一化处理，得到了丢单值：

4.4重构优化

重构指的是，在同一轧制单元内，对工件进行重新排产，以使得不可行解变为可行解。在实验中选择了其中最优的重构方式作为优化后的重构方式来完成算法的求解。

对于信誉成本来讲，重构方式并不会影响结果;对于时间成本来讲，由于重构调整均于同一轧制单元内，时间成本也不会受到影响。所以，只有经济成本会受到重构方式的影响。经济成本中，能够受重构方式改变影响的仅有宽度、厚度和硬度跳变所带来的电力成本大小。进一步分析，重构方式对厚度和硬度跳变所带来的电力成本大小的影响是随机的，所以这部分影响同样不考虑。最终，重构方式在理论上仅会对宽度跳变成本产生非概率性影响。

宽度跳变成本中，上升重构和下降重构单个轧制单元中宽度跳变累加值为当前轧制单元中宽度最大值同宽度最小值的差，而极大值重构的宽度跳变累加值永远大于等于上升重构和下降重构的该值。另外，为了提高解的多样性，最终选择上升下降重构为改进后的重构方式。

4.5禁忌搜索优化

禁忌搜索可以使解的搜索避免产生回路，为了提升算法效率，本文设计了禁忌搜索同人工蜂群相结合的方法来提升算法性能。

为了解决禁忌表消耗内存过大问题，设计了简化禁忌表。在简化禁忌解的记录中，只保存蜜源中的变化部分，未变化部分则不予记录。

对于记录部分来说，有两类信息，一个是在蜜源中的位置信息，也称为信息位;另一个是其内部的数据信息，也称为数据位。如图3所示：

在该简化禁忌解中，为了区分位置和数据两类信息，将位置信息均取其相反数，由于存在-1作为是否更换轧辊以及是否进行机器维护的判别数，位置信息会反向增加一个数量为1 的偏差数，如-4代表位置偏移量为3。除此之外，-2表示前后两数据位置相邻，为了简化数据长度，将-2省略。上图的简化禁忌解中，第一位为3，为数据位，蜜源第一位存在变动，变动后的数据信息为3;简化禁忌解第二位为-4，小于-1，为位置位，表示3位的偏移;第三位为8，为数据位，结合上一位-4的3位偏移量，蜜源第四位存在变动，变动后的数据信息为8;禁忌解第四位为0，为数据位，数据位相连，说明省略位置位-2，所以蜜源第五位存在变动，变动后的数据为0。以此类推，结合初始蜜源，可得出该简化禁忌解所表示蜜源的完整信息。

5实验及仿真结果

本文通过国内某钢厂的真实算例，来完成实验仿真。图4为考虑丟单和未考虑丢单实验结果仿真图。由于未丢单不存在信誉成本，因此对比实验为双目标。

图中三角形为无丢单状态下的优质解，十字符为有丢单状态下的优质解，有丢单状态下的优质解在经济成本和时间成本上均优于无丢单状态下的优质解，因此说明丢单存在效果，验证了丢单的有效性。

表2和表3分别为考虑丢单情况下，标准人工蜂群算法和改进人工蜂群算法在规模为150、200和250情况下进行10组同算例的平均值结果对比表和方差结果对比表。表2中可以看出，标准人工蜂群算法在三个指标的平均值上均大于改进人工蜂群算法，这也说明了改进后的人工蜂群算法在性能上优于标准人工蜂群算法;表3中可以看出，标准人工蜂群算法在三个指标的方差上均大于改进人工蜂群算法，这也说明了改进后的人工蜂群算法在稳定性上优于标准人工蜂群算法。表中还表明，无论规模大小，改进人工蜂群算法均优于标准人工蜂群算法，说明改进存在效果，验证了改进的有效性。

6结论

热轧是整个加工的最后过程，合理的热轧调度能够有效提高生产效率和资源利用率，本文对热轧调度进行研究并进行实验仿真，得到了如下结论：

1）通过仿真实验验证可知，在考虑丢单问题后，实验结果无论在经济成本还是在时间成本上，均优于未考虑丢单问题的情况。因此丢单能够更好地提高解的质量。

2）通过仿真实验验证可知，在进行了丢单优化、重构优化以及禁忌搜索优化后，实验结果无论在经济指标、时间指标还是信誉指标的均值和方差上，均优于标准人工蜂群算法。因此可以认为改进存在效果，能够有效提升算法精度和稳定性。参考文献：

[1] He Y， Liao N， Rao J， et al. Energy conservation path of China iron and steel industry driven by relative policies[J].Energy Ef⁃ ficiency，2021， 14（1）：14-16.

[2]黄辉，罗小川，郑秉霖，等.炼铁-炼钢区间铁水重调度方法及其应用[J].系统工程学报，2013，28（2）：234-247.

[3] Viana M S， Junior O M， Contreras R C. A modified genetic al⁃gorithm with local search strategies and multi-crossover opera⁃ tor for job shop scheduling problem[J]. Sensors， 2020， 20（18）：32-35.

[4] Tang L， Liu J， Rong A， et al. A review of planning and sched⁃uling systems and methods for integrated steel production[J]. European Journal of Operational Research， 2001，133（1）：1-20.

[5]王冰.热轧生产计划优化方法的研究与应用[D].大连：大连理工大学，2005.

[6] Sheikhalishahi M， Eskandari N， Mashayekhi A， et al. Multiective open shop scheduling by considering human error and preventive maintenance[J]. Applied Mathematical Model⁃ ling， 2019， 67（4）：573-587.

[7]刘峰源.从一则案例说说那些"本不该丢掉"的订单[J].印刷技术，2019，742（10）：52-54.

【通联编辑：梁书】