两阶段法求解混装模式下的加热炉调度

［摘 要］针对目前加热炉调度模型少有考虑混装模式下加热炉调度优化的不足，建立了连铸-热轧混装一体化模式下的加热炉生产调度优化模型，并提出了基于贪婪算法和模拟退火算法的两阶段求解方法。生产数据测试表明该模型和算法能有效解决加热炉调度问题。

［关键词］混装模式；加热炉；生产调度优化；多阶段决策

doi:10.3969/j.issn.1673-0194.2009.15.013

［中图分类号］TP399 ；F273.1；TB112［文献标识码］A［文章编号］1673-0194（2009）15-0042-03

1 引 言

加热炉位于钢铁生产中连铸工序和热轧工序之间，是钢铁生产中的高能耗环节［1］。目前有关加热炉的研究主要从热能的角度侧重于加热炉加热优化控制研究［2］，但对于加热炉的生产调度优化的研究相对较少［3-4］。本文以一体化模式下的加热炉优化调度为研究对象， 建立了连铸-热轧混装一体化模式下的加热炉生产调度优化的数学模型， 并应用基于贪婪算法和模拟退火算法的两阶段方法求解。加热炉生产实际数据仿真结果表明，该算法能有效求解加热炉调度优化问题。

2 混装模式下的加热炉物流分析

图1 混装模式下的加热炉调度过程

连铸-热轧混装一体化模式下加热炉调度过程如图1所示。混装模式下原料既有从连铸机产出的直装坯，也有库内板坯。其中，直装坯通过输送辊道直接进入加热炉加热；板坯库冷坯、保温坑温装坯先进入上料辊道， 然后通过装料辊道装炉。板坯入炉后， 随着在炉时间及在炉位置的前移，板坯的温度逐渐升高。最终，当板坯温度（或者在炉时间）满足要求且符合轧制计划的出炉顺序要求时，板坯出炉并由输送辊道送往轧机进行轧制。

目前常用的加热炉调度方法是根据板坯的轧制顺序和加热炉炉号顺序，依次向各加热炉分配板坯。在混装模式下沿用上述顺序装炉方式，由于没有考虑冷热板坯加热时间差异，冷热板坯混装对加热的影响等因素，将导致板坯质量下降和加热炉能耗的增加。因此，设计合理的加热炉调度方案，在满足混装一体化生产约束下，尽量缩短生产时间和减少冷热板坯混合装炉，对提高板坯加热质量和降低加热炉能耗都具有重要意义。

3 加热炉调度模型

本文研究的加热炉的调度优化问题可描述为：在连铸-热轧一体化计划已经确定的前提下决定如何将板坯分配给不同的加热炉进行加热，使得在满足连铸出坯间隔、板坯在炉时间等约束下，尽量缩短轧线生产时间和减少冷热板坯混合装炉，以节约能源、提高产品质量。根据以上描述，建立数学模型如下： 

min∑i,fn(i)∈Slabδ1×Pi,fn(i)×1S1-Sfn(i)+

∑i,hn(i)∈Slabδ2×(ei-ehn(i)-h)(1)

s.t. ei-si≥pmini, i∈Slab(2)

ei-si≤pmini, i∈Slab (3)

∑k∈FurFki=1, i∈Slab(4)

ei-efn(i)≥0, i、 fn(i)∈Slab(5)

ei-ehn(i)≥0, i、 hn(i)∈Slab(6)

ei-ehn(i)≤hmax, i、 hn(i)∈Slab(7)

si≥c i, i∈Slab, Typei=0(8)

Typei=0 直装坯1 非直装坯

Fi=0 板坯i分配给加热炉k, i∈Slab， k∈Fur1否则

