基于遗传算法的炼钢-连铸重计划方法

第36卷第1期 北京科技大学学报 Vol.36 No.1 2014年1月 Journal of University of Science and Technology Beijing Jan.2014 基于遗传算法的炼钢一连铸重计划方法 龙建宇”，郑忠四，高小强)，龚永民)，呼万哲) 1)重庆大学材料科学与工程学院，重庆4000452)重庆大学经济与工商管理学院，重庆400044 3)攀枝花钢铁集团公司提钒炼钢厂，攀枝花617000 ☒通信作者，E-mail:chengzh@cgu.cdu.cm 摘要针对多约束的炼钢一连铸重计划问题，提出了一种按扰动时炉次的状态进行炉次分类求解的重计划方法.将重计划 问题中的约束分成强制约束和柔性约束两类，针对正在作业炉次设计了基于时间顺推和遗传算法的混合算法，针对未作业炉 次设计了基于时间倒推和遗传算法的混合算法，通过强制约束结合混合算法搜寻可行解，然后在可行解中利用柔性约束搜寻 最优解.采用钢厂的生产实绩数据进行仿真实验验证了该方法的可行性和有效性. 关键词炼钢：连铸：生产计划：调度：遗传算法 分类号TP273:TF345 Production re-planning based on genetic algorithm for steelmaking-continuous casting LONG Jian-yu,ZHENG Zhong,GAO Xiao-qiang,GONG Yong-min'),HU Wan-zhe 1)College of Material Science and Engineering,Chongqing University,Chongqing 400045,China 2)College of Economics and Business Administration,Chongqing University,Chongqing 400044,China 3)Vanadium-extracting and Steel-making Plant,Panzhihua Iron and Steel (Group)Co.,Panzhihua 617000,China Corresponding author,E-mail:zhengzh@cqu.edu.cn ABSTRACT An approach,whose hardcore is a classification of charges by determining whether the charge starts at the time of disturbance occurrence,of making a re-plan was proposed to solve the problem of multi-constrained steelmaking-continuous casting re-planning.The constraints of the re-planning problem are divided into hard and soft constraints.A hybrid algorithm based on time forward inferring and genetic algorithm is designed for the processing charges,and another hybrid algorithm based on time backward inferring and genetic algorithm is designed for the un-processing charges.The feasible solution of the re-planning problem is solved with the hybrid algorithm and hard constraints,and the optimal solution is searched with the soft constraints in the feasible solution.The feasibility and effectiveness of the method were verified with the help of simulation experiments by production data in a steel plant. KEY WORDS steelmaking:continuous casting:production planning:scheduling:genetic algorithms 炼钢一连铸是现代钢铁企业生产流程的关键环 础上重新编制计划，即重计划.炼钢一连铸重计划关 节，该区段设备多，生产组织紧凑、复杂，如何对炼 系到生产是否能稳定、连续的进行，因此该研究对实 钢一连铸区段进行有效的生产调度关系到整个钢铁 际生产有着重要的意义. 厂的生产运行顺畅与否”.在实际生产过程中常常 关于炼钢一连铸生产调度优化问题的研究已成 会出现各种随机扰动事件，这使得正在执行的计划 为近年来的研究热点-，其中涉及炼钢一连铸的重 失效.此时，必须依据实时调度信息在原计划的基 计划调度.文献9]对炼钢一连铸重调度问题进行 收稿日期：2013-0408 基金项目：国家高技术研究发展计划资助项目(2007AA04Z161):国家自然科学基金资助项目(50574110,50174061)：重庆市科技攻关重点项 目(CSTC2011AB3053) DOI:10.13374/j.issn1001-053x.2014.01.018:http://journals.ustb.edu.cn

第 36 卷 第 1 期 2014 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 1 Jan． 2014 基于遗传算法的炼钢--连铸重计划方法 龙建宇1) ，郑 忠1) ，高小强2) ，龚永民1，3) ，呼万哲1) 1) 重庆大学材料科学与工程学院，重庆 400045 2) 重庆大学经济与工商管理学院，重庆 400044 3) 攀枝花钢铁集团公司提钒炼钢厂，攀枝花 617000  通信作者，E-mail: zhengzh@ cqu． edu． cn 摘 要 针对多约束的炼钢--连铸重计划问题，提出了一种按扰动时炉次的状态进行炉次分类求解的重计划方法． 将重计划 问题中的约束分成强制约束和柔性约束两类，针对正在作业炉次设计了基于时间顺推和遗传算法的混合算法，针对未作业炉 次设计了基于时间倒推和遗传算法的混合算法，通过强制约束结合混合算法搜寻可行解，然后在可行解中利用柔性约束搜寻 最优解． 采用钢厂的生产实绩数据进行仿真实验验证了该方法的可行性和有效性． 关键词 炼钢; 连铸; 生产计划; 调度; 遗传算法 分类号 TP273; TF345 Production re-planning based on genetic algorithm for steelmaking-continuous casting LONG Jian-yu1) ，ZHENG Zhong1)  ，GAO Xiao-qiang2) ，GONG Yong-min1，3) ，HU Wan-zhe 1) 1) College of Material Science and Engineering，Chongqing University，Chongqing 400045，China 2) College of Economics and Business Administration，Chongqing University，Chongqing 400044，China 3) Vanadium-extracting and Steel-making Plant，Panzhihua Iron and Steel ( Group) Co． ，Panzhihua 617000，China  Corresponding author，E-mail: zhengzh@ cqu． edu． cn ABSTＲACT An approach，whose hardcore is a classification of charges by determining whether the charge starts at the time of disturbance occurrence，of making a re-plan was proposed to solve the problem of multi-constrained steelmaking-continuous casting re-planning． The constraints of the re-planning problem are divided into hard and soft constraints． A hybrid algorithm based on time forward inferring and genetic algorithm is designed for the processing charges，and another hybrid algorithm based on time backward inferring and genetic algorithm is designed for the un-processing charges． The feasible solution of the re-planning problem is solved with the hybrid algorithm and hard constraints，and the optimal solution is searched with the soft constraints in the feasible solution． The feasibility and effectiveness of the method were verified with the help of simulation experiments by production data in a steel plant． KEY WOＲDS steelmaking; continuous casting; production planning; scheduling; genetic algorithms 收稿日期: 2013--04--08 基金项目: 国家高技术研究发展计划资助项目( 2007AA04Z161) ; 国家自然科学基金资助项目( 50574110，50174061) ; 重庆市科技攻关重点项 目( CSTC2011AB3053) DOI: 10． 13374 /j． issn1001--053x． 2014． 01． 018; http: / /journals． ustb． edu． cn 炼钢--连铸是现代钢铁企业生产流程的关键环 节，该区段设备多，生产组织紧凑、复杂，如何对炼 钢--连铸区段进行有效的生产调度关系到整个钢铁 厂的生产运行顺畅与否［1］． 在实际生产过程中常常 会出现各种随机扰动事件，这使得正在执行的计划 失效． 此时，必须依据实时调度信息在原计划的基 础上重新编制计划，即重计划． 炼钢--连铸重计划关 系到生产是否能稳定、连续的进行，因此该研究对实 际生产有着重要的意义． 关于炼钢--连铸生产调度优化问题的研究已成 为近年来的研究热点［2--8］，其中涉及炼钢--连铸的重 计划调度． 文献［9］对炼钢--连铸重调度问题进行

