基于优化调度模型的焦炉推焦计划编制方法
蔡 雁，吴 敏，杨 静，曹卫华
(中南大学 信息科学与工程学院，湖南 长沙，410083)
摘 要：针对焦炉正常和异常2种工况，提出基于优化调度模型的焦炉作业计划编制方案。在正常工况下，建立使设备总的机械行程最短、出焦延迟时间最短和检修时间足够长的优化调度模型；在异常工况下，通过将乱笺炉号、事故状态、病号炉3种情况归结为乱笺炉号的情况，建立系统实现目标不变，以恢复过程中所有小循环总费用最小为目标的异常工况下的优化调度模型。针对2种优化调度模型，分别提出正常工况下的焦炉作业计划编排方法和基于Dijkstra 算法的异常工况焦炉作业计划编排方法，该方法将实际的乱笺问题转化为最短路径问题。仿真实验结果表明，采用该方法实现了推焦计划的自动编制，提高了生产效率和企业的经济效益，证明该方法是有效的。
关键词：焦炉；优化调度；最短路径算法；Dijkstra算法
中图分类号：TP229 文献标识码：A 文章编号：1672-7207(2007)04-0745-06
Coke oven working planning based on optimization scheduling models
CAI Yan, WU Min, YANG Jing, CAO Wei-hua
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: A coke oven working planning based on optimization scheduling models was presented for normal and abnormal conditions of coke oven. Under the normal conditions, an optimization model was obtained to achieve the shortest mechanism path in the facilities, the shortest lag time of pushing management and enough repairing time. Under the abnormal conditions, oven number out of sequence, accident state and broken oven were uniformly described as oven number out of sequence. Based on that, an optimization model for the abnormal conditions was established to achieve targets and the least cost of little cycle in recovering process. To deal with these two optimization models, the corresponding coke oven working planning was proposed, i.e., one was under normal conditions, and the other was based on Dijkstra algorithm under abnormal conditions. This method translates the practical chaotic groups into the shortest path problem. The simulation results show that the proposed methods can be used to realize coke plans automatically and efficiency of production and the economic efficiency of enterprises are enhanced, so the proposed method is effective.
Key words：coke oven; optimization scheduling; the shortest path algorithm; Dijkstra algorithm
长期以来，国内的推焦计划编制采用人工编制推焦计划的方法存在着任务繁琐、效率低、理论依据少、对异常情况难以及时反映等问题，容易导致疲劳操作、机械过于损耗、焦炉加热[1]不稳定等现象，进而降低焦炭质量和焦炉寿命。因此，必须利用先进的计算机优化调度[2]技术对焦炉作业计划进行自动编制，在异常情况时对作业计划及时修正，充分保证机械设备的定期维护。
许多源于生产实际的生产计划与调度问题是优化问题[3]，调度的目标是将任务合理地安排到各机器，并合理安排任务的加工次序和加工时间，使约束条件被满足，性能指标达到最优或者较优。近年来，在调度领域出现了许多新的优化方法，使调度问题的研究方法向多元化方向发展，常用的方法有以下几种：确定性最优方法[4-5]，基于启发式规则的调度方法[6]，仿真调度方法[7]，基于DEDS(discrete event dynamic systems，即离散事件动态系统)的解析模型方法[8]，启发式图搜索法，模拟退火法[9]和遗传算法等。各种调度方法在煤炭混料、炼钢、轧钢工序等领域的应用也越来越广泛[10]。但是，目前优化调度方法在焦炉生产过程中的应用还很少。在此，本文作者将优化调度的思想[11-12]与焦炉的工艺相结合，针对一套焦炉作业的设备，对正常情况和异常情况 2 种状态分别建立焦炉作业计划的编制方案。
1 优化调度模型
建立推焦计划表是根据现场的焦炉生产情况，综合考虑乱笺、设备故障等多方面因素，按照白班、中班、晚班的顺序，编排出合理的每天每班推焦的炭化室序号的先后顺序，给出推焦的炉数和对应炭化室的计划推焦时间、结焦时间、装煤时间和单炉操作时间等参数。推焦计划的实施方案既要保证焦炉每天的生产量和焦炭的质量，也要考虑延长炉体寿命，降低热量消耗，提高操作效率，减少机械损耗。焦炉存在正常工况和异常工况2种状态，在此，根据这2种工作状态分别建立相应的优化调度模型。
1.1 正常工况下的优化调度模型
以某钢铁企业的焦炉作业计划为例，该企业新1号、2号焦炉在计划编制中采用5-2串序，新1号焦炉为60孔JN-60型焦炉，新2号焦炉为55孔的JN-60型焦炉，2座焦炉目前有2台推焦车、2台煤车、1台拦焦车(备用1台)和1台熄焦车。2座焦炉的推焦串序如下。
新1号焦炉的推焦串序为：
1号笺：56,61,66,71,76,81,86,91,96,101,106,111；
3号笺：58,63,68,73,78,83,88,93,98,103,108,113；
5号笺：60,65,70,75,80,85,90,95,100,105,110,115；
2号笺：57,62,67,72,77,82,87,92,97,102,107,112；
4号笺：59,64,69,74,79,84,89,94,99,104,109,114。
新2号焦炉的推焦串序为：
1号笺：1,6,11,16,21,26,31,36,41,46,51；
3号笺：3,8,13,18,23,28,33,38,43,48,53；
5号笺：5,10,15,20,25,30,35,40,45,50,55；
2号笺：2,7,12,17,22,27,32,37,42,47,52；
4号笺：4,9,14,19,24,29,34,39,44,49,54。
在焦炉作业计划与优化调度中，要达到以下目标：一是总的机械行程最短，即路程费用最少；二是每孔结焦时间与规定结焦时间之差(这里用出焦延迟时间费用来表示)最小；三是检修时间要足够，即检修时间费用最长。其中，结焦时间指煤料在炭化室内停留的时间，通常是指从开始平煤(装煤时刻)至开始推焦(推焦时刻)的时间间隔；周转时间指某一炭化室从本次推焦(或装煤)至下次推焦(或装煤)的时间间隔，对于全炉，周转时间为全炉操作时间与检修时间之和。一般检修时间以2~3 h为宜。
建立下述优化调度模型：
其中：tjie1为规定结焦时间；tjie2为实际结焦时间；ttui1为上周周转时间的实际推焦时间；tmei2为上周周转时间的实际装煤时间；ttui2为下周周转时间的计划推焦时间；n为1号、2号焦炉总炉数；m为单孔操作时间；τ为周转时间；N为第j次推焦的炉号；A为计划推焦时间与规定推焦时间相差大于5 min的炉数；tj为第j次推焦时实际结焦时间与计划结焦时间差；a，b和c为加权系数；β为反映延长结焦时间时炉体受损程度上升的快慢因子。目标函数中减1是为了使t=0(即按时出炉)时炉体不受损。加权系数a，b和c的确定带有较大的主观性，因而，如何确定a，b和c是该优化调度模型的关键。
1.2 异常工况下的优化调度模型
在生产过程中，影响焦炉作业计划的异常工况及处理方法主要有以下几种。
1.2.1 乱笺
推焦时，若发现焦饼不熟、收缩不好，则应关上炉门继续加热，待成熟后再推，这样就造成推焦延迟，即“乱笺”。这时，在编排计划时，就应逐步“顺笺”，根据实际情况采取“向前提”、“向后丢”的方法尽快调正，尽量在较短的时间内恢复正常。
1.2.2 事故影响
在焦炉生产中，经常会发生装煤孔堵眼、炉门框夹焦、炉墙集炭过厚、推焦杆变形、四车出现机械故障等事故，当事故时间短、影响的炉数少时，通过缩短操作时间和利用检修时间推焦的办法赶回丢失的炉数，即事故后将下一个炉号推焦时间后移，推焦顺序不变，同时适当缩短操作时间，或利用检修时间推焦，以便下个循环时能恢复正常推焦。若事故时间比较长、影响的炉数较多时，事故后先按正点时间推焦，同时缩短操作时间，当缩短的时间足够推1炉焦时就把因事故延迟的炉数赶回1炉，依此类推赶回丢失的炉数，而在下次推焦循环中按乱笺处理。若事故过长，则必须丢炉。
1.2.3 病号炉
病号炉的炭化室墙面变形，推焦阻力增加，导致推焦困难，须经常推二次焦。为避免二次推焦，在编排推焦计划时，另排病号炉，按其周期时间单独排出循环图表。
针对以上存在的事故，对于病号炉，在编排推焦计划时不安排在一般的循环表中，需要单独进行计划编排。而对于事故影响，若时间较短，则在本次循环就可以调整推焦串序，尽快恢复正常生产；而当时间较长时，若在本循环未能正常地推焦串序，则在下个循环按照乱笺处理。因此，对于事故造成的对推焦串序的影响，在采用智能方法进行优化调度时，可以按照处理乱笺的方式进行计划编排。
在乱笺的情况下，系统要实现的目标不变，仍然由路程费用(这里用实际的机械行程和正常推焦串序情况下的机械行程的差值来表示)、出焦延迟时间费用构成，只是在乱笺的情况下，要经过几次小循环才能逐步恢复到正常的推焦计划，所以，在这种情况下，以恢复过程中所有小循环总的费用最小为目标。因此，在式(1)基础上进行相应修改，得到如下优化调度模型：
其中：n1为出现乱笺时，恢复到原来的推焦串序需要经过调整的小循环次数；ti, jie2为实际结焦时间；ti, tui1为上周周转时间的实际推焦时间；ti, mei1为上周周转时间的实际装煤时间；ti, mei2为下周周转时间的计划推焦时间；Ni,j为第i次循环时第j次推焦的炉号；Ai为第i次小循环时计划推焦时间与规定推焦时间相差大于5 min的炉数；ti,j为第i次小循环时第j号炉时间结焦时间与计划结焦时间差；Nway表示正常推焦顺序时总的机械行程；其他变量和系数如表1所示。
表1 推焦计划表
Table 1 Pushing plan table
2 焦炉作业计划编排方案
针对2种工况下建立的优化调度模型，提出相应的焦炉作业计划编排方法。
2.1 正常工况下的焦炉作业计划编排方法
由式(1)，通过简单的数学计算，就可以编制出正常情况下的推焦计划的大循环表。
在目标函数中要求总的机械行程最短，由于“5-2”推焦串序操作较为紧凑，节省时间和电力，机械行程比“9-2”串序的更短，且适用于5炉距新型推焦车，推焦车采用五炉距一次对位操作，缩短了机械行程，因此，本方案选择“5-2”推焦串序。
针对每孔结焦时间与规定结焦时间之差最小的要求，本方案使每孔实际的结焦时间和规定的结焦时间相等，并尽量按照编排好的推焦计划表进行推焦操作。因结焦时间可以近似等于周转时间，而周转时间是由生产任务来确定的，根据生产现场的实际情况，周转时间一般为20 h左右，所以，方案中也选择结焦时间为20 h。
目标函数的第3个要求就是检修时间要足够。设周转时间为τ，已知τ＝20 h，n=138，若设定1号、2号焦炉的单炉操作时间m为8 min，则检修时间为：
根据(3)式，可计算出检修时间为4.7 h。根据5-2串序，将1号焦炉的每笺分为2部分：前6个炉号为第1部分A1，后6个炉号为第2部分A2；将2号焦炉的每笺分为2部分：前5个炉号为第1部分B1，后6个炉号为第2部分B2。在编排计划时，A1，A2，B1和B2作为一个连续推焦，推焦的先后顺序是，B1—A1—B2—A2。以后各笺均以此顺序进行操作，每笺推完之后，安排检修时间为1 h。这样，每班可以检修2次，每次1 h。当在推1号焦炉时，2号焦炉可以进行小检修，并且有比较充分的时间将机械移动到指定炉号，2号焦炉推焦车还有卸余煤的时间，这样就又延长了检修时间，符合目标函数的要求。
根据以上分析，编排出1 d的推焦计划表，如表1所示。表中“>”表示开始检修，后面的时间就是检修时间的开始和结束时间，(72)和(66)为炉数，周转时间为20 h，单炉操作时间为8 min。在正常工况时，每班推焦计划应符合推焦计划表。
2.2 基于Dijkstra算法的异常工况焦炉作业计划编排方法
对于异常工况，可以归结为乱笺炉号的处理。乱笺是因各种原因而产生一个或者几个延迟推焦的炉号，在编排计划时，就应逐步“顺笺”，尽快调正，尽量在较短的时间内恢复正常的推焦顺序。因此，可以把乱笺的问题转化为求解最短路径的问题。
最短路径问题[13]是对一个赋权的有向图D中指定的2个点Vs和Vj找到1条从Vs到Vj的路，使得这条路上所有弧的权数总和最小，这条路称为从Vs到Vj的最短路，这条路上所有弧的权数总和称为从Vs到Vj的距离。
传统的最短路径算法主要有Floyd算法和Dijkstra算法[14]。Floyd算法用于计算所有节点之间的最短路径，而Dijkstra算法则用于计算一个节点到其他所有节点的最短路径，其主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。本文需要求解的就是一个结点到另一个结点间的最短路径，所以，选择Dijkstra算法。下面介绍最短路径的Dijkstra算法，然后把乱笺的实际问题转换为纯数学的最短路径问题，用Dijkstra算法求解。
Dijkstra算法适用于每条弧的赋权数Ｃi,j≥0的情况，是目前公认的求解最短路问题的最经典的算法。Dijkstra算法也称为双标号法。所谓双标号，也就是图中的点Vj赋予2个标号(lj,kj)：第1个标号表示从起点Vs到Vj的最短路的长度，第2个标号kj表示从起点Vs到Vj的最短路上Vj前面一个邻点的下标，从而找到Vs到Vj的最短路及Vs与Vj的距离，它能给出从某指定顶点到图中其他所有顶点的最短路。其时间复杂度为O(n2)。其中，n为结点个数。
在异常工况时，乱笺的情况很多，造成混乱的推焦顺序也多种多样。这里举例说明Dijkstra算法的具体应用。例如在推焦计划中的正常推焦顺序为“1—6—11—16—21—26”，实际推焦时因为某种原因产生延迟推焦，出现乱笺，使1号炉在该出炉时没有出炉而产生延迟推焦，结果使实际推焦顺序变为“6—11—16—21—26—1”，本系统要实现的目标就是在目标函数(1)式最小的情况下使推焦顺序尽快恢复正常。可以把这个实际问题化为最短路径问题，并用Dijkstra算法来求解。
开始乱笺后的推焦顺序为“6—11—16—21— 26—1”，记为初始状态，用V1表示；恢复正常后的推焦顺序“1—6—11—16—21—26”，记为末状态，用点Vn表示。其中，n为乱笺影响的炉数，这里n＝6。从初始状态V1到恢复到末状态V6，可以经过“6—11—16—21—1—26”，“6—11—16—1—21—26”，“6—11—1—16—21—26”和“6—1—11—16—21—26” 4个状态，分别用点V2，V3，V4和V5表示。则问题转换为从点V1到V6找到一条路，使得这条路上所有弧的费用的总和最小，这条路称为从V1到V6的最短路，可用图1表示。
图1 采用Dijkstra算法的最短路模型
Fig.1 The shortest path model based on Dijkstra’s model
对图1中的每条弧赋予权数。对于弧(Vi, Vj)，它的权数即为从Vi变到Vj的顺序时总的行程费用、因推焦提前、延迟产生的费用和减少检修时间的费用之和，可根据(2)式计算其数值，用Ci,j表示。这样，就把实际的乱笺问题转化为纯数学的最短路径问题，可以用Dijkstra算法来求解。按前面的方法，首先对第1个点进行标号，然后，找到未标号的点的集合和已标号的点的集合，逐步对各个未标号的点进行标号，直到未标号点的集合为空为止，最后，计算起始点到其他所有点的最短路程，便可知从V1到V6的最小费用和所经过的最短路径。
3 应用实例
在正常工况时，每班推焦计划应符合推焦计划表。在没有延迟推焦和不改变生产计划时，每班的推焦计划应与循环推焦计划表相一致，这样，编制时就很简单。但遇到延迟推焦，生产计划调整及特殊炉号处理等情况时，就须将这些特殊因素考虑在内进行仔细 编排。
在异常工况时建立的数学模型中，其目标函数(2)式中加权系数a和b的确定带有较大的主观性，因而如何确定a和b是采用此目标函数的重要问题，而且乱笺的情况处理经分析属于NP难题，有没有最优解及能不能求出最优解也是无法确定的。因此，需要用仿真来验证。通过大量的仿真实验，最终确定函数中的加权系数为：a＝0.4，b＝1－a＝0.6。用Matlab仿真最短解。Matlab仿真程序中用到了图与网络论中求最短路径的Dijkstra算法，M-函数格式为：
[S, D]=minroute(i, m, W)
其中：i为最短路径的起始点；m为图顶点数；W为图的带权邻接矩阵。不构成边的2顶点之间的权用inf表示。显示结果为：S的每一列从上到下记录了从始点到终点的最短路径所经顶点的序号；D为向量，记录了S中所示路径的大小。以前面的例子进行仿真，结果为：
由该结果可得到1条最短V1→V3→V5→V6，也就是说，从状态“6—11—16—21—26—1”调正到“6—11—16— 1—21—26”，再到“6—1—11—16—21—26”，最后恢复正常串序“1—6—11—16—21—26”，这个方案使总的费用最少。实际生产中的情况比以上例子要复杂得多，因此，运用此方法时，需经过多种情况下的仿真才能使仿真结果能得到最优解。
4 结 论
a. 针对焦炉作用计划与优化调度的目标函数的多样性、约束条件复杂、各系统不容易确定等难点，通过分析焦炉作业计划的特点以及编制原则，分别对于焦炉生产经常遇到的乱笺、事故和病号炉等的异常情况，建立了综合考虑出焦延迟费用、总的机械行程和机械设备检修时间等因素的优化模型。
b. 对于正常工况，根据现场的经验，设计了焦炉作业计划的编排方法；而对于异常工况，运用基于图与网络模型的优化调度思想，采用最短路径算法的迪克斯特拉(Dijkstra)算法编排作业计划，并且在MATLAB仿真平台下进行仿真，验证了基于Dijkstra算法的异常工况作业计划编制方法的有效性。实验结果表明，采用此方法能实现推焦计划的自动编制，在实际运用中能节省人力物力，大大提高了生产效率和经济效益。
参考文献：
[1] 周国雄, 赖旭芝, 曹卫华, 等. 焦炉集气管压力智能解耦控制系统的应用[J]. 中南大学学报: 自然科学版, 2006, 37(3): 558-560.
ZHOU Guo-xiong, LAI Xu-zhi, CAO Wei-hua, et al. Application of intelligent decoupling control system for coke-oven collector pressure[J]. Journal of Central South University: Science and Technology, 2006, 37(3): 558-560.
[2] 谢建国, 陈松乔, 陈建二. VBR流磁盘I/O的优化调度及特定的缓冲计算[J]. 中南工业大学学报: 自然科学版, 2001, 32(2): 204-208.
XIE Jian-guo, CHEN Song-qiao, CHEN Jian-er. The optimizing schedule of the VBR stream disk I/O and buffer computing in special situation[J]. Journal of Central South University of Technology: Natural Science, 2001, 32(2): 204-208.
[3] 唐立新. 基于智能优化的钢铁生产计划与调度研究[J]. 管理学报, 2005, 2(3): 263-267.
TANG Li-xin. Intelligent optimization-based production planning and scheduling in iron and steel industry[J]. Chinese Journal of Management, 2005, 2(3): 263-267.
[4] Sarin S C, Ahn S, Bishop A B. An improved branching scheme for the branch and bound procedure of scheduling n jobs on m machines to minimize total weighted flow time[J]. Intern at J Production Res, 1988, 26: 1183-1191.
[5] Potts C N, van Wassenhove L N. A branch and bound algorithm for the total weighted tardiness problem[J]. Operation Research, 1985, 33: 363-377.
[6] Wu S Y D, Wysk R A. An application of discrete-event simulation to on-line control and scheduling inflexible manufacturing[J]. Int J Prod Res, 1989, 27(9): 1603-1623.
[7] Leung L C, Maqnheshw A S K, Miller W A. Concurrent part assignment and tool allocation in FMS with material handling considerations[J]. Int J Prod Res, 1993, 31(1): 117-138.
[8] 刘瑞华, 涂奉生. Fork-Join 排队网络的建模与稳定性[J]. 控制与决策, 1994, 9(3): 131-135.
LIU Rui-hua, TU Feng-sheng. Modeling and stability of Fork-Join queueing networks[J]. Control and Decision, 1994, 9(3): 131-135.
[9] 田 澎, 杨自厚, 张嗣瀛. 同顺序(flow shop ) 排序问题的模拟退火求解[J]. 信息与控制, 1994, 23(3): 133-139.
TIAN Peng, YANG Zi-hou, ZHANG Si-ying. Flow-shop scheduling by simulated annealing[J]. Information and Control, 1994, 23(3): 133-139.
[10] 杨自厚. 神经网络技术及其在钢铁工业中的应用[J]. 冶金自动化, 1996, 20(4): 48-51.
YANG Zi-hou. Neural network models and its applications to iron and steel making processes[J]. Metallurgical Industry Automation, 1996, 20(4): 48-51.
[11] Jouni S. Production Planning in Printed Circuit Board Assembly[D]. Finland: Department of Computer Science, University of Turku, 2002.
[12] 蒋圣平, 邹益仁, 梁 刚. 钢铁企业CIMS下生产计划的研究[J]. 冶金自动化, 2003, 27(6): 1-6.
JIANG Sheng-ping, ZOU Yi-ren, LIANG Gang. Study on production planning in iron & steel enterprise CIMS[J]. Metallurgical Industry Automation, 2003, 27(6): 1-6.
[13] 韩伯棠. 管理运筹学[M]. 北京: 高等教育出版社, 2001: 203-216.
HAN Bo-tang. Management operations research[M]. Beijing: Higher Education Press, 2001: 203-216.
[14] 严蔚敏, 吴伟民. 数据结构[M]. 北京: 清华大学出版社, 1997: 188-189.
YAN Wei-min, WU Wei-min. Data structure[M]. Beijing: Tsinghua University Press, 1997: 188-189.
收稿日期：2007-01-10
基金项目：国家“863”计划资助项目(2006AA04Z172)；国家杰出青年科学基金资助项目(60425310)
作者简介：蔡 雁(1978-)，女，湖南益阳人，助理研究员，从事计算机应用研究
通讯作者：吴 敏，男，教授，博士生导师；电话：0731-8830342; E-mail: min@mail.csu.edu.cn