式中，Fur为加热炉集合；Slab为板坯号集合；si为板坯i的开始加工时刻；ei为板坯i的实际加工完成时刻；pmini为板坯i在加热炉加工时所需的最短的额定加工时间；pmaxi为板坯i在加热炉内停留的最长时间；fn(i)为加热炉内，与板坯i直接相连的后续板坯；hn(i)为紧邻板坯i轧制的板坯；h为最短出坯间隔时间；hmax为热轧机等待加热炉出坯的时间上限值；ci为直装坯i的产出时刻；Typei为板坯类型；Fki为板坯i的入炉标记；Pij为板坯j与板坯i连续装炉的温度差异惩罚系数。

目标函数式（1）表示加热炉调度的优化目标为加热惩罚与轧线等待惩罚总费用最小，其中第一项为连续装炉板坯温度差异的惩罚费用；第二项为由于板坯未能按时提供轧线所需的板坯从而导致轧线空闲的惩罚费用，δ1、δ2为上述两惩罚项的权重。约束（2）表示板坯在加热炉内的实际加工时间不少于最短额定加工时间；约束（3）表示板坯不能在加热炉内停留时间过长；约束（4）表示每块板坯都被分配而且只被分配到一个加热炉加工；约束（5）表示在同一加热炉中加工的板坯先进入炉的先进热轧；约束（6）表示板坯在热轧机轧制前一块板坯时一直在加热炉中停留；约束（7）表示热轧机的空闲时间不超过一个预先设定的值；约束（8）表示直装板坯的入炉时刻必须大于其连铸出坯时刻。 

4 算法设计

加热炉调度优化问题属于NP-hard问题［3］，采用随机搜索方法，容易产生非可行解，且求解速度较慢。为了避免上述缺陷，本文应用两阶段求解方法：在第一阶段，应用基于贪婪算法和时间回溯的启发式方法确定可行的设备指派方案；在第二阶段，应用模拟退火算法，调整板坯与加热炉炉号的匹配，最终寻找优化的调度方案。

4.1 初始解生成

本文采用了交货期最早优先（Earliest Due Date，EDD）指派规则，根据轧制顺序按从小到大排列，依次求解各板坯的入炉时间和炉号。

首先定义变量［i］为第i块轧制的板坯。求解步骤如下：

Step 1：按轧制顺序由小到大排列板坯。

Step 2：随机安排第一块轧制的板坯的入炉炉号，确定入炉时间s［1］=0，最佳出炉时间e［1］=pmin［1］，及出炉时间窗［pmin［1］, pmax［1］］。i=2。

Step 3：依次计算板坯［i］安排到k （k=1，…，M）加热炉后的目标惩罚值。若炉群满足约束，则选择目标值最小的炉号为入炉炉号，确定相应的入炉、出炉时间窗，及最佳入炉、出炉时间，进入Step 5。否则，进入Step 4。

Step 4：采用时间顺序回溯策略，选择板坯［i-1］的次优加热炉，重新指派板坯的入炉炉号及加工时间；当遍历所有加热炉，仍然找不到［i］板坯的合适解，回溯板坯［i-2］，依次类推；如果回溯到起始板坯仍然找不到合适解，则在该启发式方法下无解，结束循环。

Step 5：i=i+1，执行Step 3，直到所有板坯安排完毕。

4.2 解的改进

本文应用模拟退火算法，以第一阶段的可行解作为初始解，通过板坯交换和插入算子，调整板坯与加热炉的组合，从而寻找优化调度方案。具体方法描述如下：

Step 1：初始化参数n=0，c=0，k=0，当前温度tmax=tk；

Step 2：若n＞N1（N1为该温度下总循环次数），或c＞N2（N2为该温度下无改进解的累计次数），或板坯遍历完毕，则转Step 6；否则，随机选择要交换的板坯［i］（定义其入炉时间窗定义为［S［i］, S［i］］），并确定其邻域U为：与［i］的入炉时间窗交集不为空的板坯集合。

Step 3：当U≠，则从领域中随机选择一邻居［j］，转Step 4；否则，令n=n+1，转Step 2；

