基于“炉-机对应”的炼钢-连铸生产调度问题遗传优化模型

刘 倩，杨建平，王柏琳，刘 青，高 山，李宏辉

1) 北京科技大学钢铁冶金新技术国家重点实验室，北京 100083 2) 北京科技大学东凌经济管理学院，北京 100083 3) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083 4) 莱芜钢铁集团银山型钢有限公司，莱芜 271104

钢铁制造流程是一个多组元、多相态、多层次、多尺度、开放性的、动态有序的复杂过程，其竞争力、可持续发展力的根本性来源是整个生产流程运行和管理的智能化[1].炼钢-连铸过程是钢铁制造流程的关键区段，由于生产过程的复杂性和不确定性，当前多数生产调度模型的实际应用效果并不理想，生产调度计划很大程度上仍依靠人工编制.因此，研发合理有效的复杂生产调度问题的模型和求解算法，是当前众多学者关注和研究的重点和热点.

近年来，各种进化算法（遗传算法[2-3]、蚁群算法[4-5]、蜂群算法等[6-7]）、启发式方法及人工智能方法等被逐渐应用于生产调度问题的求解[8-9].文献[10]～[12]针对炼钢-连铸过程计划优化问题，建立多目标生产调度优化模型，提出基于精英策略(NSGA2)的多目标遗传算法，控制了非劣解集的选取.文献[13]～[16]针对炼钢-连铸生产调度模型，提出基于改进变异算子和自适应算子、交叉变异自适应概率等的遗传算法，提高搜索性能.文献[17]提出了一种并行向后推理和遗传算法相结合的生产计划优化模型，以提高炼钢连铸生产计划的效率和性能.文献[18]提出了一种基于遗传算法、禁忌搜索和模拟退火算法求解作业车间调度问题的新算法，算法迭代过程采用禁忌搜索方法生成新种群.

基于上述研究，运用遗传算法求解炼钢-连铸过程生产调度问题的改进策略可总结为以下三种：（1）基于优先级的选择和排序策略；（2）基于算法本身某些参数优化的策略；（3）遗传算法与其他算法结合策略.这几类策略较少深入结合炼钢-连铸生产过程的一些根本问题，如优化的生产模式、工序/设备间对应匹配关系，因而往往很难应用到实际生产中.本文以国内某中大型转炉炼钢厂为研究对象，针对其生产过程因多品种、小批量、多规格、高质量等需求特征而产生的流程复杂、衔接匹配欠佳等问题，开展炼钢-连铸过程生产调度模型与求解算法的研究.在考虑工序/设备之间匹配关系的基础上，提出了一种基于“炉-机对应”策略的改进遗传算法，通过对实际生产计划的求解，验证了该算法在减少生产过程设备等待时间、提高转炉/精炼炉与连铸机的匹配程度方面具有较好的效果.

1 炼钢-连铸生产调度模型建立

炼钢-连铸生产调度问题是影响钢铁生产流程高效运行的关键问题之一，典型的炼钢-连铸生产流程主要包括炼钢、精炼和连铸等多个工序/环节，其中精炼工序根据钢种需求选择合适的设备，每个工序同时存在着多台生产设备，因此，生产调度问题可以归结为多阶段多并行机的混合流水调度问题[19].图1为典型的炼钢-连铸生产流程示意图，其中BOF、LF、RH、CC分别为转炉、LF精炼、RH精炼及连铸，n为炉次数，Mj为设备号.

1.1 问题描述与假设

为了确保生产流程的高效稳定运行，在满足约束条件的基础上，调度问题主要是根据浇次计划为每个工序上的生产炉次在多台并行设备中选择合理的设备，并安排其作业任务的起止时间.此外，还需考虑不同的加工路径造成运输过程时间差异，造成炉次等待时间过长，影响整个生产过程生产顺行.本文研究的炼钢-连铸生产调度是在给定浇次计划下进行的，并满足以下基本假设：

（1）浇次数量、浇次包含的钢种类别、炉次顺序及对应连铸机均为已知；

图1 典型炼钢-连铸生产流程示意图Fig.1 Flowchart of typical steelmaking continuous casting production scheduling

