钢铁企业彩涂机组合同计划问题建模与优化研究

□高 聪

一、引言

本文研究的彩涂机组合同计划是国内某大型钢铁企业中面临的实际问题，目标是协调企业内各机组之间的关系，从而优化彩涂机组的库存结构，使彩涂机组可以得到更好的调度，降低生产成本，提高生产效率。一个彩涂产品的合同需要5道主要工序才能到达彩涂机组的前库，分别为炼铁、炼钢、热轧、冷轧和热镀锌。由于生产工艺的限制，属于同一合同的板卷通常不能在机组上连续生产。这导致属于同一合同的板卷分处于各个机组的前库之中。属于同一合同且处于同一机组前库内的板卷称为该合同的子合同。

一些机组，比如热轧机组和冷轧机组，在调度方面的约束限制较少，其调度具有较大的自由度。在制定这些机组的调度计划时更多的是考虑下游各机组的物流平衡。这就给工序机组的协调生产提供了可能。前道机组参照彩涂机组提供的时间表生产彩涂机组的子合同，子合同按照彩涂机组希望的时间到达彩涂机组前库，从而达到优化彩涂机组库存结构的目的，进而降低生产成本和提高生产效率。

图1为对彩涂机组进行合同计划前后的生产时间表，（a）中显示根据子合同所在机组与机组间最小生产周期计算得到子合同对彩涂机组的最早到达时间；根据子合同最早到达时间，产生一个预调度；（b）中显示根据得到的预调度和机组间平均生产周期，倒推得到子合同在各前道机组上的理想生产时间。机组间最小生产周期是指当板卷具有最高优先级时在机组间的生产间隔时间。机组间平均生产周期为通过以往生产数据统计的板卷在机组间的生产间隔时间。

图1 彩涂机组合同计划问题示意

子合同是彩涂机组合同调度问题的基本单位，属于同一个合同的子合同除重量外的其他所有属性都相同，比如宽度、厚度、涂层颜色等。一个合同中的任意子合同拖期，则该合同拖期。若有多个子合同拖期，则该合同的拖期量等于所有子合同中拖期量的最大值。

目前，已经有很多关于钢铁工业调度问题的研究，但对钢铁企业内部多机组之间协调的研究还比较少。Okano等[1]研究了冷轧区的调度问题，并且开发了一个复杂的智能算法求解此问题。Tang和Wang[2]研究了面向在库板卷的彩涂机组调度问题，其调度对象均为在库板卷，在计算拖期惩罚时，以板卷为单位。Wang和Tang[3]研究了包含尚未到库的板卷的彩涂机组的调度问题，该研究只能被动地接受板卷的到达时间，因此轧制单元的开始时间也需要被决定，以满足生产的连续性。本文与Wang和Tang[3]研究的区别在于，本文根据彩涂机组合同计划问题的结果可以给出子合同在各个机组上推荐的生产时间，并假设子合同可以按照期望的时间完成，因此轧制单元之中不允许有空隙，且目标函数中不存在预处理费用及库存费用。

本文设计了禁忌搜索算法和变邻域算法以在合理的计算时间内求得问题的近优解。

二、求解方法

本节介绍彩涂机组合同计划问题的求解方法。首先介绍产生初始解的启发式算法，然后介绍在禁忌搜索和变邻域算法中用到的2种邻域，以及1种加速领域搜索的策略。

1.产生初始解

1个解由m个轧制单元组成，Πk为第k个轧制单元的顺序，则1个解S可表示为S={Π1,Π2, …,Πm}。令S[i]表示解S中的第i个子合同。初始解的产生方式为串行方式，即先产生第一个轧制单元，然后产生第二个，直到所有子合同都被调度。初始解启发式算法是基于贪婪思想设计的，即每次都找到与已调度的最后的子合同之间过渡费用最少的子合同加入到调度中。

2.邻域

禁忌搜索算法和变邻域搜索算法都是基于邻域搜索的算法。下面将介绍本文使用的2种邻域，即插入邻域和交换邻域，以及加速邻域搜索的策略。

（1）插入邻域

插入邻域是由在基解基础上实施插入移动得到的新解的集合。插入移动将1个子合同从原来的位置移动到一个新的位置上。在本文中，由于彩涂机组的宽度约束的限制，1个子合同在原所在轧制单元内的可移动空间非常小，插入移动通常是将1个子合同在轧制单元之间进行移动。

（2）交换邻域

1个对P(i,j)，表示1个交换移动，交换的对象是子合同S[i]和S[j]。通过对解S实施交换移动P(i,j)可以得到新解S'=Pij(S)。交换邻域Nswap为式（1）。

被交换的子合同重量上会有差异，而且由于子合同是在不同轧制单元之间进行交换，可能会导致移动涉及的轧制单元的容量溢出。修复的过程等同于插入邻域中的修复。

（3）加速策略

属于同一合同的子合同，除重量外，具有完全相同的属性。子合同间的过渡费用不涉及子合同的重量，因此属于同一合同的子合同之间的过渡费用和切换时间均为0。在交换和插入移动中，如果被移动的子合同与同属1个合同的其他子合同相邻，则此子合同不能被单独移动，而需将所有相邻的属于同一合同的子合同都一起移动。这样做的原因是将属于同一合同的子合同分开移动，对目标函数带来改进的可能性很小。另外，将属于同一合同的子合同一起移动，可以在一定程度上减少算法的计算时间。