·116 北京科技大学学报 第36卷 了分析，针对正在作业炉次提出了己分配设备不变 水，钢水倒入转炉下台车上的钢包内，通过天车和台 的时间修正模型，对于未作业炉次，建立了多目标非 车的运输作业，把钢水包运送至精炼环节，根据生产 线性0-1整数规划模型.该方案能缩短动态调度时 工艺要求依次在不同的精炼设备上精炼钢水，精炼 间、维持生产的稳定性，但由于方案中保持正在作业 完成后，再通过天车和台车，把钢水包运送至连铸并 炉次的未加工操作己分配设备不变，因此无法适应 实施浇铸，形成铸坯 任意设备出现故障情况下的重计划.文献0]提出 转树 精炼 连铸！ 了重调度炉次分类处理，针对正在作业炉次提出了 时间并行顺推算法，针对未作业炉次提出了基于遗 传算法和时间并行倒推的混合优化算法.时间并行 钩坯 顺推算法求解速度快，但其中炉次设备的分配仅通 高温 铁水 过启发式规则进行确定，对于多约束的炼钢一连铸 重调度问题，有时难以求得可行解.文献1]提出 了一个由任务、推理和领域三模块组成的知识模型 去管理炼钢过程中的各种扰动问题，给出了一个重 图1炼钢一连铸生产过程 Fig.I Production process of steelmaking-continuous casting 调度的框架结构，但并未给出具体的模型和求解算 法.目前的重计划方法大多拘于静态调度问题的解 在钢厂生产调度中，炉次是指同一个转炉内治 决，对动态随机性处理能力不足 炼的钢水，由于一个炉次的钢水被装入一个钢包中， 钢厂生产作业计划是依据ERP(企业资源计划 所以从炼钢到连铸前被调度的工件均为炉次，炉次 系统)系统下达的生产批量计划分批编制的，重计 是钢厂生产调度中最小的生产单元.浇次是指在同 划是保证生产作业计划有效实施的重要形式.考虑 一连铸机上连续浇铸的炉次集合，是钢厂生产调度 到重计划信息表达的完整性，本文将重计划发生时 中最大的生产单元.炼钢一连铸作业计划制定流程 刻批次内的所有炉次分成己完成作业炉次集合、正 是：首先按照技术标准将用户合同转化为生产合同， 在作业炉次集合和未作业炉次集合，三个集合内所 编制炉次计划.在炉次计划的基础上，结合热轧轧 有炉次的计划耦合成新的作业计划.已完成作业炉 制计划的要求，编制生产批量计划.在生产批量计 次的计就是炉次的生产实绩信息，研究的重点是 划中，己经确定了浇次的连铸机以及浇次内炉次的 如何编制正在作业炉次与未作业炉次的计划，以及 加工顺序和生产工艺.最后，在生产批量计划的基 如何确保耦合后的作业计划满足炼钢一连铸重计划 础上，进一步结合炼钢一连铸各环节生产能力，编制 问题的众多约束.为更准确表达生产组织及工艺约 生产作业计划，形成各炉次的火车时刻表.本文的 束等特征，将约束分成强制约束和柔性约束两大类， 研究内容就是基于生产批量计划和作业计划，研究 针对正在作业炉次提出了基于时间顺推和遗传算法 扰动时的重计划编制方法 的混合算法，针对未作业炉次提出了基于时间倒推 1.2炼钢一连铸重计划问题 和遗传算法的混合算法，通过强制约束结合混合算 生产作业计划的编制过程就是在满足各类约束 法搜寻可行解，然后在可行解中利用柔性约束搜寻 的前提下，给各炉次安排加工设备，并确定其在各设 最优解.重计划模块是生产计划调度系统网的重 备上的开始加工时间和结束加工时间.当一批生产 要组成部分，通过对钢厂的实际数据进行的系统仿 作业计划生成后，调度员应尽可能按照该计划进行 真实验来验证方法的可行性和有效性 调度和组织生产.由于生产过程中的复杂性和不稳 1重计划问题描述 定性，预定的生产作业计划在实施时可能因发生的 随机扰动而造成执行困难.若扰动小，如时间存在 1.1炼钢一连铸生产过程及作业计划制定流程 较小偏差、交换炉座，可通过生产计划调度系统中的 炼钢一连铸过程主要包含三个生产环节：炼钢、 计划修复程序进行小范围的调整：若扰动大，如设备 精炼和连铸.炼钢与连铸环节各自包含一个并行机 故障、设备启用、时间偏差过大以及任务变更，则必 组，而精炼环节一般包含多个并行机组，以实现不同 须依据实时调度信息在原计划的基础上重新编制生 精炼工艺要求.一般性的炼钢一连铸生产过程如图 产作业计划. 1所示：从高炉运来的高温铁水兑入转炉治炼成钢 炼钢一连铸静态计划编制问题是一个多目标多