（2）浇次的计划开浇时间和停浇时间已知；

（3）炉次在不同工序（冶炼、精炼、连铸等）的作业周期已知；

（4）炉次在冶炼、精炼工序上的设备指派不受限制，且精炼工序具有一定的时间缓冲；

（5）不考虑设备因突发事故造成的生产中断.

1.2 符号定义

i—炉次序号，由I个炉次组成，其中i∈[1,I]；

j—工序编号，共有J道生产工序，其中j∈[1,J]；

k—工序j中的设备编号，由Mj台设备组成，其中；

l—浇次序号，Ωl为浇次l包含的炉次集合，其中l∈Ωl，Ωl={Zl,Zl+1,Zl+2,···,Zl+I-1}，其中Zl为浇次l包含的炉次的第一炉次；

i′—工序j设备k上紧邻炉次i的后一炉次；

j′—炉次i在加工路径中工序j的紧后工序；

k′—炉次i在下一个工序j′上的设备编号；Xi,j,k—炉次i在工序j设备k上的开始作业时间；

Xl,i,j,k—浇次l中第i炉次在工序j设备k上的开始作业时间；

Pi,j,k—炉次i在工序j设备k上的作业时间；

Pl,i,j,k—浇次l中第i炉次在工序j设备k上的作业时间；

Tj,j′—相邻工序j和工序j′之间的标准运输时间；

Tl—第l个浇次的开浇时间；

σ—不同浇次之间的调整时间；

1.3 数学模型

除运输时间外，炉次在炼钢-连铸过程的等待时间要尽可能小.等待时间为下一工序的开始作业时间Xi,j′,k′与上一工序结束时间之差，再减去工序之间的运输时间Tj,j′的所得到的差，上一工序的结束时间即为上一工序开始作业时间Xi,j,k与工序操作时间Pi,j,k之和.基于上述描述和假设，建立以目标炉次在工序间总等待时间最小为目标的炼钢-连铸生产调度模型：

调度模型的约束条件如下：

其中：式（2）表示每个浇次准时开浇；式（3）表示每个炉次在每个工序只能在一台设备处理；式（4）表示同一浇次内的相邻炉次必须进行连续浇注；式（5）表示同一个炉次在下一个工序的操作必须在上一个工序结束后进行；式（6）表示同一设备的下一个炉次的操作必须在上一炉次处理完后进行；式（7）表示浇次间调整和准备时间约束.

2 模型求解方法

基于遗传算法简捷通用的特点，本文采用遗传算法求解上述模型.遗传算法的主要内容包括：染色体编码、初始种群生成、适应度计算、交叉和变异.

2.1 染色体编码及解码

为方便对染色体进行编码和解码，本文的编码方式采用分段组合编码[20].构造的染色体编码包含浇次信息和设备选择信息，因此，编码分为两个部分，其中第一部分包括各浇次的开工时间Tl，第二部分是炉次在各工序的设备号Mj.如下染色体：

其中，T1代表第1个浇次的开浇时间，Tl代表第l个浇次的开浇时间.123代表1号炉次的生产路径为：1号转炉—2号精炼炉—3号连铸机.

基于以上的编码方式，运用遗传算法求解炉次在不同工序中的设备选择信息，根据已知的浇次信息，通过倒推便可得到对应的其他工序上的时间信息.

2.2 基于“炉-机对应”策略的初始种群生成

炼钢-连铸过程的“炉-机对应”原则是指炼钢/精炼工序和连铸工序中不同设备之间明确的对应关系，其表现形式一般分为“定炉对定机”和“一一对应”2种[21].“炉-机对应”调控策略则是炼钢-连铸过程实现工序/设备的节奏匹配和产能平衡的具体调控措施，使炼钢-连铸过程生产模式、工艺路径在整个运行过程中更加有序简捷.考虑到实际生产中的连浇及等待时间约束对生产节奏的影响，以炉次在工序间总等待时间最小为优化目标，给出炉次的合理设备指派和作业时间信息.基于以上的思想，生成初始种群的四个步骤如下：

步骤1：将浇次信息输入，包括炉次信息、时间参数、算法参数等；

