第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·
·120 北京科技大学学报 第36卷 全局计划的可行性. 种群P中没有一条合格染色体，则执行Step2. Step9:从亚中删除染色体c,令c=c+1,执行 3应用实例 Step 6. Step10:构造下一代种群P,令d=d+1,执行 某大型炼钢厂有转炉五座；精炼设备八台：五台 Step 4. LF,三台RH;连铸机五台.结合本文提出的方法，采 (1)将上一代种群中被标记为合格的染色体直 用Visual Studio2005.net开发了生产计划调度系统 接复制到下一代种群P中. 中的重计划模块.系统运行的后台数据库采用 (2)执行杂交操作，产生一批染色体，其个数 Microsoft SQL Server2005,利用与L4/L3建立的数 为上一代种群中不合格染色体总数与杂交概率的 据通信接口，从企业Oracle数据库中获得系统运行 乘积.杂交操作采用参数化的均匀交叉法的.父 相关数据.统计生产实绩数据得出设备加工时间和 代1和父代2进行杂交，每个基因在遗传时投掷一 工位间运输时间如表1和表2所示.以表3中的浇 枚硬币，出现正面则遗传父代1的基因，出现反面 次计划编制的初始作业计划（图3）为基础，通过设 则遗传父代2的基因.正反面出现的概率可以相 置生产扰动来进行仿真实验.具体设计了两组实验 同也可以不同，本文采用相同的概率。参数化的均 来验证重计划方法的可行性和有效性，分别是炉次 匀交叉法能保证合法的父代产生的子代一定是合 延迟到达下的重计划和转炉故障下的重计划.遗传 法的. 算法参数设置为：种群大小100，进化代数300，交叉 (3)执行变异操作，产生一批染色体，其个数为 概率0.9，变异概率0.1. 上一代种群中不合格染色体总数与变异概率的乘 表1设备加工时间 积.本文使用的变异操作不同于传统的基因突变方 Table 1 Process time of equipment 法，而是采用产生初始种群的方法随机产生一批合 转炉+ 法的染色体 设备 LF RH 铸机 炉后处理 Step 11:在末代种群P中的合格染色体中利用 加工时间/min[40,42,45]B5,40,45][20,26,30B0,43,56 柔性约束选取最优解作为最终解，算法结束.选取 注：[门]内第1个数为最小值，第2个数为平均值，第3个数为最 时，柔性约束①、②和③所占权重依次减小.若末代 大值 表2工位间运输时间 Table 2 Transportation time between equipments min LFI LF2 LF3 LF4 LF5 RHI RH2 RH3 CCI CC2 CC3 CC4 CC5 BOF1 30% 31分 27 280 30% BOF2 30哈 30% 29% 29始 31第 BOF3 29% 30暗 28最 296 320 BOF4 43 46 30时 259 27 BOF5 402 437 29 237 27 LFI 8品 278 30竖 56 616 28% 30 315 LF2 7品 288 30培 的 5品 285 318 32 LF3 27k 150 270 28 7i3 18 198 LF4 309 185 78 29第 30始 169 9%1 8品 LF5 31贤 192 7f。 30品 313 179 9 87 RHI 87: 9品 278 30点 31始 RH2 27品 28品 7落 198 19骋 RH3 284 28 15 7 注：a6中a表示平均值，b表示最小值，c表示最大值 初始计划中炉次8在转炉1上的开始时间为 LF2的运输时间为29min,由表1可知转炉工位的 11:00,当计划执行到该时刻时，炉次8未准时到达. 加工时间区间为40,45]，由表2可知转炉1到LF2 计划中炉次8在转炉1上冶炼43min,从转炉1到 的运输时间区间为24,37]，因此当炉次8延迟到
北 京 科 技 大 学 学 报 第 36 卷 全局计划的可行性． Step 9: 从 Ψ 中删除染色体 c，令 c = c + 1，执行 Step 6． Step 10: 构造下一代种群 P，令 d = d + 1，执行 Step 4． ( 1) 将上一代种群中被标记为合格的染色体直 接复制到下一代种群 P 中． ( 2) 执行杂交操作，产生一批染色体，其个数 为上一代种群中不合格染色体总数与杂交概率的 乘积． 杂交操作采用参数化的均匀交叉法［15］． 父 代 1 和父代 2 进行杂交，每个基因在遗传时投掷一 枚硬币，出现正面则遗传父代 1 的基因，出现反面 则遗传父代 2 的基因． 正反面出现的概率可以相 同也可以不同，本文采用相同的概率． 参数化的均 匀交叉法能保证合法的父代产生的子代一定是合 法的． ( 3) 执行变异操作，产生一批染色体，其个数为 上一代种群中不合格染色体总数与变异概率的乘 积． 本文使用的变异操作不同于传统的基因突变方 法，而是采用产生初始种群的方法随机产生一批合 法的染色体． Step 11: 在末代种群 P 中的合格染色体中利用 柔性约束选取最优解作为最终解，算法结束． 选取 时，柔性约束①、②和③所占权重依次减小． 若末代 种群 P 中没有一条合格染色体，则执行 Step 2． 3 应用实例 某大型炼钢厂有转炉五座; 精炼设备八台: 五台 LF，三台 ＲH; 连铸机五台． 结合本文提出的方法，采 用 Visual Studio 2005． net 开发了生产计划调度系统 中的 重 计 划 模 块． 系统运行的后台数据库采用 Microsoft SQL Server 2005，利用与 L4 /L3 建立的数 据通信接口，从企业 Oracle 数据库中获得系统运行 相关数据． 统计生产实绩数据得出设备加工时间和 工位间运输时间如表 1 和表 2 所示． 以表 3 中的浇 次计划编制的初始作业计划( 图 3) 为基础，通过设 置生产扰动来进行仿真实验． 具体设计了两组实验 来验证重计划方法的可行性和有效性，分别是炉次 延迟到达下的重计划和转炉故障下的重计划． 遗传 算法参数设置为: 种群大小 100，进化代数 300，交叉 概率 0. 9，变异概率 0. 1． 表 1 设备加工时间 Table 1 Process time of equipment 设备 转炉 + 炉后处理 LF ＲH 铸机 加工时间/min ［40，42，45］ ［35，40，45］ ［20，26，30］ ［30，43，56］ 注: ［］内第 1 个数为最小值，第 2 个数为平均值，第 3 个数为最 大值． 表 2 工位间运输时间 Table 2 Transportation time between equipments min LF1 LF2 LF3 LF4 LF5 ＲH1 ＲH2 ＲH3 CC1 CC2 CC3 CC4 CC5 BOF1 3024 36 3124 37 2723 34 2822 38 3026 36 BOF2 3023 35 3024 36 2924 36 2922 38 3126 37 BOF3 2923 35 3025 37 2822 38 2924 36 3227 38 BOF4 4335 50 4636 55 3024 35 2520 33 2721 35 BOF5 4034 48 4337 50 2922 36 2317 34 2721 34 LF1 83 11 2715 50 3017 52 53 15 63 16 2812 46 3015 50 3115 50 LF2 73 12 2816 50 3018 55 75 17 53 15 2813 49 3116 50 3216 51 LF3 2717 48 65 9 1510 30 2720 41 2824 42 75 13 188 25 1910 28 LF4 3016 49 186 22 75 9 2915 45 3015 45 169 19 96 11 85 13 LF5 3118 51 199 25 76 10 3015 50 3117 50 1710 26 98 12 87 11 ＲH1 87 11 97 12 2710 45 3015 48 3114 49 ＲH2 2719 40 2823 40 75 13 1910 26 1911 27 ＲH3 2814 44 2815 46 155 22 75 13 74 13 注: ac b 中 a 表示平均值，b 表示最小值，c 表示最大值． 初始计划中炉次 8 在转炉 1 上的开始时间为 11: 00，当计划执行到该时刻时，炉次 8 未准时到达． 计划中炉次 8 在转炉 1 上冶炼 43 min，从转炉 1 到 LF2 的运输时间为 29 min，由表 1 可知转炉工位的 加工时间区间为［40，45］，由表 2 可知转炉 1 到 LF2 的运输时间区间为［24，37］，因此当炉次 8 延迟到 ·120·
第1期 龙建宇等：基于遗传算法的炼钢一连铸重计划方法 ·121· 达时间大于8min时，将影响炉次在下游工位上的 从图3中可以看出：转炉1、2，LF1、2,RH1,铸机1、2 加工.重计划启动时刻为炉次到达时刻，实验1中 形成一个区域：转炉3，L3,RH2,铸机3形成一个 炉次8延迟20min到达，重计划结果如图4所示. 区域：转炉4、5，LF4、5,RH3,铸机4、5形成一个区 对比图3和图4可知，算法主要是通过降低铸机1 域对比图3和图5可知，转炉1的故障打破了这 的拉速，延长炉次7的浇铸时间来处理该生产扰动 个规律，但新的作业计划仍然满足所有的强制约束， 表3浇次计划 因此是可行的 Table 3 Cast plan 转的1 浇次号浇次内炉数钢种 工艺路径 目标铸机 转炉 与4 6 A BOF-F-CC 1# 转炉5 工立上士中文口 1F1 四口口口口口口 2 5 B BOF-F-CC 1 LF2 h口a口t与o 13 12T口c2aono C g 1F4 BOFJF-RH-CC D BOFLF-CC 3+ RHI RH 的中西中0应西出 5 5机1 BOF-F-CC 3# 之中□工 52 53 十十2工 6 > F BOF-FRH-CC 4 机4 1发 G BOF-F-CC 5* TD60 上午0800上午1000上午1200 上午0200 图5转护故障下的重计划 转炉1 Fig.5 Re-planning under basic oxygen fumnace failure 转的2 转的3 转的4 铸的5 结论 士口t口口中拉口口▣ (1)针对多约束的炼钢一连铸重计划问题，将 4 ”C产上发口 上工 RHI 问题中的约束分成强制约束和柔性约束两类.强制 声当面计与 RH3 机1 约束是保证作业计划可执行的约束条件，而柔性约 3 束是促使作业计划更优化的约束条件.求解算法首 回 机5 边上进4喷白 先利用强制约束得出可行解，然后在可行解中利用 上午0600 上午0800上午10.00下午1200下午0200 柔性约束找出最优解。 图3初始生产作业计划 (2)针对生产计划执行过程中发生的随机扰 Fig.3 Original production plan 动，按扰动的性质对其进行分类处理：针对小型扰 转炉1 动，在保证全局计划满足强制约束的前提下，设计了 转炉2 转炉3引 转护4 计划修复程序进行小范围调整来修改原计划：针对 转5 中 士口a口口口中口 口应和 大型扰动，提出了以时间递推和遗传算法的混合算 12 1F3 t竹的R间em口2 法为核心的重计划求解方法 (3)采用生产实绩数据进行的仿真实验结果表 RHI tH. 明，提出的重计划编制方法能处理炼钢一连铸生产 体机I 机 过程中的典型生产扰动，并有效地制定出可执行的 机3 阵机4 12中效工口 铸机5 时p十中特的四的回 重计划方案，系统具较强的现场适应性 上午0600 上午0800上午10.00 下午1200下午0200 图4炉次延迟到达下的重计划 :考文献 Fig.4 Re-planning under heat delayed arrival [1]Yu G,Tian N Y,Xu A J.Computer-aided simulation of steelmak- 实验2为转炉故障下的重计划.当计划执行到 ing-continuous casting production scheduling.J Univ Sci Technol 10:55时，转炉1出现故障，此时启动重计划，重计 Beijing,2009,31(9):1183 划结果如图5所示.由于生产计划编制中存在铸机 (于港，田乃媛，徐安军.炼钢一连铸区段生产调度与计算机 尽量提前开浇约束（柔性约束①），因此在设备选择 仿真.北京科技大学学报，2009,31(9)：1183) 2] Liu Q,Huang X W,Fu P Y.Production mode optimization of a 时，炉次会选择到达目标铸机运输时间较短的设备 steelmaking workshop system.J Univ Sci Technol Beijing,2005, 进行加工，这就导致计划中出现了区域对应现象. 27(6):736
第 1 期 龙建宇等: 基于遗传算法的炼钢--连铸重计划方法 达时间大于 8 min 时，将影响炉次在下游工位上的 加工． 重计划启动时刻为炉次到达时刻，实验 1 中 炉次 8 延迟 20 min 到达，重计划结果如图 4 所示． 对比图 3 和图 4 可知，算法主要是通过降低铸机 1 的拉速，延长炉次 7 的浇铸时间来处理该生产扰动． 表 3 浇次计划 Table 3 Cast plan 浇次号 浇次内炉数 钢种 工艺路径 目标铸机 1 6 A BOF-LF-CC 1# 2 5 B BOF-LF-CC 1# 3 5 C BOF-LF-ＲH-CC 2# 4 5 D BOF-LF-CC 3# 5 4 E BOF-LF-CC 3# 6 7 F BOF-LF-ＲH-CC 4# 7 8 G BOF-LF-CC 5# 图 3 初始生产作业计划 Fig． 3 Original production plan 图 4 炉次延迟到达下的重计划 Fig． 4 Ｒe-planning under heat delayed arrival 实验 2 为转炉故障下的重计划． 当计划执行到 10: 55 时，转炉 1 出现故障，此时启动重计划，重计 划结果如图 5 所示． 由于生产计划编制中存在铸机 尽量提前开浇约束( 柔性约束①) ，因此在设备选择 时，炉次会选择到达目标铸机运输时间较短的设备 进行加工，这就导致计划中出现了区域对应现象． 从图 3 中可以看出: 转炉 1、2，LF1、2，ＲH1，铸机 1、2 形成一个区域; 转炉 3，LF3，ＲH2，铸机 3 形成一个 区域; 转炉 4、5，LF4、5，ＲH3，铸机 4、5 形成一个区 域． 对比图 3 和图 5 可知，转炉 1 的故障打破了这 个规律，但新的作业计划仍然满足所有的强制约束， 因此是可行的． 图 5 转炉故障下的重计划 Fig． 5 Ｒe-planning under basic oxygen furnace failure 4 结论 ( 1) 针对多约束的炼钢--连铸重计划问题，将 问题中的约束分成强制约束和柔性约束两类． 强制 约束是保证作业计划可执行的约束条件，而柔性约 束是促使作业计划更优化的约束条件． 求解算法首 先利用强制约束得出可行解，然后在可行解中利用 柔性约束找出最优解． ( 2) 针对生产计划执行过程中发生的随机扰 动，按扰动的性质对其进行分类处理: 针对小型扰 动，在保证全局计划满足强制约束的前提下，设计了 计划修复程序进行小范围调整来修改原计划; 针对 大型扰动，提出了以时间递推和遗传算法的混合算 法为核心的重计划求解方法． ( 3) 采用生产实绩数据进行的仿真实验结果表 明，提出的重计划编制方法能处理炼钢--连铸生产 过程中的典型生产扰动，并有效地制定出可执行的 重计划方案，系统具较强的现场适应性． 参 考 文 献 ［1］ Yu G，Tian N Y，Xu A J． Computer-aided simulation of steelmaking-continuous casting production scheduling． J Univ Sci Technol Beijing，2009，31( 9) : 1183 ( 于港，田乃媛，徐安军． 炼钢--连铸区段生产调度与计算机 仿真． 北京科技大学学报，2009，31( 9) : 1183) ［2］ Liu Q，Huang X W，Fu P Y． Production mode optimization of a steelmaking workshop system． J Univ Sci Technol Beijing，2005， 27( 6) : 736 ·121·
·122 北京科技大学学报 第36卷 (刘青，黄星武，富平原.炼钢厂系统生产模式优化.北京科 method and its application for steelmaking-casting.Syst Eng Theory 技大学学报，2005,27(6)：736) Pact,2012,32(4):826 3]Tang LX,Liu J Y,Rong A Y,et al.A review of planning and (庞新富，俞胜平，罗小川，等.混合Jobshop炼钢-连铸重调 scheduling systems and methods for integrated steel production. 度方法及其应用.系统工程理论与实践，2012,32(4)：826) EurJ0 per Res,2001,133(1）:1 [10]Zheng Z,Zhu D F,Gao X Q.An approach of production sched- 4]Atighehchian A,Bijari M,Tarkesh H.A novel hybrid algorithm uling and replanning in a steelmaking-continuous casting plant.I for scheduling steel-making continuous casting production.Comput Chongqing Univ,2008,31(7)820 0 per Res,2009,36(8):2450 (郑忠，朱道飞，高小强.钢厂炼钢一连铸生产调度及重计划 5]Wang H B,Xu A J,Yao L,et al.Appling an improved genetic 方法.重庆大学学报，2008,31(7)：820) algorithm for solving the production scheduling problem of steel- [11]Roy R,Adesola B A,Thornton S.Development of a knowledge making and continuous casting.J Unir Sci Technol Beijing,2010, model for managing schedule disturbance in steel-making.Int J 32(9):1232 Prod Res,2004,42(18):3975 (汪红兵，徐安军，姚琳，等。应用改进遗传算法求解炼钢连 [12]Chen K,Zheng Z,Gao X Q,et al.Development of planning and 铸生产调度问题.北京科技大学学报，2010,32(9)：1232) scheduling system for steelmaking-continuous casting.Comput 6]Kovacic M.Sarler B.Genetic algorithm-based batch filling sched- Eng4ppl,2013,49(1):62 uling in the steel industry.Mater Manuf Processes,2011,26(3): (陈开，郑忠，高小强，等.炼钢一连铸生产计划调度系统开 464 发.计算机工程与应用，2013,49(1)：62) Missbauer H,Hauber W,Stadler W.A scheduling system for the [13]Gupta J N D.Two-stage hybrid flowshop scheduling problem.J steelmaking-continuous casting process:a case study from the 0 per Res Soc,1988,39(4):359 steel-making industry.Int J Prod Res,2009,47(15):4147 [14]Cowling P,Johansson M.Using real time information for effective [8]Tang L X,Guan J,Hu G F.Steelmaking and refining coordinated dynamic scheduling.Eur J Oper Res,2002,139 (2):230 scheduling problem with waiting time and transportation considera- [15]Gongalves J F.de Magalhaes Mendes,Resende M G C.A tion.Comput Ind Eng,2010,58:239 hybrid genetic algorithm for the job shop scheduling problem.Eur 9]Pang X F,Yu P,Luo X C,et al.Hybrid job shop rescheduling J0 per Res,2005,167(1):77
北 京 科 技 大 学 学 报 第 36 卷 ( 刘青，黄星武，富平原． 炼钢厂系统生产模式优化． 北京科 技大学学报，2005，27( 6) : 736) ［3］ Tang L X，Liu J Y，Ｒong A Y，et al． A review of planning and scheduling systems and methods for integrated steel production． Eur J Oper Ｒes，2001，133( 1) : 1 ［4］ Atighehchian A，Bijari M，Tarkesh H． A novel hybrid algorithm for scheduling steel-making continuous casting production． Comput Oper Ｒes，2009，36( 8) : 2450 ［5］ Wang H B，Xu A J，Yao L，et al． Appling an improved genetic algorithm for solving the production scheduling problem of steelmaking and continuous casting． J Univ Sci Technol Beijing，2010， 32( 9) : 1232 ( 汪红兵，徐安军，姚琳，等． 应用改进遗传算法求解炼钢连 铸生产调度问题． 北京科技大学学报，2010，32( 9) : 1232) ［6］ Kovacˇicˇ M，arler B． Genetic algorithm-based batch filling scheduling in the steel industry． Mater Manuf Processes，2011，26( 3) : 464 ［7］ Missbauer H，Hauber W，Stadler W． A scheduling system for the steelmaking-continuous casting process: a case study from the steel-making industry． Int J Prod Ｒes，2009，47( 15) : 4147 ［8］ Tang L X，Guan J，Hu G F． Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration． Comput Ind Eng，2010，58: 239 ［9］ Pang X F，Yu S P，Luo X C，et al． Hybrid job shop rescheduling method and its application for steelmaking-casting． Syst Eng Theory Pract，2012，32( 4) : 826 ( 庞新富，俞胜平，罗小川，等． 混合 Jobshop 炼钢--连铸重调 度方法及其应用． 系统工程理论与实践，2012，32( 4) : 826) ［10］ Zheng Z，Zhu D F，Gao X Q． An approach of production scheduling and replanning in a steelmaking-continuous casting plant． J Chongqing Univ，2008，31( 7) : 820 ( 郑忠，朱道飞，高小强． 钢厂炼钢--连铸生产调度及重计划 方法． 重庆大学学报，2008，31( 7) : 820) ［11］ Ｒoy Ｒ，Adesola B A，Thornton S． Development of a knowledge model for managing schedule disturbance in steel-making． Int J Prod Ｒes，2004，42( 18) : 3975 ［12］ Chen K，Zheng Z，Gao X Q，et al． Development of planning and scheduling system for steelmaking-continuous casting． Comput Eng Appl，2013，49( 1) : 62 ( 陈开，郑忠，高小强，等． 炼钢--连铸生产计划调度系统开 发． 计算机工程与应用，2013，49( 1) : 62) ［13］ Gupta J N D． Two-stage hybrid flowshop scheduling problem． J Oper Ｒes Soc，1988，39( 4) : 359 ［14］ Cowling P，Johansson M． Using real time information for effective dynamic scheduling． Eur J Oper Ｒes，2002，139( 2) : 230 ［15］ Gonalves J F，de Magalha珓es Mendes，Ｒesende M G C． A hybrid genetic algorithm for the job shop scheduling problem． Eur J Oper Ｒes，2005，167( 1) : 77 ·122·