根据彩涂机组的工艺规程，如果尝试将较窄的子合同安排在较宽的子合同之前，此移动就可以从邻域中除去，以减少邻域规模，加速搜索过程。

3.改进算法

本文设计了2种智能优化算法，禁忌搜索算法和变邻域搜索算法。下面将分别介绍这2种算法。

（1）禁忌搜索算法

由于大部分插入操作都需要被修复，因此搜索插入邻域的时间会比搜索交换邻域长很多。禁忌搜索算法中的邻域搜索是邻域Nswap。长度为TL的禁忌表被用来记录最近TL次迭代中进行移动的逆移动以防止算法陷入局部最优当中。禁忌表中的元素为形如(i,j)的对，表示对子合同i和j进行交换移动。如果邻域Nswap中的解Pij(S)被选中做为下一次迭代的基解，则对(S[i],S[j])被加入到禁忌表中，并将禁忌表中的第一个元素从禁忌表中删除。如果(S[i],S[j])或(S[j],S[i])已经存在于禁忌表中，1个移动P(i,j)被认为是禁忌的。当f(Pij(S))

邻域搜索是在邻域Nswap中找到不被禁忌的移动产生的最好解，或者尽管被禁忌但破禁的移动产生的解。禁忌搜索使用的停止准则为最大迭代次数MaxIter和最大无改进迭代次数MaxIterWI。两者任何一个被满足，禁忌搜索算法停止。

（2）变邻域搜索算法

变邻域搜索算法（Variable Neighborhood Search, VNS）是Mladenovic和Hansen[4]在1997年提出的一种超启发式算法。变邻域搜索是基于邻域搜索的，与其他基于邻域搜索的超启发式算法不同，变邻域搜索不使用kick、记忆、杂交等手段，而只是通过邻域搜索扩大算法搜索的范围，并且只有当有历史最优解被改进时算法才会前进。通过这种方式，历史最优解中好的片段和特征可以最大程度地被保留，并且被应用到新的希望邻域的搜索中。变邻域搜索的核心思想是系统地变换邻域搜索使用的邻域。目前，变邻域搜索算法已经被用来解决很多组合最优化问题[5～8]。Hansen和Mladenovic[9]对变邻域搜索的原则和应用进行了综述。本文的变邻域搜索使用了交换邻域和插入邻域。

变邻域搜索算法的详细流程如下：

——步骤1：初始化令S为初始解，Iter=0；

——步骤2;Iter=Iter+1；如果Iter=MaxIter，变邻域搜索算法结束；否则转步骤3；

——步骤3:随机选择Nswap(S)中的1个解S'；在Nswap(S')中找到邻域最优解S''，如果f(S'')

——步骤4:随机选择Ninsert(S)中的1个解S'；在Ninsert(S')中找到邻域最优解S''，如果f(S'')

三、实验结果

为了验证所提出模型和算法的有效性，本文使用了国内某钢铁企业的6组实际生产数据进行测试。数据包括所有机组前库内的属于彩涂合同的板卷信息。根据调研得到机组间的最短生产周期和平均生产周期。算法使用C语言编写，运行在Intel Core i5-10210U CPU和409 6MB内存的个人计算机上。

表1和表2给出了禁忌搜索算法、变邻域搜索算法的模拟仿真结果及企业前1年彩涂机组的平均绩效。涉及到企业技术参数的保密，表中的所有数据都被归一化。Ncw列表示颜色切换次数，Ntar列表示每千吨拖期合同个数，Vwd列表示每千吨宽度跳跃，Vtk表示每千吨厚度跳跃，WTturn表示轧制单元平均重量。表中ENP为彩涂机组的2004年平均业绩，SimTS为基于禁忌搜索算法结果的模拟仿真数据，SimVNS为基于变邻域搜索算法结果的模拟仿真数据。对禁忌搜索算法和变邻域搜索算法，最大迭代次数均为200代。禁忌搜索的最大无改进迭代次数为100次，禁忌表长度为41。由于企业只能给出机组的年平均业绩而没有问题的目标函数，且只关心实际生产指标而不关心目标函数，因此表1和表2中没有给出目标函数的对比，而只是各项指标的对比。

表1 禁忌搜索算法与模拟仿真的结果比较

表2 变邻域搜索算法与模拟仿真的结果比较

根据表1和表2的对比结果，可以得出以下结论：

（1）对目标函数中的所有指标，基于智能算法的解的模拟仿真结果均好于彩涂机组平均绩效。

（2）变邻域搜索的解在各指标上均优于禁忌搜索算法。

（3）禁忌搜索算法在计算时间上略少于变邻域搜索算法，平均少6.05%。

四、结语

本文研究了彩涂机组合同计划问题，给出了此问题的数学模型。并对此NP难问题提出了2种启发式算法，即禁忌搜索算法和变邻域搜索算法。基于2种算法产生解进行模拟仿真，同彩涂机组之前1年的平均生产成绩进行对比，证明了本文提出算法的有效性。在各个指标的对比中，变邻域搜索算法均优于禁忌搜索算法。变邻域搜索算法的计算时间较禁忌搜索算法时间稍长6.05%。目前，内嵌变邻域搜索算法的决策支持系统已经开发并在国内某大型钢铁企业中实际使用。