步骤2：根据钢种要求，为炉次选择最佳的作业路径并指派相应的设备，设备指派遵循以下4条“炉-机对应”调控策略.

（1）如果Pi,2,k≤Pi,3,k，即精炼周期不大于浇铸周期，在不考虑过程等待时间时，一台精炼炉即可满足一台连铸机连浇所需的钢水供应；

（2）如果Pi,2,k>Pi,3,k，即精炼周期大于浇铸周期，至少需要一座以上的精炼炉才能保证连铸机连浇，在该座精炼炉供应钢水的同时，还需要其他精炼炉也适时供应钢水，才能保证对应的这台连铸机连浇；

（3）如果Pi,1,k≤Pi,3,k，即转炉周期不大于浇铸周期，在不考虑过程等待时间时，一台转炉即可供应一台连铸机连浇；

（4）如果Pi,1,k>Pi,3,k，即转炉周期大于浇铸周期，至少需要一座以上的转炉才能保证连浇，在该转炉向连铸机供应钢水的同时，还需要其他转炉适时供应钢水，才能保证对应的这台连铸机连浇.

图2 炉次在冶炼、精炼工序的时间参数Fig.2 Time parameters of the heat sequences of the smelting and refining process

当工序j′上炉次出现先到后加工现象时，重新返回炉次i在上一工序j的加工次序，遵循先到先加工原则，对炉次顺序进行重新调整，从而消除时间冲突，如图3所示.

步骤4：重复步骤2、3直到初始种群生成.

“炉-机对应”策略通过平衡工序节奏与产能关系，为炉次选择最佳的工艺路径及设备匹配，建立炼钢（精炼）工序和连铸工序设备之间明确的对应关系，减少由于设备随机指派造成的工序设备间对应关系不明确、工序设备交叉混乱；同时减少由于设备随机指派造成个别炉次上下工序设备间距离较远的情况.

图3 炉次顺序调整Fig.3 Adjustment of the heat sequences

2.3 适应度计算

遗传算法的适应度计算是染色体性状的评价指标.基于排序选择能够根据适应度的大小进行选择操作，能够保留优良个体能直接进入后代种群，因此，本文选择基于排序选择的适应度计算，其适应度分配的计算公式[14]为：

其中，F表示适应度，Nind为种群中个体数目，Pos为个体在种群中的排序位置，SP为选择压力，一般取[1.0，2.0]，这里取2.0.

2.4 遗传操作

通过编码组成初始群体后，遗传操作的任务就是对个体按照它们对适应度大小进行选择、交叉和变异，从而实现优胜劣汰的进化过程.遗传操作的关键步骤如下：

（1）选择操作：选择操作是在适应度函数的评估上进行的，通过基于排序适应度选择方法进行操作，将上一代优良的个体保留下来，淘汰性能较差的个体.

（2）交叉操作：随机选择种群内某两个个体，交换两个个体上同一炉次i在工序j的加工设备（不包含连铸工序）.

（3）局部搜索：将（2）中当前最优解作为局部搜索的初始解，通过邻域动作交换相邻工序上的设备指派（不包括连铸工序），从当前解的临近解空间中选择一个最优解作为当前解，迭代100次，直到达到最优解.

（4）变异操作：随机选择种群内某个个体工序j上的任意两台设备，并从两台设备上分别随机选择所加工的炉次i'、i"进行交换.

2.5 基于“炉-机对应”策略的改进遗传算法

为获得更为合理、可行性高的调度方案，考虑到等待时间和“炉-机对应”程度的相互制约，本文在遗传算法初始种群生成过程中引入“炉-机对应”策略，构建改进遗传算法模型.此外，为考察改进遗传算法的高效性，采用启发式算法作为对照实验，详细说明如下.

（1）算法A1：不包含“炉-机对应”策略的遗传算法；

（2）算法A2：在A1算法基础上，种群生成过程中引入“炉-机对应”调控策略，若个体满足2.2节中的策略（1）或（3），则该个体对应工序上的炉次不进行交叉、变异操作；若个体不满足策略（1）或（3），则该个体对应工序上的炉次进行交叉、变异操作.