北 京 科 技 大 学 学 报 第 36 卷 了分析，针对正在作业炉次提出了已分配设备不变 的时间修正模型，对于未作业炉次，建立了多目标非 线性 0--1 整数规划模型． 该方案能缩短动态调度时 间、维持生产的稳定性，但由于方案中保持正在作业 炉次的未加工操作已分配设备不变，因此无法适应 任意设备出现故障情况下的重计划． 文献［10］提出 了重调度炉次分类处理，针对正在作业炉次提出了 时间并行顺推算法，针对未作业炉次提出了基于遗 传算法和时间并行倒推的混合优化算法． 时间并行 顺推算法求解速度快，但其中炉次设备的分配仅通 过启发式规则进行确定，对于多约束的炼钢--连铸 重调度问题，有时难以求得可行解． 文献［11］提出 了一个由任务、推理和领域三模块组成的知识模型 去管理炼钢过程中的各种扰动问题，给出了一个重 调度的框架结构，但并未给出具体的模型和求解算 法． 目前的重计划方法大多拘于静态调度问题的解 决，对动态随机性处理能力不足． 钢厂生产作业计划是依据 EＲP( 企业资源计划 系统) 系统下达的生产批量计划分批编制的，重计 划是保证生产作业计划有效实施的重要形式． 考虑 到重计划信息表达的完整性，本文将重计划发生时 刻批次内的所有炉次分成已完成作业炉次集合、正 在作业炉次集合和未作业炉次集合，三个集合内所 有炉次的计划耦合成新的作业计划． 已完成作业炉 次的计划就是炉次的生产实绩信息，研究的重点是 如何编制正在作业炉次与未作业炉次的计划，以及 如何确保耦合后的作业计划满足炼钢--连铸重计划 问题的众多约束． 为更准确表达生产组织及工艺约 束等特征，将约束分成强制约束和柔性约束两大类， 针对正在作业炉次提出了基于时间顺推和遗传算法 的混合算法，针对未作业炉次提出了基于时间倒推 和遗传算法的混合算法，通过强制约束结合混合算 法搜寻可行解，然后在可行解中利用柔性约束搜寻 最优解． 重计划模块是生产计划调度系统［12］的重 要组成部分，通过对钢厂的实际数据进行的系统仿 真实验来验证方法的可行性和有效性． 1 重计划问题描述 1. 1 炼钢--连铸生产过程及作业计划制定流程 炼钢--连铸过程主要包含三个生产环节: 炼钢、 精炼和连铸． 炼钢与连铸环节各自包含一个并行机 组，而精炼环节一般包含多个并行机组，以实现不同 精炼工艺要求． 一般性的炼钢--连铸生产过程如图 1 所示: 从高炉运来的高温铁水兑入转炉冶炼成钢 水，钢水倒入转炉下台车上的钢包内，通过天车和台 车的运输作业，把钢水包运送至精炼环节，根据生产 工艺要求依次在不同的精炼设备上精炼钢水，精炼 完成后，再通过天车和台车，把钢水包运送至连铸并 实施浇铸，形成铸坯． 图 1 炼钢--连铸生产过程 Fig． 1 Production process of steelmaking-continuous casting 在钢厂生产调度中，炉次是指同一个转炉内冶 炼的钢水，由于一个炉次的钢水被装入一个钢包中， 所以从炼钢到连铸前被调度的工件均为炉次，炉次 是钢厂生产调度中最小的生产单元． 浇次是指在同 一连铸机上连续浇铸的炉次集合，是钢厂生产调度 中最大的生产单元． 炼钢--连铸作业计划制定流程 是: 首先按照技术标准将用户合同转化为生产合同， 编制炉次计划． 在炉次计划的基础上，结合热轧轧 制计划的要求，编制生产批量计划． 在生产批量计 划中，已经确定了浇次的连铸机以及浇次内炉次的 加工顺序和生产工艺． 最后，在生产批量计划的基 础上，进一步结合炼钢--连铸各环节生产能力，编制 生产作业计划，形成各炉次的火车时刻表． 本文的 研究内容就是基于生产批量计划和作业计划，研究 扰动时的重计划编制方法． 1. 2 炼钢--连铸重计划问题 生产作业计划的编制过程就是在满足各类约束 的前提下，给各炉次安排加工设备，并确定其在各设 备上的开始加工时间和结束加工时间． 当一批生产 作业计划生成后，调度员应尽可能按照该计划进行 调度和组织生产． 由于生产过程中的复杂性和不稳 定性，预定的生产作业计划在实施时可能因发生的 随机扰动而造成执行困难． 若扰动小，如时间存在 较小偏差、交换炉座，可通过生产计划调度系统中的 计划修复程序进行小范围的调整; 若扰动大，如设备 故障、设备启用、时间偏差过大以及任务变更，则必 须依据实时调度信息在原计划的基础上重新编制生 产作业计划． 炼钢--连铸静态计划编制问题是一个多目标多 ·116·