Step 4：若［S［j］, S［j］］［S［i］，则计算板坯［i］与［j］交换后的目标函数改进量Δf；若［S［j］, S［j］］［S［i］, S［i］］或［S［j］, S［j］］［S［i］, S［i］］，则判断［i］插入到［j］前后或［j］插入到［i］前后的目标函数改进量Δf。若Δf≤0，则执行相应交换或插入操作，记录当前最优解；否则当e-Δf/tk≥rand(1)，（rand(1)表示一个0 到1 之间的均匀随机数），执行交换或插入。

Step 5：若板坯［i］与板坯［j］没有执行交换或插入操作，令U=U-{［j］}，重复Step 3~Step 4；否则，n=n+1，若目标函数值非减，则令c=c+1，否则，c=0，进入Step 2。

Step 6：若连续N3次降温均没有出现改进解，输出最优解，算法停止；否则，令n=0，c=0，k=k+1，tk=α×tk-1，转Step 2。

5 数据验证

本文采用了由120块板坯组成的一体化计划，分别应用以下算法进行测试：基于顺序入炉规则的传统调度方法，基于贪婪算法的求解方法，本文提出的二阶段优化求解方法。实验结果如表1所示。

从测试结果可以看出：采用传统的顺序入炉方式，由于其没有考虑冷热板坯同炉加热对板坯质量和加热节奏的影响，通过公式（1）计算的目标惩罚值很高，不适合作为混装模式的生产组织形式；基于贪婪算法的求解方法一定程度上优化了装炉效果；采用本文提出的两阶段求解方法，目标惩罚值最小，求解效果最好。此外，从运行时间上看，两阶段法的求解速度完全能够满足现场生产调度的要求。

表1仿真实验结果

优化方式

运行结果

顺序入炉贪婪算法二阶段方法

总加工时间（min）550528473

温度最大跳跃（℃）450280100

目标函数值5 6364 9893 530

运行时间（s）6.48.817.8

6 结 论

本文针对混装一体化生产物流的特点，建立了混装模式下的加热炉生产调度模型。为便于求解，首先构造了基于贪婪算法和时间回溯算法的启发式方法，从而提高了可行解的求解速度；在第二阶段，基于模拟退火方法，设计了板坯交换和插入算子，快速实现了解的优化。实例计算证明该算法能及时有效求解混装模式下的加热炉调度优化问题。

主要参考文献

［1］ Tang LX, Liu JY, Rong AY, Zhou YH. A Review of Planning and Scheduling Systems and Methods for Integrated Steel Production ［J］. European Journal of Operational Research, 2001,133(1):1-20.

［2］ 安月明,温治. 步进梁式板坯加热炉数学模型及其仿真系统［J］. 系统仿真学报, 2006,19(12):2827-2830.

［3］ 宁树实,王伟,刘全利. 钢铁生产中的加热炉优化调度算法研究 ［J］. 控制与决策, 2006,21(10):1138-1142.

［4］ 李婧,李苏剑. 加热炉炉群生产物流仿真系统的设计和实现［J］. 钢铁, 2001,36(8):52-55.

A Two Stage Method for Optimal Scheduling Problem of Reheating

Furnace in Hybrid Charge Mode Production

LIANG He-lan1, LI Su-jian1, DENG You-hao2

(1.Department of Logistics Engineering, School of Mechanical Engineering, University of Science and Technology

Beijing, Beijing, 100083, China; 2.Shougang Qian’an Iron & Steel CO., LTD., Hebei, 064404, China)

Abstract： Focusing on the limitations of traditional optimal scheduling methods of reheating furnace that seldom consider the optimization for hybrid charge mode production, an optimization model for furnace scheduling problem of hybrid charge mode is formulated, and a two-stage combination method composed of both greedy and improved simulation anneal algorithm is put forward for solving the problem. Test with data from practical production process shows that the proposed method is suitable for practical production.

Key words: Hybrid Charge Mode; Reheating Furnace; Scheduling Optimization; Multi-stage Decision