（3）算法A3：启发式算法，以目标炉次工序间总等待时间最小为优化目标，在连续浇铸的前提下，倒推出各炉次在各工序的开始和结束作业时间，以设备时间冲突最小规则为炉次指派设备，生成粗调度，再用线性规划模型消除设备冲突.

图4为改进遗传算法求解步骤，输入钢厂浇次计划信息及算法参数，根据“炉-机对应”策略进行设备指派，然后倒推计算出炉次在精炼和冶炼设备/工序的开工时间；若产生炉次作业时间冲突，遵循先到先加工原则，返回炉次上一工序，重新对炉次加工顺序进行调整，消除时间冲突；此时，若满足进化代数直接输出最优解，若不满足，通过适应度计算选择最优个体进入下一代，再进行交叉、局部搜索和变异操作，形成新一代种群，重复上述操作直至产生最优解.

3 实验结果讨论分析

以国内某炼钢厂的生产调度方案编制为例，用上文提出的三种算法对本文建立炼钢-连铸生产调度模型进行求解，从时间结果和炉-机匹配程度两方面进行分析和评价，选出优化性能最佳的算法及生产调度方案.

3.1 实验背景及数据

国内某钢厂现有4座转炉（BOF）、4座LF精炼炉（LF）、4台连铸机（CCM），由于4台连铸机的生产能力大于4座转炉（精炼炉），因此，兼顾工序产能匹配和产能最大化的前提下，主要采用4座转炉供应3台连铸机的生产模式.其生产模式主要有：4BOF-3CCM模式大约占比80%，4BOF-4CCM模式大约占比10%，3BOF-3CCM模式占10%.

本文第2节的算法采用C#语言进行编程，运行于Microsoft Visual Studio软件.基于前人的研究成果[20,22]，经过多次实验，确定改进遗传算法参数设置如下：进化代数为100，种群规模为500，自适应函数参数pc= 0.8、pm= 0.001.

3.2 实验结果与分析

下面运用本文建立三种算法进行生产调度方案的求解，从运行过程的等待时间和炉-机匹配程度两方面对调度方案进行分析讨论.

3.2.1 等待时间分析

由上文的研究可知，本文提出三种算法来比较调度方案的有效性.除炉次各工序间等待时间之和最小的目标函数T0之外，还选取部分能够反映实际生产顺行情况的数据作为算法有效性的评价指标，即工序间最长等待时间T1、工序间等待时间大于30 min的炉次占比p以及浇次开浇时间最大偏离量T2.分别运用三种算法对三种生产模式下的算例进行排产方案求解，具体结果见表1.由于篇幅所限，下文仅讨论4BOF-3CCM、4BOF-4CCM模式下的结果.

图4 基于“炉-机对应”策略的遗传算法求解流程Fig.4 Solution procedure of the scheduling problems derived using the genetic algorithm based on the “furnace-caster coordinating” strategy

由表1可知，运用遗传算法（A1、A2）得到的开浇时间最大偏离量均为0，表明每天基本的生产任务可以完成；用启发式算法（A3）得到的开浇时间有一定偏离，偏离范围在44～110 min，且A3算法求得的排产方案在目标函数、工序前最长等待时间及工序前等待时间>30 min的炉次占比均比其他两种方法所得效果差.这是由于启发式算法A3为消除设备上的资源冲突问题，造成开浇时间偏离，从而导致工序间等待时间变长，因此，A3算法不可用.A2与A1算法的求解结果相比，A2算法在目标函数及工序间最长等待时间两方面均优于A1算法，算例1在工序间最长等待时间上由77 min减小到54 min，算例2在工序间最长等待时间上由97 min减小到76 min；算例1在工序前等待时间>30 min的炉次占比由19%减小到13%，算例2在工序前等待时间>30 min的炉次占比由35%减小到29%.这是由于未引入“炉-机对应”策略的A1算法在设备选择上随机性大，个别炉次的加工路径不合理，造成等待时间的过长，A2算法引入“炉-机对应”策略，在工序设备上表现为“定炉对定机”或“一一对应”模式，减少了个别炉次等待时间的不合理，进一步提高了排产方案的可行性.