第1期 龙建宇等：基于遗传算法的炼钢一连铸重计划方法 ·117· 约束的NP难题，而重计划问题除了具有静态计划 序，因此操作总数也可以得出 编制的所有约束外，还必须兼顾扰动条件下原计划 B,重计划时，炉次Lg的第o(Lg的操作数， 完成偏差控制等特定约束，更具复杂性和挑战 1≤0g≤0(i,j)）个操作的运行状态.B,=0表示 性3.因此，将重计划问题中的约束分成强制约 “未加工”，By=1表示“正在进行”，Bm,=2表示 束和柔性约束.强制约束是保证计划可执行的约束 “己完成”.随着生产的运行，各炉次的B依次被 条件，柔性约束是促使计划更优化的约束条件 赋值 强制约束： 2:炉次集合，Lg∈2 (1)连浇生产约束.同一浇次内的炉次应在铸 2p,2m,24:2p是已完成作业的炉次集合，对于 机上无间断的被加工，相邻浇次间需要一定的时间 炉次Lg若Bg=2(og=1,2,…,0(i,j),则Lg∈ 间隔 2:2是未作业的炉次集合，对于炉次Lg,若B= (2)工艺约束.炉次应该按照生产批量计划中 0(og=1,2,…,0(i,j)),则Lg∈2w:2是正在作业 规定的加工操作类型和次序进行加工· 炉次集合，21=2-2m-2p (3)设备约束.同一时刻一个设备最多加工一 wo:重计划发生时刻，正在作业炉次Lg(Lg∈ 个炉次，故障设备不能加工炉次.计划中，设备开始 2)所处的操作数 加工第一炉的时间不能早于该设备的最早可用 时间. ,k筑，k到，：，k0k的表示原计划/重计 (4)工位作业时间与工位间运输时间约束.依 划/生产实际中炉次L,的第0，个操作在第g类设备 据生产要求和厂房布局，不同工位的作业时间与不 上的第k台设备上治炼g表示设备类，g=1,2,…, 同工位间的运输时间应该处于一个固定区间内. N,如g=1表示转炉类，有k=1,2,3,4,5台设备： (5)重计划时间约束.重计划发生时，炉次还 g=3表示RH类，有k=1,2,3台设备；g=N表示 未完成的操作的开始时间不能早于重计划发生 铸机类，有k=1,2,3,4,5台铸机.来自原计划 时间. 中，为已知解；k,是求解对象，为未知解：，来自生 柔性约束： 产实绩，为己知解 (1)铸机尽量提前开浇约束.生产批量计划中 WT:第g类设备的加工时间，加工时间具有上 规定了各铸机的开浇时间，在不早于该开浇时间的 下限，即WT∈[WT",WTm],可根据生产实绩数 前提下，铸机应尽量提前开浇.重计划时，若所有铸 据分析得出. 机已经开浇，该约束不起作用. TTg:第g类设备上的第k台设备到第g类 (2)生产稳定性约束.在动态环境下，为保障 设备上的第k台设备的运输时间，运输时间具有上 生产连续性和稳定性，重计划时，各炉次后续操作的 下限，即TT。∈TT,TT],可根据生产实 开始时间、结束时间和加工设备应尽量保证与原计 绩数据分析得出 划一致. ES:第g类设备上的第k台设备的最早可用 (3)设备利用率均衡约束.同一类设备的利用 时间.铸机的最早可用时间来自生产批量计划，其 率均衡，减少某些设备过度使用而产生故障造成的 他设备的最早可用时间根据生产实绩数据得到. 生产扰动，以提高生产稳定性 PS ()P"S ()P"S()PS 2 重计划编制方法 ()/PS(k0）/P”S(k0,）是炉次L的第o 个操作在第g类设备的第k个机器上的原计划开始 2.1符号定义 时间/重计划开始时间/实际开始时间.PS(y） L:表示浇次i的第j个炉次.浇次内各炉次的 来自原计划表，为已知解：PS(k)是求解对象， 加工顺序在生产批量计划中己给定 O(i,):炉次L从转炉到连铸工序的操作总 为未知解：P"S,()来自生产实绩，为已知解。 数，即炉次所经过的加工设备总数.O(,)=1(个 PE,(,）,PE,(k),P"E,(k,）:PEy 转炉)+精炼重数+1（个连铸机），由于生产工艺要 (k,)PE,(k0,）/PE,(k0,）是炉次Lg的第o 求的不同，即使在同一浇次中不同炉次的精炼重数 个操作在第g类设备的第k个机器上的原计划结束 也可能不一样，从而导致操作总数不同.生产批量 时间/重计划结束时间/实际结束时间.PE,() 计划中规定了各炉次治炼应该经历的精炼类型和次 来自原计划表，为已知解：PE,(k,)是求解对象

第 1 期 龙建宇等: 基于遗传算法的炼钢--连铸重计划方法 约束的 NP 难题，而重计划问题除了具有静态计划 编制的所有约束外，还必须兼顾扰动条件下原计划 完成偏差控制等特定约束，更具复杂性和挑战 性［13--14］． 因此，将重计划问题中的约束分成强制约 束和柔性约束． 强制约束是保证计划可执行的约束 条件，柔性约束是促使计划更优化的约束条件． 强制约束: ( 1) 连浇生产约束． 同一浇次内的炉次应在铸 机上无间断的被加工，相邻浇次间需要一定的时间 间隔． ( 2) 工艺约束． 炉次应该按照生产批量计划中 规定的加工操作类型和次序进行加工． ( 3) 设备约束． 同一时刻一个设备最多加工一 个炉次，故障设备不能加工炉次． 计划中，设备开始 加工第一炉的时间不能早于该设备的最早可用 时间． ( 4) 工位作业时间与工位间运输时间约束． 依 据生产要求和厂房布局，不同工位的作业时间与不 同工位间的运输时间应该处于一个固定区间内． ( 5) 重计划时间约束． 重计划发生时，炉次还 未完成的操作的开始时间不能早于重计划发生 时间． 柔性约束: ( 1) 铸机尽量提前开浇约束． 生产批量计划中 规定了各铸机的开浇时间，在不早于该开浇时间的 前提下，铸机应尽量提前开浇． 重计划时，若所有铸 机已经开浇，该约束不起作用． ( 2) 生产稳定性约束． 在动态环境下，为保障 生产连续性和稳定性，重计划时，各炉次后续操作的 开始时间、结束时间和加工设备应尽量保证与原计 划一致． ( 3) 设备利用率均衡约束． 同一类设备的利用 率均衡，减少某些设备过度使用而产生故障造成的 生产扰动，以提高生产稳定性． 2 重计划编制方法 2. 1 符号定义 Lij : 表示浇次 i 的第 j 个炉次． 浇次内各炉次的 加工顺序在生产批量计划中已给定． O( i，j) : 炉次 Lij 从转炉到连铸工序的操作总 数，即炉次所经过的加工设备总数． O( i，j) = 1( 个 转炉) + 精炼重数 + 1( 个连铸机) ，由于生产工艺要 求的不同，即使在同一浇次中不同炉次的精炼重数 也可能不一样，从而导致操作总数不同． 生产批量 计划中规定了各炉次冶炼应该经历的精炼类型和次 序，因此操作总数也可以得出． βijoij : 重计划时，炉次 Lij 的第 oij ( Lij 的操作数， 1≤oij≤O( i，j) ) 个操作的运行状态． βijoij = 0 表示 “未加工”，βijoij = 1 表示“正在进行”，βijoij = 2 表示 “已完成”． 随着生产的运行，各炉次的 βijoij 依次被 赋值． Ω: 炉次集合，Lij∈Ω． ΩP，ΩW，ΩH : ΩP 是已完成作业的炉次集合，对于 炉次 Lij ，若 βijoij = 2( oij = 1，2，…，O( i，j) ) ，则 Lij∈ ΩP ; ΩW 是未作业的炉次集合，对于炉次 Lij ，若 βijoij = 0( oij = 1，2，…，O( i，j) ) ，则 Lij∈ΩW ; ΩH 是正在作业 炉次集合，ΩH = Ω － ΩW － ΩP ． woij : 重计划发生时刻，正在作业炉次 Lij ( Lij∈ ΩH ) 所处的操作数． kg ijoij ，k' ijoij g ，k″ijoij g : kg ijoij /k' ijoij g /k″ijoij g 表示原计划/重计 划/生产实际中炉次 Lij的第 oij个操作在第 g 类设备 上的第 k 台设备上冶炼． g 表示设备类，g = 1，2，…， Ng，如 g = 1 表示转炉类，有 k = 1，2，3，4，5 台设备; g = 3表示 ＲH 类，有 k = 1，2，3 台设备; g = Ng 表示 铸机类，有 k = 1，2，3，4，5 台铸机． kg ijoij 来自原计划 中，为已知解; k' ijoij g 是求解对象，为未知解; k″ijoij g 来自生 产实绩，为已知解． WTg : 第 g 类设备的加工时间，加工时间具有上 下限，即 WTg∈［WTmin g ，WTmax g ］，可根据生产实绩数 据分析得出． TTkgk' g' : 第 g 类设备上的第 k 台设备到第 g'类 设备上的第 k'台设备的运输时间，运输时间具有上 下限，即 TTkgk' g' ∈［TTmin kgk' g'，TTmax kgk' g'］，可根据生产实 绩数据分析得出． ESkg : 第 g 类设备上的第 k 台设备的最早可用 时间． 铸机的最早可用时间来自生产批量计划，其 他设备的最早可用时间根据生产实绩数据得到． PSg ijoij ( kg ijoij ) ，P' Sg ijoij ( k' ijoij g ) ，P″ Sg ijoij ( k″ijoij g ) : PSg ijoij ( kg ijoij ) /P'Sg ijoij ( k' ijoij g ) / P″Sg ijoij ( k″ijoij g ) 是炉次 Lij的第 oij 个操作在第 g 类设备的第 k 个机器上的原计划开始 时间/重计划开始时间/实际开始时间． PSg ijoij ( kg ijoij ) 来自原计划表，为已知解; P'Sg ijoij ( k' ijoij g ) 是求解对象， 为未知解; P″Sg ijoij ( k″ijoij g ) 来自生产实绩，为已知解． PEg ijoij ( kg ijoij ) ，P' Eg ijoij ( k'ijoij g ) ，P″Eg ijoij ( k″ijoij g ) : PEg ijoij ( kg ijoij ) /P'Eg ijoij ( k' ijoij g ) / P″Eg ijoij ( k″ijoij g ) 是炉次 Lij的第 oij 个操作在第 g 类设备的第 k 个机器上的原计划结束 时间/重计划结束时间/实际结束时间． PEg ijoij ( kg ijoij ) 来自原计划表，为已知解; P'Eg ijoij ( k' ijoij g ) 是求解对象， ·117·

·118 北京科技大学学报 第36卷 为未知解：PE,(k)来自生产实绩，为已知解。 顺推和遗传算法的混合算法进行求解.对于2，中 2.2重计划编制方法 各炉次L,的重计划，构造一种基于时间倒推和遗传 在现实生产中，由于不可避免的随机扰动存在，使 算法的混合算法进行求解.整个重计划编制方法的 得计划与实绩往往存在偏差尤其当扰动过大时，必须 原理如图2(a)所示.图2(b)是以甘特图形式表达 根据扰动时的生产实际情况，进行炉次的重计划 的炼钢一连铸过程的重计划示例效果图，重计划的 进行重计划编制时，首先对炉次集合2进行分 扰动因素是流程中的3"LF发生故障.在此之前，原 类，将其分成已完成作业的炉次集合2、未作业的 计划在执行过程中还出现了一个扰动一炉次1运 炉次集合2和正在作业炉次集合2.对于2中 送至3"LF的实际时间稍大于计划时间，由于偏差较 各炉次L与其细，=，PS,(k,）=PS,(k,)， 小，因此能在满足强制约束④的前提下，缩短炉次1 PE(k）=PE,(k）(og=1,2,…,0(i,ji））. 从3"LF至2铸机的运输时间来保证炉次1按时开 对于2中各炉次L的重计划，构造一种基于时间 浇，从而避免了启用重计划求解算法. 扰动发生 重计划发生时刻 小扰动 已完成作业炉次 犹动识别与分析 计划修复处理 结束 1转炉 89406 正在作业炉次 大扰动 2”转炉2止3里517 未作业炉次 实时调度信息 重计划编制开始 原作业计划 PLF 183107 2LF 2 1411 31.F 9}56 护次计划分类 PRH 8911011 1铸机 891011 间间 已完成炉次 正在作业炉次 未作业炉次 2”铸机 1234567 3F故障 r转炉894011 各工 2”转炉1■3567 PS u-Ps 基于时间顺推 位最 基于时间倒推 VLF 83145L 和遗传算法的 i 和遗传算法的 PE (PE 用时 211067 混合算法 混合算法 291F 间 结束) 191 划 1 PRH 8191011 o=2.….04i) 约束库：强M约束+柔性约束 r铸机较小时▣偏差89101 2“铸机 1134567→ (a) b 图2炼钢一连铸重计划编制过程.()重计划编制原理：(b)重计划效果图 Fig.2 Replanning process of steelmaking-continuous casting:(a)principle of re-planning:(b)effect diagram of replanning 2.3基于时间递推和遗传算法的混合算法 而成.这里仅以PFGA为例详细介绍算法的结构， 基于时间递推和遗传算法的混合算法包含两个 其中也会简单标识出PDGA的不同之处. 算法：基于时间顺推和遗传算法的混合算法（以下 重计划编制开始时，2中的炉次L,只可能处 简称PFGA)与基于时间倒推和遗传算法的混合算 于两种状态：在工位上加工（存在某个0使得B= 法（以下简称PDGA).PFGA是针对2H中各炉次的 1)和在运输途中（不存在某个0使得B,=1).重 重计划编制算法，PDGA是针对2中各炉次的重 计划时，正在工位上加工的炉次必须安排在该工位 计划编制算法.两种算法的结构基本一样，但存在 上继续加工，而在运输途中的炉次的预定紧后加工 两个不同点：①2中的炉次的某些操作己经完成， 工位可以改变.P℉GA算法流程如下. 考虑到重计划的完整性，应将其实际冶炼信息转化 Step1:将炉次已完成的操作的实际冶炼信息转 为炉次的重计划信息，因此PFGA会比PDGA多出 变为该炉次的重计划信息并保存(PDGA中没有该 一个操作：②P℉GA中炉次的重计划是利用时间顺 操作). 推和染色体携带的信息编制而成，而PDGA中炉次 (1)将集合2赋予临时集合(，初始化炉次计 的重计划是利用时间倒推和染色体携带的信息编制 数器h,令h=1;

北 京 科 技 大 学 学 报 第 36 卷 为未知解; P″Eg ijoij ( k″ijoij g ) 来自生产实绩，为已知解． 2. 2 重计划编制方法 在现实生产中，由于不可避免的随机扰动存在，使 得计划与实绩往往存在偏差． 尤其当扰动过大时，必须 根据扰动时的生产实际情况，进行炉次的重计划． 进行重计划编制时，首先对炉次集合 Ω 进行分 类，将其分成已完成作业的炉次集合 ΩP、未作业的 炉次集合 ΩW 和正在作业炉次集合 ΩH ． 对于 ΩP 中 各炉次 Lij ，其 k' ijoij g = k″ijoij g ，P'Sg ijoij ( k' ijoij g ) = P″Sg ijoij ( k″ijoij g ) ， P'Eg ijoij ( k' ijoij g ) = P″Eg ijoij ( k″ijoij g ) ( oij = 1，2，…，O( i，j) ) ． 对于 ΩH 中各炉次 Lij的重计划，构造一种基于时间 顺推和遗传算法的混合算法进行求解． 对于 ΩW 中 各炉次 Lij的重计划，构造一种基于时间倒推和遗传 算法的混合算法进行求解． 整个重计划编制方法的 原理如图 2( a) 所示． 图 2( b) 是以甘特图形式表达 的炼钢--连铸过程的重计划示例效果图，重计划的 扰动因素是流程中的 3# LF 发生故障． 在此之前，原 计划在执行过程中还出现了一个扰动———炉次 1 运 送至 3# LF 的实际时间稍大于计划时间，由于偏差较 小，因此能在满足强制约束④的前提下，缩短炉次 1 从 3# LF 至 2# 铸机的运输时间来保证炉次 1 按时开 浇，从而避免了启用重计划求解算法． 图 2 炼钢--连铸重计划编制过程． ( a) 重计划编制原理; ( b) 重计划效果图 Fig． 2 Ｒe-planning process of steelmaking-continuous casting: ( a) principle of re-planning; ( b) effect diagram of re-planning 2. 3 基于时间递推和遗传算法的混合算法 基于时间递推和遗传算法的混合算法包含两个 算法: 基于时间顺推和遗传算法的混合算法( 以下 简称 PFGA) 与基于时间倒推和遗传算法的混合算 法( 以下简称 PDGA) ． PFGA 是针对 ΩH 中各炉次的 重计划编制算法，PDGA 是针对 ΩW 中各炉次的重 计划编制算法． 两种算法的结构基本一样，但存在 两个不同点: ① ΩH 中的炉次的某些操作已经完成， 考虑到重计划的完整性，应将其实际冶炼信息转化 为炉次的重计划信息，因此 PFGA 会比 PDGA 多出 一个操作; ② PFGA 中炉次的重计划是利用时间顺 推和染色体携带的信息编制而成，而 PDGA 中炉次 的重计划是利用时间倒推和染色体携带的信息编制 而成． 这里仅以 PFGA 为例详细介绍算法的结构， 其中也会简单标识出 PDGA 的不同之处． 重计划编制开始时，ΩH 中的炉次 Lij只可能处 于两种状态: 在工位上加工( 存在某个 oij使得 βijoij = 1) 和在运输途中 ( 不存在某个 oij使得 βijoij = 1) ． 重 计划时，正在工位上加工的炉次必须安排在该工位 上继续加工，而在运输途中的炉次的预定紧后加工 工位可以改变． PFGA 算法流程如下． Step 1: 将炉次已完成的操作的实际冶炼信息转 变为该炉次的重计划信息并保存( PDGA 中没有该 操作) ． ( 1) 将集合 ΩH 赋予临时集合 ζ，初始化炉次计 数器 h，令 h = 1; ·118·

第1期 龙建宇等：基于遗传算法的炼钢一连铸重计划方法 ·119· (2)若！不为空，则继续执行以下步骤，否则执 Step3:初始化迭代计数器d,令d=1. 行Step2: Step4:若d小于初始设定的迭代次数altNum, (3)取出炉次h,初始化炉次操作数o,=1; 则继续执行以下步骤，否则执行Step11. (4)若o≤0(i,),则继续执行以下步骤，否则 Step5:将种群P赋予临时集合亚，初始化染色 转(9)； 体计数器c,令c=1. (5)若By=2,则k,=y,PS,(k,）= Step6:若亚不为空，则继续执行以下步骤，否 PS(kg),PE(k）=PE,(k),转(8)； 则执行Step 10. (6)若By=1,则k的=k0,PS,(k,)= Step7:取出染色体c,利用时间顺推和染色体 PS,(),依据强制约束④随机产生一个作业时 携带的信息将2：中各炉次的剩余操作编制重计划 间WTPE,(k,)=PS,(k0,）+WTg,令wog= (PDGA中是时间倒推，这意味着炉次首先计算末端 0,转(9)： 工序铸机上的计划，然后依据炉次所规定加工操作 (7）若B,=0,则令w0g=0g-1,转(9)； 类型和次序以及染色体的信息，从后往前依次编制 (8)令0g=0+1,转(4)； 计划). (9)从！中删除炉次h,令h=h+1,转(2) (1)将集合2赋予临时集合飞，初始化炉次计 Step2:构造初始种群P. 数器h,令h=1; (1)按初始设定的种群大小popSize随机产生 (2)若（不为空，则继续执行以下步骤，否则执 符合数量的染色体.染色体由两部分组成：第一部 行Step8; 分代表所有计划炉次的加工路径信息，其长度等于 (3)取出炉次h,初始化炉次操作数og=wog+ 1: 所有炉次还未执行的操作数(B,=0)的总和，该部 分染色体由自然数字组成，对于炉次L,若 (4)若0<0(i,),则继续执行以下步骤，否则 转(6)； 0(i,j》-wog=2,则Lg对应的染色体模块24]表示 g+)=2,6=4:第二部分代表铸机开浇信 (5)已知h的第o:-1个操作的加工设备为 息，其大小等于重计划发生时还未开浇的铸机个数， k,-),根据染色体编码规则，找出h的第og个操 若铸机全部开浇，则染色体不包含第二部分，该部分 作的加工设备k,依据强制约束④随机产生一个 染色体由自然数字组成，对于铸机k,生产批量计 该工位间的运输时间TT,则PS,(k,)= 划中规定其最早开浇时间为ES。,则：对应的染 PEy-)(k气，-)）+TTg,依据强制约束④随机 色体模块B]表示其开浇时间为ESy,+3min.假 产生一个作业时间WT,则PE,(k)= 设流程中具有四类设备：有五台转炉(g=1),五台 PS,(k,)+WT,转(8)： LF(g=2),三台RH(g=3),五台铸机(g=4),重计 (6)若o=0(i,j),则继续执行以下步骤，否则 划发生时，3铸机和5铸机均未开浇.若24中有炉 转(9)； 次L4L2,和L2,它们所规定的加工操作类型分别 (7)根据染色体编码规则，找出炉次h的第0 是：转炉-LF一铸机、转炉RH一铸机和转炉LFRH- (i,》个操作的加工设备k),若k品)己经开浇 铸机.重计划发生时可得出：O(i,)-wo,=1(i= 则依据L4计划中规定的h在铸机k品)上的浇铸 1,j=4),0(i,j)-w0=2(i=2,j=1),0(i,j）- 顺序和连浇规则可计算h浇铸的开始时间PS, w0=3(i=2,j=2).则染色体【322415)(32)]表 (k品）和结束时间PE0(kn）,若k还 示：L4后续加工路径为铸机3，L21后续加工路径为 未开浇则依据染色体编码规则可计算出k励的开 RH2-铸机2，L22后续加工路径为LF4RH1-铸机5； 浇时间，进而得出h浇铸的开始时间和结束时间： 3"铸机的开浇时间为ES+3min,5铸机的开浇时 (8)令0=0+1，转(4)； 间为ES,4+2min: (9)从（中删除炉次h,令h=h+1,转(2） (2)检查染色体的合法性并将不合法的染色体 Step8:针对所有已重排计划的炉次（即包括2， 修复.检查原则有三条：①染色体第一部分中的自 中的炉次，PDGA中则包括2，和2中的炉次)，利 然数字必须要有相对应的设备：②染色体中不能出 用强制约束检查依靠染色体c携带的信息编制的重 现故障设备；③炉次的浇铸铸机必须和生产批量计 计划是否合理，若合理则将染色体c标记为合格，对 划中指定的铸机一致. 所有己重排计划的炉次进行约束满足检测能够保证

第 1 期 龙建宇等: 基于遗传算法的炼钢--连铸重计划方法 ( 2) 若 ζ 不为空，则继续执行以下步骤，否则执 行 Step 2; ( 3) 取出炉次 h，初始化炉次操作数 oij = 1; ( 4) 若 oij≤O( i，j) ，则继续执行以下步骤，否则 转( 9) ; ( 5) 若 βijoij = 2，则 k' ijoij g = k″ijoij g ，P' Sg ijoij ( k' ijoij g ) = P″Sg ijoij ( k″ijoij g ) ，P'Eg ijoij ( k' ijoij g ) = P″Eg ijoij ( k″ijoij g ) ，转( 8) ; ( 6) 若 βijoij = 1，则 k' ijoij g = k″ijoij g ，P' Sg ijoij ( k' ijoij g ) = P″Sg ijoij ( k″ijoij g ) ，依据强制约束④随机产生一个作业时 间 WTg，P'Eg ijoij ( k' ijoij g ) = P'Sg ijoij ( k' ijoij g ) + WTg，令 woij = oij ，转( 9) ; ( 7) 若 βijoij = 0，则令 woij = oij － 1，转( 9) ; ( 8) 令 oij = oij + 1，转( 4) ; ( 9) 从 ζ 中删除炉次 h，令 h = h + 1，转( 2) ． Step 2: 构造初始种群 P． ( 1) 按初始设定的种群大小 popSize 随机产生 符合数量的染色体． 染色体由两部分组成: 第一部 分代表所有计划炉次的加工路径信息，其长度等于 所有炉次还未执行的操作数( βijoij = 0) 的总和，该部 分染 色 体 由 自 然 数 字 组 成，对 于 炉 次 Lij ，若 O( i，j) － woij = 2，则 Lij对应的染色体模块［24］表示 k″ij( woij + 1) g = 2，k″ijO( i，j) g' = 4; 第二部分代表铸机开浇信 息，其大小等于重计划发生时还未开浇的铸机个数， 若铸机全部开浇，则染色体不包含第二部分，该部分 染色体由自然数字组成，对于铸机 k Ng，生产批量计 划中规定其最早开浇时间为 ESkNg，则 k Ng对应的染 色体模块［3］表示其开浇时间为 ESkNg + 3 min． 假 设流程中具有四类设备: 有五台转炉( g = 1) ，五台 LF( g = 2) ，三台 ＲH( g = 3) ，五台铸机( g = 4) ，重计 划发生时，3# 铸机和 5# 铸机均未开浇． 若 ΩH 中有炉 次 L14、L21和 L22，它们所规定的加工操作类型分别 是: 转炉--LF--铸机、转炉--ＲH--铸机和转炉--LF--ＲH- -铸机． 重计划发生时可得出: O( i，j) － woij = 1 ( i = 1，j = 4) ，O( i，j) － woij = 2 ( i = 2，j = 1) ，O( i，j) － woij = 3( i = 2，j = 2) ． 则染色体［( 322415) ( 32) ］表 示: L14后续加工路径为铸机 3，L21后续加工路径为 ＲH2--铸机 2，L22后续加工路径为 LF4--ＲH1--铸机 5; 3# 铸机的开浇时间为 ES34 + 3min，5# 铸机的开浇时 间为 ES54 + 2min ; ( 2) 检查染色体的合法性并将不合法的染色体 修复． 检查原则有三条: ①染色体第一部分中的自 然数字必须要有相对应的设备; ②染色体中不能出 现故障设备; ③炉次的浇铸铸机必须和生产批量计 划中指定的铸机一致． Step 3: 初始化迭代计数器 d，令 d = 1． Step 4: 若 d 小于初始设定的迭代次数 altNum， 则继续执行以下步骤，否则执行 Step 11． Step 5: 将种群 P 赋予临时集合 Ψ，初始化染色 体计数器 c，令 c = 1． Step 6: 若 Ψ 不为空，则继续执行以下步骤，否 则执行 Step 10． Step 7: 取出染色体 c，利用时间顺推和染色体 携带的信息将 ΩH 中各炉次的剩余操作编制重计划 ( PDGA 中是时间倒推，这意味着炉次首先计算末端 工序铸机上的计划，然后依据炉次所规定加工操作 类型和次序以及染色体的信息，从后往前依次编制 计划) ． ( 1) 将集合 ΩH 赋予临时集合 ζ，初始化炉次计 数器 h，令 h = 1; ( 2) 若 ζ 不为空，则继续执行以下步骤，否则执 行 Step 8; ( 3) 取出炉次 h，初始化炉次操作数 oij = woij + 1; ( 4) 若 oij ＜ O( i，j) ，则继续执行以下步骤，否则 转( 6) ; ( 5) 已知 h 的第 oij － 1 个操作的加工设备为 k' ij( oij － 1) g ，根据染色体编码规则，找出 h 的第 oij个操 作的加工设备 k' ijoij g' ，依据强制约束④随机产生一个 该工位 间 的 运 输 时 间 TTk' gk' g'，则 P' Sg' ijoij ( k' ijoij g' ) = P'Eg ij( oij － 1) ( k' ij( oij － 1) g ) + TTk' gk' g'，依据强制约束④随机 产生 一 个 作 业 时 间 WTg'，则 P' Eg' ijoij ( k'ijoij g' ) = P'Sg' ijoij ( k' ijoij g' ) + WTg'，转( 8) ; ( 6) 若 oij = O( i，j) ，则继续执行以下步骤，否则 转( 9) ; ( 7) 根据染色体编码规则，找出炉次 h 的第 O ( i，j) 个操作的加工设备 k' ijO( i，j) g ，若 k' ijO( i，j) g 已经开浇 则依据 L4 计划中规定的 h 在铸机 k' ijO( i，j) g 上的浇铸 顺序和连浇规则可计算 h 浇铸的开始时间 P'Sg ijO( i，j) ( k' ijO( i，j) g ) 和结束时间 P'Eg ijO( i，j) ( k' ijO( i，j) g ) ，若 k' ijO( i，j) g 还 未开浇则依据染色体编码规则可计算出 k' ijO( i，j) g 的开 浇时间，进而得出 h 浇铸的开始时间和结束时间; ( 8) 令 oij = oij + 1，转( 4) ; ( 9) 从 ζ 中删除炉次 h，令 h = h + 1，转( 2) ． Step 8: 针对所有已重排计划的炉次( 即包括 ΩP 中的炉次，PDGA 中则包括 ΩP 和 ΩH 中的炉次) ，利 用强制约束检查依靠染色体 c 携带的信息编制的重 计划是否合理，若合理则将染色体 c 标记为合格，对 所有已重排计划的炉次进行约束满足检测能够保证 ·119·