表1 三种算法的测试结果Table 1 Test results of three algorithms

3.2.2 炉-机匹配程度分析

为进一步验证A2算法的有效性，对不同生产模式下的炉-机匹配程度进行深入分析.应用A1与A2算法，对比了算例1（4BOF-3CCM模式）和算例2（4BOF-4CCM模式）各工序设备及其生产能力的匹配关系.

图5和图6分别为4BOF-3CCM模式和4BOF-4CCM模式改进前后的炉-机对应关系图，其中四种颜色路线表示四座转炉（精炼炉）上生产的钢水路线，箭头上的数值和箭头粗细表示该设备生产的钢水去往下个工序设备上的比例大小.用A1算法求解的算例1的调度方案其设备选择较为分散，转炉-精炼炉、精炼炉-连铸机的钢水供应较为平均；用A2算法求解的调度计划“炉-机匹配”程度大大提升，3号转炉去往3号精炼炉的钢水比例由25%提升到61%，3号精炼炉去往3号连铸机的钢水比例由25%提升到67%，由于3号连铸机连铸周期大于3号精炼/转炉周期，图5（b）所示BOF3—LF3—CCM3表现为“一一对应”形式.用A1算法求解的算例2的调度方案各设备上产能匹配较为平均，设备间的对应关系较为混乱，设备指派较为不合理；用A2算法求解的排产方案其精炼炉与连铸机的对应关系较为明确，1号转炉去往1号精炼炉的钢水比例由12%提升到42%，3号转炉去往3号精炼炉的钢水比例由31%提升到64%，由于1号连铸机连铸周期大于1号精炼/转炉周期，图6（b）所示BOF1—LF1—CCM1表现为“一一对应”形式.改进后的遗传算法减少了工序设备指派的随机性，明确设备间的对应关系，在减少不同设备之间的交叉作业、优化钢厂生产模式上具有较好效果.

综上所述，两种遗传算法能保证完成每天的生产任务，启发式算法的开浇时间有较大偏离，且其他评价指标性能较差，故A3算法不可用.A2算法与A1算法获得调度方案相比，A2算法在目标函数、炉次间的最长等待时间及工序间等待时间>30 min占比等几方面均优于A1算法，且用A2算法求解的调度方案大大提高了炉-机匹配程度，以4BOF-3CCM模式下的算例1为例，工序间最长等待时间由77 min减小到54 min，3号精炼炉去往3号连铸机的钢水比例由25%提升到67%，因此，A2算法较优.

图5 改进前（a）后（b）算例1的炉-机对应关系Fig.5 “Furnace-caster coordinating” in Sample 1 before (a) and after (b) improvement

图6 改进前（a）后（b）算例2的炉-机对应关系Fig.6 “Furnace-caster coordinating” in Sample 2 before (a) and after (b) improvement

通过对现场数据的分析，算法中炉次在工序过程的运输时间选取了实际生产中的平均值，由于实际运输时间受到天车调度约束的影响，下一阶段工作拟采用Plant Simulation软件构建炼钢-连铸过程多工序协同运行的仿真模型，探究天车运行对炉次在工序间等待时间的影响，对天车运行约束下的调度计划的影响做进一步研究.

4 结论

本文针对炼钢-连铸过程因多品种、小批量、多规格、高质量等需求特征造成的生产流程复杂、衔接匹配欠佳等问题，建立炼钢-连铸过程炉次总等待时间最小的调度模型，在遗传操作过程引入“炉-机对应”原则以改善初始种群的质量，并根据转炉（精炼）与连铸作业周期的比较，来确定是否对个体进行交叉、变异操作.通过对某钢厂炼钢-连铸生产过程三种主要生产模式进行仿真计算，结果表明改进遗传优化模型具有减少等待时间、优化炉-机对应关系的效果，验证了本文模型和算法的有效性.随着钢厂产品升级造成车间布局复杂、生产调度混乱的问题越来越多，本文提出的算法对优化钢厂生产模式、减少作业交叉、保证整个生产过程顺利进行有一定的参考价值.NE.Cms_Insert