钢坯热轧加热炉区生产调度模型与算法

D0I:10.13374M.issn1001-053x.2012.07.014 第34卷第7期 北京科技大学学报 Vol.34 No.7 2012年7月 Journal of University of Science and Technology Beijing Jul.2012 钢坯热轧加热炉区生产调度模型与算法 杨业建 姜泽毅四 张欣欣 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:zyjiang@(usth.edu.cm 摘要钢坯热轧加热炉区生产调度属于组合优化中的NP-complete问题.本文根据加热炉区生产特点建立了分别以生产能 耗最小化和加热质量最优化为主次目标的钢坯加热炉区调度数学模型，将其归结为布尔可满足性问题，构造了采用二进制编 码方式的遗传禁忌搜索算法进行求解.基于实际生产数据的模拟优化结果表明，该模型和求解方法充分满足了现场加热炉区 生产调度的需求，在满足生产工艺约束的前提下，缩短了生产时间，提高了钢坯入炉温度和加热质量，与传统人工调度方法的 结果相比具有更好的节能、高产效果 关键词加热炉：生产调度：数学模型：遗传算法：禁忌搜索 分类号T℉089：F406.2 Model and algorithm of furnace area production scheduling in slab hot rolling YANG Yejian,JIANG Ze-yi☒，ZHANG Xin--in School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:zyjiang@ustb.edu.cn ABSTRACT A reheating furnace area scheduling problem in steel production has the NP-hard feature of a combinatorial optimization problem.A mathematical model of the scheduling problem was established according to the production features of the furnace area.Of the scheduling model,the first aim is to minimize the energy consumption cost and the second to optimize the heating quality,so the scheduling problem can be summed up as a Boolean satisfiability problem.A binary encoding method and a hybrid genetic-tabu search algorithm were proposed to solve the mathematical model.Simulation results based on practical data show that the mathematical model and the solution method fully satisfy the demand of furnace area production scheduling.Under the condition of meeting process constraints,the production time is reduced,the charging temperature is increased and the heating quality is improved.The mathemati- cal model and the solution method have a better performance of high production and energy efficiency than the traditional manual sched- uling method. KEY WORDS heating furnaces:scheduling:mathematical models:genetic algorithms:tabu search 钢坯加热炉是钢坯热轧前的加热设备，是现提下，决定钢坯在加热炉区中的加工路径.Clifford 代治金企业铸一轧工序的缓冲环节和耗能大户.在 等因提出了一种加热炉调度策略，但没有考虑后续 满足生产工艺要求的前提下，优化加热炉区的生 热轧工序的约束要求；Paralic等)用启发式模型和 产调度，减少加热工序能耗，对降低生产成本尤为 约束规划两个途径对推钢式加热炉调度进行了分析 重要W 和比较，该方法推广应用到其他炉型有一定难度：宁 近年来，有关加热炉的研究大多侧重于加热炉 树实等阅将加热炉调度问题看作背包容量为无限 数学模型和优化控制P,对钢坯在加热炉区的生 的多约束背包问题进行优化求解，但其加热工艺过 产调度的关注相对较少.加热炉区生产调度是在轧于简化，加热时间只有几分钟，且未考虑加热炉的能 制计划（即钢坯离开加热炉区的次序）和连铸出坯 力约束，不具普遍性.现有加热炉区调度模型均是 计划（即钢坯到达加热炉区的时间）己经确定的前 以最小化钢坯在炉时间为优化目标，没有充分考虑 收稿日期：201105-06 基金项目：国家重点基础研究发展计划资助项目(2012CB720405):中央高校基本科研业务费专项(FRF-AS-10-005B)

第 34 卷 第 7 期 2012 年 7 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 7 Jul． 2012 钢坯热轧加热炉区生产调度模型与算法 杨业建 姜泽毅 张欣欣 北京科技大学机械工程学院，北京 100083 通信作者，E-mail: zyjiang@ ustb． edu． cn 摘 要 钢坯热轧加热炉区生产调度属于组合优化中的 NP-complete 问题． 本文根据加热炉区生产特点建立了分别以生产能 耗最小化和加热质量最优化为主次目标的钢坯加热炉区调度数学模型，将其归结为布尔可满足性问题，构造了采用二进制编 码方式的遗传禁忌搜索算法进行求解． 基于实际生产数据的模拟优化结果表明，该模型和求解方法充分满足了现场加热炉区 生产调度的需求，在满足生产工艺约束的前提下，缩短了生产时间，提高了钢坯入炉温度和加热质量，与传统人工调度方法的 结果相比具有更好的节能、高产效果． 关键词 加热炉; 生产调度; 数学模型; 遗传算法; 禁忌搜索 分类号 TF089; F406. 2 Model and algorithm of furnace area production scheduling in slab hot rolling YANG Ye-jian，JIANG Ze-yi ，ZHANG Xin-xin School of Mechanical Engineering，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: zyjiang@ ustb． edu． cn ABSTRACT A reheating furnace area scheduling problem in steel production has the NP-hard feature of a combinatorial optimization problem． A mathematical model of the scheduling problem was established according to the production features of the furnace area． Of the scheduling model，the first aim is to minimize the energy consumption cost and the second to optimize the heating quality，so the scheduling problem can be summed up as a Boolean satisfiability problem． A binary encoding method and a hybrid genetic-tabu search algorithm were proposed to solve the mathematical model． Simulation results based on practical data show that the mathematical model and the solution method fully satisfy the demand of furnace area production scheduling． Under the condition of meeting process constraints，the production time is reduced，the charging temperature is increased and the heating quality is improved． The mathemati￾cal model and the solution method have a better performance of high production and energy efficiency than the traditional manual sched￾uling method． KEY WORDS heating furnaces; scheduling; mathematical models; genetic algorithms; tabu search 收稿日期: 2011--05--06 基金项目: 国家重点基础研究发展计划资助项目( 2012CB720405) ; 中央高校基本科研业务费专项( FRF--AS--10--005B) 钢坯加热炉是钢坯热轧前的加热设备，是现 代冶金企业铸--轧工序的缓冲环节和耗能大户． 在 满足生产工艺要求的前提下，优化加热炉区的生 产调度，减少加热工序能耗，对降低生产成本尤为 重要［1］． 近年来，有关加热炉的研究大多侧重于加热炉 数学模型和优化控制［2--5］，对钢坯在加热炉区的生 产调度的关注相对较少． 加热炉区生产调度是在轧 制计划( 即钢坯离开加热炉区的次序) 和连铸出坯 计划( 即钢坯到达加热炉区的时间) 已经确定的前 提下，决定钢坯在加热炉区中的加工路径． Clifford 等［6］提出了一种加热炉调度策略，但没有考虑后续 热轧工序的约束要求; Paralic 等［7］用启发式模型和 约束规划两个途径对推钢式加热炉调度进行了分析 和比较，该方法推广应用到其他炉型有一定难度; 宁 树实等［8］将加热炉调度问题看作背包容量为无限 的多约束背包问题进行优化求解，但其加热工艺过 于简化，加热时间只有几分钟，且未考虑加热炉的能 力约束，不具普遍性． 现有加热炉区调度模型均是 以最小化钢坯在炉时间为优化目标，没有充分考虑 DOI:10.13374/j.issn1001-053x.2012.07.014

·842 北京科技大学学报 第34卷 加热炉的工艺特点和加热炉自身的缓冲作用. 因此，加热炉区的生产调度可以归结为如何确定每 在实际生产中，提高钢坯入炉温度可减少加热 块钢坯的加热炉号、入炉时间和出炉时间，该问题属 钢坯的耗能和时间需求，对降低生产能耗大有裨益： 于组合优化难题) 同一加热炉内钢坯规格和入炉温度相近，可稳定加 加热炉区的生产调度方案需要满足的要求主要 热炉工况，提高钢坯的加热质量.本文采用钢坯 有：(1)入炉时间受钢坯到达时间的制约：(2)钢坯 温降时间作为反映生产能耗的优化指标、同炉钢坯 的加热时间根据入炉温度、钢种和规格不同而不同， 离散度作为反映生产质量的优化指标，以生产能耗 与加热工艺要求密切相关；(3)已入炉钢坯在轧制 最小化和加热质量最优化为目标，结合实际生产工 前不允许在加热炉外停留，必须在加热炉中保温等 艺要求，建立钢坯加热炉区调度模型.将问题归结 待：(4)钢坯出加热炉区顺序必须严格符合轧制计 为可满足性问题(satisfiability problem,SAT),并采 划规定的次序；（⑤）加热炉的出坯规则是先进先出： 用遗传禁忌搜索算法进行优化研究. (6)加热炉的装钢、步进、出钢操作与钢坯位置分 布、在炉时间相关，加热炉装钢位无钢坯才能入炉， 1 问题描述 出钢位有钢坯才能出炉 钢坯热轧加热炉区生产调度计划衔接着连铸出 目前在生产实际中常用的加热炉调度方法是按 坯计划和轧制计划.连铸出坯计划由治金生产上游 照钢坯的轧制顺序依炉号顺序依次向各加热炉分配 工序决定（主要取决于产品的钢种差异），轧制计划 钢坯，然后依炉号顺序出炉.这种调度方法基本能 由下游工序决定（主要取决于产品的规格），由此造 够保证按照轧制顺序向热轧机组持续供应钢坯的要 成钢坯到达和离开加热炉区的次序有较大差异，因 求，但往往由于钢坯到达顺序和轧制顺序的差异以 而需要加热炉作为连接上下游工序的缓冲活套@， 及热轧生产换辊等间断操作的原因，使钢坯入库率 加热炉区主要包括板坯库、多座加热炉以及辊道等 和入库时间增加，从而增加加热工序能耗和影响加 输送装置.钢坯到达加热炉区后需首先决定是直接 热质量.通过加热炉区的优化调度，在满足热轧要 入炉还是进钢坯库暂存一定时间后再出库入炉，在 求的前提下，尽量增加钢坯入炉温度，对提高钢坯加 选择入哪座加热炉时还需考虑轧制计划对出炉顺序 热质量和降低加热炉能耗都具有重要意义 和钢坯加热工艺的要求 综合考虑钢坯的来坯顺序、轧制次序、钢坯入炉 加热炉区的缓冲作用主要由板坯库暂时存放、 温度和钢坯的钢种规格等因素，对钢坯入库、出库和 多座加热炉的分配和加热炉操作控制来实现.板坯 加热炉选择等进行调度分配，在满足轧制要求的基 库和多座加热炉的分配主要是通过生产调度实现缓 础上，实现节能降耗和加热质量的优化.针对这一 冲作用，加热炉操作控制通过调节设备工况实现缓 要求提出两个优化指标：(1)通过钢坯等待入炉时 冲作用，其主要调节参数为步进节奏和各段炉温设 间来反映钢坯入炉温度一钢坯温降时间：(2)同 定，步进节奏与炉内钢坯加热时间需求密切相关，各 炉加工钢坯的规格和入炉温度差异—同炉钢坯离 段炉温设定由各段内钢坯的实时和目标温度决定. 散度.其中，钢坯温降时间体现钢坯热送热装效果， 实际生产中，加热炉工况受炉内所有钢坯的影响，其 提高入炉温度可以有效地降低加热炉燃耗、提高加 能耗与钢坯加热时间、入炉温度和加热质量要求等 热炉产量和减少钢坯的氧化烧损：同炉钢坯离散度 因素相关.根据加热炉的热工原理，减少钢坯入炉 反应加热炉工况平稳程度，入炉钢坯差异越小，则加 前的温降时间及稳定同一加热炉内钢坯的规格和入 热炉工况越稳定，同时加热质量越好.本文通过不 炉温度可以有效降低生产能耗. 同指标的重要性分析，采用串联方式，按钢坯温降时 加热炉区生产调度是在钢坯的轧制计划和连铸 间→同炉钢坯离散度的重要程度排序，在计算中分 出坯计划已定的情况下，确定钢坯在加热炉区中的 阶段对结果进行串行寻优， 加工路径和时间，实现以满足热轧顺序要求为首要 2数学模型 前提下的能耗最小和加热质量最优的目标.钢坯的 加工路径和时间主要包括钢坯是否入钢坯库和库内 钢坯热轧加热炉区调度问题可以概述为：有m 存放时间、钢坯的加热炉号、钢坯的入炉时间、钢坯 座加热炉，块钢坯，在钢坯的到达时间和热轧顺序 的出炉时间.钢坯是否入钢坯库和库内存放时间根 一定的基础上，求解钢坯的加热炉号、入炉时间和出 据钢坯到达时间（与连铸出坯计划和运输情况相 炉时间.本文选取生产能耗最小和加热质量最优为 关)和入炉加热时间（与轧制计划相关）综合确定 目标，经转化可以描述为：在满足各项生产要求的前

北 京 科 技 大 学 学 报 第 34 卷 加热炉的工艺特点和加热炉自身的缓冲作用． 在实际生产中，提高钢坯入炉温度可减少加热 钢坯的耗能和时间需求，对降低生产能耗大有裨益; 同一加热炉内钢坯规格和入炉温度相近，可稳定加 热炉工况，提高钢坯的加热质量［9］． 本文采用钢坯 温降时间作为反映生产能耗的优化指标、同炉钢坯 离散度作为反映生产质量的优化指标，以生产能耗 最小化和加热质量最优化为目标，结合实际生产工 艺要求，建立钢坯加热炉区调度模型． 将问题归结 为可满足性问题( satisfiability problem，SAT) ，并采 用遗传禁忌搜索算法进行优化研究． 1 问题描述 钢坯热轧加热炉区生产调度计划衔接着连铸出 坯计划和轧制计划． 连铸出坯计划由冶金生产上游 工序决定( 主要取决于产品的钢种差异) ，轧制计划 由下游工序决定( 主要取决于产品的规格) ，由此造 成钢坯到达和离开加热炉区的次序有较大差异，因 而需要加热炉作为连接上下游工序的缓冲活套［10］． 加热炉区主要包括板坯库、多座加热炉以及辊道等 输送装置． 钢坯到达加热炉区后需首先决定是直接 入炉还是进钢坯库暂存一定时间后再出库入炉，在 选择入哪座加热炉时还需考虑轧制计划对出炉顺序 和钢坯加热工艺的要求． 加热炉区的缓冲作用主要由板坯库暂时存放、 多座加热炉的分配和加热炉操作控制来实现． 板坯 库和多座加热炉的分配主要是通过生产调度实现缓 冲作用，加热炉操作控制通过调节设备工况实现缓 冲作用，其主要调节参数为步进节奏和各段炉温设 定，步进节奏与炉内钢坯加热时间需求密切相关，各 段炉温设定由各段内钢坯的实时和目标温度决定． 实际生产中，加热炉工况受炉内所有钢坯的影响，其 能耗与钢坯加热时间、入炉温度和加热质量要求等 因素相关． 根据加热炉的热工原理，减少钢坯入炉 前的温降时间及稳定同一加热炉内钢坯的规格和入 炉温度可以有效降低生产能耗． 加热炉区生产调度是在钢坯的轧制计划和连铸 出坯计划已定的情况下，确定钢坯在加热炉区中的 加工路径和时间，实现以满足热轧顺序要求为首要 前提下的能耗最小和加热质量最优的目标． 钢坯的 加工路径和时间主要包括钢坯是否入钢坯库和库内 存放时间、钢坯的加热炉号、钢坯的入炉时间、钢坯 的出炉时间． 钢坯是否入钢坯库和库内存放时间根 据钢坯到达时间( 与连铸出坯计划和运输情况相 关) 和入炉加热时间( 与轧制计划相关) 综合确定． 因此，加热炉区的生产调度可以归结为如何确定每 块钢坯的加热炉号、入炉时间和出炉时间，该问题属 于组合优化难题［11］． 加热炉区的生产调度方案需要满足的要求主要 有: ( 1) 入炉时间受钢坯到达时间的制约; ( 2) 钢坯 的加热时间根据入炉温度、钢种和规格不同而不同， 与加热工艺要求密切相关; ( 3) 已入炉钢坯在轧制 前不允许在加热炉外停留，必须在加热炉中保温等 待; ( 4) 钢坯出加热炉区顺序必须严格符合轧制计 划规定的次序; ( 5) 加热炉的出坯规则是先进先出; ( 6) 加热炉的装钢、步进、出钢操作与钢坯位置分 布、在炉时间相关，加热炉装钢位无钢坯才能入炉， 出钢位有钢坯才能出炉． 目前在生产实际中常用的加热炉调度方法是按 照钢坯的轧制顺序依炉号顺序依次向各加热炉分配 钢坯，然后依炉号顺序出炉． 这种调度方法基本能 够保证按照轧制顺序向热轧机组持续供应钢坯的要 求，但往往由于钢坯到达顺序和轧制顺序的差异以 及热轧生产换辊等间断操作的原因，使钢坯入库率 和入库时间增加，从而增加加热工序能耗和影响加 热质量． 通过加热炉区的优化调度，在满足热轧要 求的前提下，尽量增加钢坯入炉温度，对提高钢坯加 热质量和降低加热炉能耗都具有重要意义． 综合考虑钢坯的来坯顺序、轧制次序、钢坯入炉 温度和钢坯的钢种规格等因素，对钢坯入库、出库和 加热炉选择等进行调度分配，在满足轧制要求的基 础上，实现节能降耗和加热质量的优化． 针对这一 要求提出两个优化指标: ( 1) 通过钢坯等待入炉时 间来反映钢坯入炉温度———钢坯温降时间; ( 2) 同 炉加工钢坯的规格和入炉温度差异———同炉钢坯离 散度． 其中，钢坯温降时间体现钢坯热送热装效果， 提高入炉温度可以有效地降低加热炉燃耗、提高加 热炉产量和减少钢坯的氧化烧损; 同炉钢坯离散度 反应加热炉工况平稳程度，入炉钢坯差异越小，则加 热炉工况越稳定，同时加热质量越好． 本文通过不 同指标的重要性分析，采用串联方式，按钢坯温降时 间→同炉钢坯离散度的重要程度排序，在计算中分 阶段对结果进行串行寻优． 2 数学模型 钢坯热轧加热炉区调度问题可以概述为: 有 m 座加热炉，n 块钢坯，在钢坯的到达时间和热轧顺序 一定的基础上，求解钢坯的加热炉号、入炉时间和出 炉时间． 本文选取生产能耗最小和加热质量最优为 目标，经转化可以描述为: 在满足各项生产要求的前 ·842·

第7期 杨业建等：钢还热轧加热炉区生产调度模型与算法 ·843· 提下，首先最小化钢坯温降时间，其次最小化同炉钢 3模型求解 坯离散度 根据以上描述，可以建立加热炉区调度问题的 根据给定时间域内的钢坯信息、轧制计划和铸 数学模型，首先定义如下参数：F={1,2,…m}为加 坯出坯计划，采用上述目标函数和约束条件，求解每 热炉序号集合，共有m座加热炉；Q=（9,92,…, 块钢坯分配的加热炉号、每块钢坯的入炉时间和出 q。)为待加工钢坯的轧制顺序，其中9：为钢坯号，共 炉时间.钢坯加热炉号的选择相对独立且对钢坯的 有n块钢坯；T,为钢坯q:的到达时刻；sg为钢坯q: 入炉时间和出炉时间有一定的决定作用，因此本文 的入炉时刻：e,为钢坯q:的出炉时刻：为所有钢 采用将求解加热炉区生产调度计划转换成求解钢坯 坯总的等待加热时间，min;D为同炉钢坯离散度的 的加热炉号的方式实现加热炉区生产调度，其优化 平均值；a、b和c为权值，且a+b+c=1;σ(T)、 求解过程为：首先确定每块钢坯分配的加热炉号，然 σ(V)和σ(G)分别为加热炉f所加工钢坯的温度 后按照约束条件生成钢坯的入出炉时间以及是否进 分布标准差、体积分布标准差和厚度分布标准差： 钢坯库，通过调整加热炉各段炉温和步进节奏实现 1板坯9：分配给加热炉f加工， 上述目标，最终生成完整的加热炉区调度方案.求 PF{0其他： 解流程如图1所示 h为最小轧制间隔时间，min;ta为钢坯最小加热时 (开始 间，min;tmx为钢坯最大加热时间，min;Ns为加热炉 产生钢还的 可同时加热最大钢坯数；M,为t时刻加热炉f内的 加热炉分配方案 钢坯数 按轧制顺序读取 加热炉调度问题的数学模型可以描述为： 轧制钢坯信总 m店=名 (s-T）, (1) 根据约束条件成 钢坯的入炉出炉时间 0时=ax月b(刀]+6x 判断板坯足否热送热装， 更新加热炉状态 盒（四]+ex月 o(G]. (2) 存人加热炉区调度计划 Subject toe.<eg,若i<j,Hg:g∈Q, (3) 否 是否轧制的 最后一块？ s<sg,若i<j,H9,g∈Q且P时=P时=1，f∈F, 是 生成加热炉区调度计划 (4) 名w 是否达到 (5) 停止条件？ 是 eu1-e≥h,Hg:g5∈Q, (6) 输出结果 tmin≤egu-Sgu≤tmm' (7) 图1调度模型的求解流程 Fig.1 Solving flowchart of the scheduling model My≤Nnx (8) 其中，式(1)表示所有钢坯温降总时间最短；式(2) 在求解过程中，以二进制表示每块钢坯分配的 表示钢坯入炉温度平均离散值、入炉钢坯体积平均 加热炉号，钢坯所分配的加热炉号按照轧制顺序排 离散值和入炉钢坯厚度平均离散值的加权平均值最 列可以组成一个二进制字符串.钢坯炉号选择的这 小；式(3)保证钢坯从加热炉区的出炉顺序与轧制 种二进制描述与逻辑学上的可满足性问题的描述形 顺序相符：式(4)保证在同一加热炉加工的钢坯先 式比较类似，该问题是历史上第一个被证明的NP- 热轧的先入炉；式(5)保证每块钢坯都被分配且只 complete问题.这类问题无法用精确算法求得最 被分配到一个加热炉加工；式(6)保证加热工序出 优解，只能通过启发式或者超启发式算法得到问题 钢的间隔符合热轧机组的要求：式(7)保证钢坯加 的满意解 热时间符合加热工艺要求：式(8)保证加热炉内钢 遗传算法是较早出现的超启发式算法，己被许 坯数不超过最大值. 多应用实例证明是求解组合优化难题的有效算法之

第 7 期 杨业建等: 钢坯热轧加热炉区生产调度模型与算法 提下，首先最小化钢坯温降时间，其次最小化同炉钢 坯离散度． 根据以上描述，可以建立加热炉区调度问题的 数学模型，首先定义如下参数: F = { 1，2，…m} 为加 热炉序号集合，共有 m 座加热炉; Q = ( q1，q2，…， qn ) 为待加工钢坯的轧制顺序，其中 qi 为钢坯号，共 有 n 块钢坯; rqi 为钢坯 qi 的到达时刻; sqi 为钢坯 qi 的入炉时刻; eqi 为钢坯 qi 的出炉时刻; t Σ w 为所有钢 坯总的等待加热时间，min; DΣ d 为同炉钢坯离散度的 平均值; a、b 和 c 为权值，且 a + b + c = 1; σ( Tf ) 、 σ( Vf ) 和 σ( Gf ) 分别为加热炉 f 所加工钢坯的温度 分布标准差、体积分布标准差和厚度分布标准差; pqi f = 1 板坯 qi 分配给加热炉 f 加工， {0 其他; h 为最小轧制间隔时间，min; tmin为钢坯最小加热时 间，min; tmax为钢坯最大加热时间，min; Nmax为加热炉 可同时加热最大钢坯数; Mt，f为 t 时刻加热炉 f 内的 钢坯数． 加热炉调度问题的数学模型可以描述为: Min t Σ w = ∑i∈S ( sqi － rqi ) ， ( 1) Min DΣ d = a × ∑ m f = 1 ［σ( Tf ) ］+ b × ∑ m f = 1 ［σ( Vf ) ］+ c × ∑ m f = 1 ［σ( Gf ) ］． ( 2) Subject toeqi ＜ eqj ，若 i ＜ j，qi，qj∈Q， ( 3) sqi ＜ sqj ，若 i ＜ j，qi，qj∈Q 且 pqi f = pqj f = 1，f∈F， ( 4) ∑ f∈F qi∈Q pqi f = n， ( 5) eqi + 1 － eqi ≥h，qi，qj∈Q， ( 6) tmin≤eqi － sqi ≤tmax， ( 7) Mt，f≤Nmax ． ( 8) 其中，式( 1) 表示所有钢坯温降总时间最短; 式( 2) 表示钢坯入炉温度平均离散值、入炉钢坯体积平均 离散值和入炉钢坯厚度平均离散值的加权平均值最 小; 式( 3) 保证钢坯从加热炉区的出炉顺序与轧制 顺序相符; 式( 4) 保证在同一加热炉加工的钢坯先 热轧的先入炉; 式( 5) 保证每块钢坯都被分配且只 被分配到一个加热炉加工; 式( 6) 保证加热工序出 钢的间隔符合热轧机组的要求; 式( 7) 保证钢坯加 热时间符合加热工艺要求; 式( 8) 保证加热炉内钢 坯数不超过最大值． 3 模型求解 根据给定时间域内的钢坯信息、轧制计划和铸 坯出坯计划，采用上述目标函数和约束条件，求解每 块钢坯分配的加热炉号、每块钢坯的入炉时间和出 炉时间． 钢坯加热炉号的选择相对独立且对钢坯的 入炉时间和出炉时间有一定的决定作用，因此本文 采用将求解加热炉区生产调度计划转换成求解钢坯 的加热炉号的方式实现加热炉区生产调度，其优化 求解过程为: 首先确定每块钢坯分配的加热炉号，然 后按照约束条件生成钢坯的入出炉时间以及是否进 钢坯库，通过调整加热炉各段炉温和步进节奏实现 上述目标，最终生成完整的加热炉区调度方案． 求 解流程如图 1 所示． 图 1 调度模型的求解流程 Fig． 1 Solving flowchart of the scheduling model 在求解过程中，以二进制表示每块钢坯分配的 加热炉号，钢坯所分配的加热炉号按照轧制顺序排 列可以组成一个二进制字符串． 钢坯炉号选择的这 种二进制描述与逻辑学上的可满足性问题的描述形 式比较类似，该问题是历史上第一个被证明的 NP￾complete 问题［12］． 这类问题无法用精确算法求得最 优解，只能通过启发式或者超启发式算法得到问题 的满意解． 遗传算法是较早出现的超启发式算法，已被许 多应用实例证明是求解组合优化难题的有效算法之 ·843·

·844· 北京科技大学学报 第34卷 一.遗传算法(genetic algorithms,.GA)是模仿自然 坯向各个加热炉的分配，其入炉和出炉时间由钢坯 界生物进化中的遗传、变异和自然选择过程，对解空 的到达时间、加热炉和轧机的生产限制来决定 间的点进行遗传操作的一类模拟进化算法围.大 当加热炉个数非2"(n≥1)时，仍可采用上述编 多数工程优化问题中，由于常常带有复杂的约束条 码方式，取合适的n值使2”最接近且大于加热炉个 件，简单的遗传算法往往不能很好地解决这类工程 数，其中无法与加热炉对应的二进制可以采用随机 优化问题.在遗传算法中增加所求解问题的先验知 分配的方式指定加热炉或依次指定给每座加热炉的 识对于求解效果的影响很大.本文选用遗传算 方式实现与加热炉的对应. 法和禁忌搜索相结合的遗传禁忌搜索算法进行求 (2)交叉算子.本文的交叉算子同时作用于两 解，其详细步骤如下 个父代，综合这两个父代的特点产生一个子代，交叉 Step1:随机生成N个初始解，形成种群(N为 算子采用了一种“局部方案保留”的策略，局部方案 种群规模)： 对应的是某些钢坯的加热炉选择方式，通过保留某 Step2:对种群中每个解执行变异运算： 个父代的局部方案来保留父代中比较优良的基因， Step3:将当前种群的个体进行两两配对，按照 以一定的概率P。执行交叉运算. 交叉概率P。随机截取配对中两个个体的部分组成 (3)变异算子.引入变异算子是为了达到全局 新的个体，按照变异概率P执行变异运算后形成新 优化的效果.本文采用的变异运算分为两次进行. 个体，存储于子代种群中； 第一次，执行完交叉算子后，以一定的概率Pm执行 Stp4:将当前种群和子代种群转化为加热炉区 变异算子，方法是随机选取一定数目的钢坯，对其反 生产计划，并计算评价值： 映加热炉分配的二进制字符串执行取反操作.第二 Step5:对当前种群和子代种群通过选择运算选 次，选取下一代种群后，对种群中所有解的编码执行 出N个子代形成新一代种群： 取反、与同等长度的二进制字符串“101010…”和 Step6:对新一代种群中的每个个体进行禁忌搜 010101…”执行异或操作，从而将一个解扩展为四 索，若得到的解优于原解则取代相应的原子代个体， 个解.第一次变异运算是为了引入突变，第二次变 将新一代种群作为当前种群； 异运算是为了引入多种选择，假设有四块钢坯，其编 Step7:判断是否满足停止条件，如满足算法终 码为00011011，则执行第二部分变异后结果为 止，输出当前种群中的最优解；如不满足，则跳转 00011011 Step 2. 11100100 实现优化问题的遗传禁忌搜索算法求解，除了 10110001 要构建遗传算法的组成部分，还要实现禁忌搜索 01001110 本文采用的编码方式、交叉算子、变异算子、适应值 由以上四种编码可以看出，执行变异算子后每 函数、选择机制、禁忌搜索和停止条件如下 一块钢坯都有了进入四座加热炉的机会，有利于寻 (1)解的编码方式.解的编码功能是将问题的 找全局最优解 解用一种便于遗传操作的方式表现出来.本文在求 (4)适应值函数.采用式(1)和式(2)的优化 解加热炉调度问题时使用二进制表示钢坯选择的加 函数目标值作为适应度函数值.根据式(1)和式 热炉，将钢坯的加热炉号按照钢坯的轧制顺序排列 (2)的重要性，在计算中分阶段进行寻优 成一个二进制字符串进行处理.假设有八块待加热 (⑤)选择机制.当前种群经过遗传变异后生成 钢坯(1,2,3,4,5,6,7,8)和四座加热炉，轧制顺序 子代种群，将当前种群并入到子代种群，计算适应 为(1,2,3,4,5,6,7,8,00”表示分配到加热炉1"， 值，然后将适应值最好的前几个个体直接复制到新 “01”表示分配到加热炉2,10”表示分配到加热炉 一代种群中，剩余的个体根据种群规模按照随机通 3”,11”表示分配到加热炉4”，一种可能的分配就 用采样方法的确定是否复制到新一代种群 可以编码为如下二进制字符串： (6)禁忌搜索.将所有钢坯两两配对，形成钢 0001101100011011. 坯对群，针对每次遗传运算所得到的新一代种群中 根据编码可以得知钢坯号为1和5的钢坯分配 的每一个解，根据禁忌表依次交换分配到不同加热 给加热炉1”，钢坯号为2和6的钢坯分配给加热炉 炉的钢坯对，得到新的解，计算其适应值，找到适应 2”,钢坯号为3和7的钢坯分配给加热炉3”，钢坯号 值优于原解的新解取代原来的解，更新禁忌表为下 为4和8的钢坯分配给加热炉4”.编码中仅体现钢 一次遗传运算中的禁忌搜索做准备，若无则保持

北 京 科 技 大 学 学 报 第 34 卷 一． 遗传算法( genetic algorithms，GA) 是模仿自然 界生物进化中的遗传、变异和自然选择过程，对解空 间的点进行遗传操作的一类模拟进化算法［13］． 大 多数工程优化问题中，由于常常带有复杂的约束条 件，简单的遗传算法往往不能很好地解决这类工程 优化问题． 在遗传算法中增加所求解问题的先验知 识对于求解效果的影响很大［14］． 本文选用遗传算 法和禁忌搜索相结合的遗传禁忌搜索算法进行求 解，其详细步骤如下． Step 1: 随机生成 N 个初始解，形成种群( N 为 种群规模) ; Step 2: 对种群中每个解执行变异运算; Step 3: 将当前种群的个体进行两两配对，按照 交叉概率 pc随机截取配对中两个个体的部分组成 新的个体，按照变异概率 pm执行变异运算后形成新 个体，存储于子代种群中; Step 4: 将当前种群和子代种群转化为加热炉区 生产计划，并计算评价值; Step 5: 对当前种群和子代种群通过选择运算选 出 N 个子代形成新一代种群; Step 6: 对新一代种群中的每个个体进行禁忌搜 索，若得到的解优于原解则取代相应的原子代个体， 将新一代种群作为当前种群; Step 7: 判断是否满足停止条件，如满足算法终 止，输出当前种群中的最优解; 如不满足，则跳转 Step 2． 实现优化问题的遗传禁忌搜索算法求解，除了 要构建遗传算法的组成部分，还要实现禁忌搜索． 本文采用的编码方式、交叉算子、变异算子、适应值 函数、选择机制、禁忌搜索和停止条件如下． ( 1) 解的编码方式． 解的编码功能是将问题的 解用一种便于遗传操作的方式表现出来． 本文在求 解加热炉调度问题时使用二进制表示钢坯选择的加 热炉，将钢坯的加热炉号按照钢坯的轧制顺序排列 成一个二进制字符串进行处理． 假设有八块待加热 钢坯( 1，2，3，4，5，6，7，8) 和四座加热炉，轧制顺序 为( 1，2，3，4，5，6，7，8) ，“00”表示分配到加热炉 1# ， “01”表示分配到加热炉 2# ，“10”表示分配到加热炉 3# ，“11”表示分配到加热炉 4# ，一种可能的分配就 可以编码为如下二进制字符串: 0001101100011011． 根据编码可以得知钢坯号为 1 和 5 的钢坯分配 给加热炉 1# ，钢坯号为 2 和 6 的钢坯分配给加热炉 2# ，钢坯号为 3 和 7 的钢坯分配给加热炉 3# ，钢坯号 为 4 和 8 的钢坯分配给加热炉 4# ． 编码中仅体现钢 坯向各个加热炉的分配，其入炉和出炉时间由钢坯 的到达时间、加热炉和轧机的生产限制来决定． 当加热炉个数非 2n ( n≥1) 时，仍可采用上述编 码方式，取合适的 n 值使 2n 最接近且大于加热炉个 数，其中无法与加热炉对应的二进制可以采用随机 分配的方式指定加热炉或依次指定给每座加热炉的 方式实现与加热炉的对应． ( 2) 交叉算子． 本文的交叉算子同时作用于两 个父代，综合这两个父代的特点产生一个子代，交叉 算子采用了一种“局部方案保留”的策略，局部方案 对应的是某些钢坯的加热炉选择方式，通过保留某 个父代的局部方案来保留父代中比较优良的基因， 以一定的概率 pc 执行交叉运算． ( 3) 变异算子． 引入变异算子是为了达到全局 优化的效果． 本文采用的变异运算分为两次进行． 第一次，执行完交叉算子后，以一定的概率 pm 执行 变异算子，方法是随机选取一定数目的钢坯，对其反 映加热炉分配的二进制字符串执行取反操作． 第二 次，选取下一代种群后，对种群中所有解的编码执行 取反、与同等长度的二进制字符串“101010 …”和 “010101…”执行异或操作，从而将一个解扩展为四 个解． 第一次变异运算是为了引入突变，第二次变 异运算是为了引入多种选择，假设有四块钢坯，其编 码为 00011011，则执行第二部分变异后结果为 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 由以上四种编码可以看出，执行变异算子后每 一块钢坯都有了进入四座加热炉的机会，有利于寻 找全局最优解． ( 4) 适应值函数． 采用式( 1) 和式( 2) 的优化 函数目标值作为适应度函数值． 根据式( 1) 和式 ( 2) 的重要性，在计算中分阶段进行寻优． ( 5) 选择机制． 当前种群经过遗传变异后生成 子代种群，将当前种群并入到子代种群，计算适应 值，然后将适应值最好的前几个个体直接复制到新 一代种群中，剩余的个体根据种群规模按照随机通 用采样方法［15］确定是否复制到新一代种群． ( 6) 禁忌搜索． 将所有钢坯两两配对，形成钢 坯对群，针对每次遗传运算所得到的新一代种群中 的每一个解，根据禁忌表依次交换分配到不同加热 炉的钢坯对，得到新的解，计算其适应值，找到适应 值优于原解的新解取代原来的解，更新禁忌表为下 一次遗传运算中的禁忌搜索做准备，若无则保持 ·844·

第7期 杨业建等：钢还热轧加热炉区生产调度模型与算法 ·845· 不变 的收敛情况可以看出，本文采用的混合算法对于模 本文在进行禁忌搜索时使用了一个向量表示钢 型的求解较为理想 坯在各加热炉之间的分配，在这个向量中包括两类 5应用实例 符号—钢还号和分隔符，钢坯号与待加热钢坯一 一对应，分隔符用于分隔分配到不同加热炉的钢坯 本文根据某厂加热炉区的实际生产数据进行了 假设有八块待加热钢坯和四个加热炉，一种可能的 多批次的加热炉区生产调度计划编制工作，并与现 分配方案可以编码为如下的向量： 场采用的人工调度方法进行了对比分析.计算参 12*34*56*78] 数：种群规模为100，迭代次数为1000次，交叉概率 根据编码可以得知，钢坯号为1和2的钢坯分 为0.8，变异概率为0.5.四组有代表性的生产数据 配到1"加热炉，钢坯号为3和4的钢坯分配到2"加 如下. 热炉，钢坯号为5和6的钢坯分配到3"加热炉，钢坯 批次1：250块板坯，共有13种规格（规格变化 号为7和8的钢坯分配到4加热炉，则可以形成24 较大). 个分配到不同加热炉的钢坯对，依次交换每对钢坯 批次2：156块板坯，共有8种规格（规格变化 对形成24个新的解向量，假设选取的钢坯对为(1， 较大) 3),则新的解向量为B2*14*56*78].重 批次3：250块板坯，共有7种规格（规格变化 复上述过程，会得到24个新解，计算其适应值与原 较小) 有的解进行比较，选取最优的解取代原有的解. 批次4：156块板坯，共有4种规格（规格变化 (7)停止条件.停止条件设置为算法运行到一 较小) 个预先设定的迭代次数时停止，取算法停止时的当 采用本文所提出的加热炉区生产调度模型与算 前种群中的最优解作为结果输出 法，针对某厂板坯热轧生产线的实际生产数据进行 生产调度计算.其中板坯的轧制顺序己经确定，且 4求解过程分析 所有板坯均可以热送热装.热轧机的生产能力为每 选取某时间段内的实际生产合同计划（共156 隔2min轧制一块板坯，共有四座规格一致的加热 块板坯)进行优化计算，求解过程中两个优化目标 炉共用入炉和出炉辊道.加热能力为：冷坯需要加 值的变化趋势如图2所示.计算采用普通计算机. 热120min,热坯加热时间视入炉温度而定.生产数 算法的参数设置为：种群规模为60，迭代次数为700 据采用四种典型生产情况下的数据.对于每组数 次，交叉概率为0.8，变异概率为0.5.所需时间为 据，用本文算法各运行30次取平均值.优化结果与 l5min,计算速度满足现场完成加热炉区生产调度 人工调度结果的对比如表1所示. 计划编制计算的需求 由表1可以看出：应用本文设计的模型和解法 23270 一板坏温降时间 70.33 所得到的加热炉生产调度方案，结果均优于现在正 23260 -同炉板坯离散度 10.32 在使用的人工调度方法得到的结果.指标1反应板 23250 坯在板坯库中等待加热的时间，时间越短，则板坯入 23241 炉温度越高，不仅可以有效降低能耗，成材率也会显 0.30马 23230 著提高，本文采用的方法与现有方法相比，每块板坯 23220 -0.29 减少了约20min的等待时间，入炉温度提高约120 2321 0.28 010020030040050060070 ℃，相应的加热工序节能10%以上，同时对缩短加 计算步数 热炉加工计划板坯的工作时间也大有裨益，减少加 图2优化目标变化趋势图 热炉的工作时间对于加热工序节能具有最直接的效 Fig.2 Trend chart of the optimization goal 果，若采用优化结果进行生产，则本文所模拟的每批 由图2可以看出，板坯温降时间随着求解步数 次生产均可直接节约7500m3以上煤气，节能效果显 的增加而逐渐减少，优化效果较好.同炉板坯离散 著：指标2为入炉温度平均离散值、入炉板坯体积平 度随求解步数的增加而逐渐收敛，其变化同时受板 均离散值和入炉板坯厚度平均离散值的加权平均 坯温降时间变化的影响，对其寻优的目的是在节能 值，该值越小则同座加热炉内板坯加热需求差异越 的基础上，进一步提高产品质量，实现生产能耗最小 小，加热炉工作更为平稳，能耗更低，同时板坯的加 基础上产品质量最优化的目标.根据上述两个目标 热质量更好

第 7 期 杨业建等: 钢坯热轧加热炉区生产调度模型与算法 不变． 本文在进行禁忌搜索时使用了一个向量表示钢 坯在各加热炉之间的分配，在这个向量中包括两类 符号———钢坯号和分隔符，钢坯号与待加热钢坯一 一对应，分隔符用于分隔分配到不同加热炉的钢坯． 假设有八块待加热钢坯和四个加热炉，一种可能的 分配方案可以编码为如下的向量: ［1 2 * 3 4 * 5 6 * 7 8］． 根据编码可以得知，钢坯号为 1 和 2 的钢坯分 配到 1# 加热炉，钢坯号为 3 和 4 的钢坯分配到 2# 加 热炉，钢坯号为 5 和 6 的钢坯分配到 3# 加热炉，钢坯 号为 7 和 8 的钢坯分配到 4# 加热炉，则可以形成 24 个分配到不同加热炉的钢坯对，依次交换每对钢坯 对形成 24 个新的解向量，假设选取的钢坯对为( 1， 3) ，则新的解向量为［3 2 * 1 4 * 5 6 * 7 8］． 重 复上述过程，会得到 24 个新解，计算其适应值与原 有的解进行比较，选取最优的解取代原有的解． ( 7) 停止条件． 停止条件设置为算法运行到一 个预先设定的迭代次数时停止，取算法停止时的当 前种群中的最优解作为结果输出． 4 求解过程分析 选取某时间段内的实际生产合同计划( 共 156 块板坯) 进行优化计算，求解过程中两个优化目标 值的变化趋势如图 2 所示． 计算采用普通计算机． 算法的参数设置为: 种群规模为 60，迭代次数为 700 次，交叉概率为 0. 8，变异概率为 0. 5． 所需时间为 15 min，计算速度满足现场完成加热炉区生产调度 计划编制计算的需求． 图 2 优化目标变化趋势图 Fig． 2 Trend chart of the optimization goal 由图 2 可以看出，板坯温降时间随着求解步数 的增加而逐渐减少，优化效果较好． 同炉板坯离散 度随求解步数的增加而逐渐收敛，其变化同时受板 坯温降时间变化的影响，对其寻优的目的是在节能 的基础上，进一步提高产品质量，实现生产能耗最小 基础上产品质量最优化的目标． 根据上述两个目标 的收敛情况可以看出，本文采用的混合算法对于模 型的求解较为理想． 5 应用实例 本文根据某厂加热炉区的实际生产数据进行了 多批次的加热炉区生产调度计划编制工作，并与现 场采用的人工调度方法进行了对比分析． 计算参 数: 种群规模为 100，迭代次数为 1 000 次，交叉概率 为 0. 8，变异概率为 0. 5． 四组有代表性的生产数据 如下． 批次 1∶ 250 块板坯，共有 13 种规格( 规格变化 较大) ． 批次 2∶ 156 块板坯，共有 8 种规格( 规格变化 较大) ． 批次 3∶ 250 块板坯，共有 7 种规格( 规格变化 较小) ． 批次 4∶ 156 块板坯，共有 4 种规格( 规格变化 较小) ． 采用本文所提出的加热炉区生产调度模型与算 法，针对某厂板坯热轧生产线的实际生产数据进行 生产调度计算． 其中板坯的轧制顺序已经确定，且 所有板坯均可以热送热装． 热轧机的生产能力为每 隔 2 min 轧制一块板坯，共有四座规格一致的加热 炉共用入炉和出炉辊道． 加热能力为: 冷坯需要加 热 120 min，热坯加热时间视入炉温度而定． 生产数 据采用四种典型生产情况下的数据． 对于每组数 据，用本文算法各运行 30 次取平均值． 优化结果与 人工调度结果的对比如表 1 所示． 由表 1 可以看出: 应用本文设计的模型和解法 所得到的加热炉生产调度方案，结果均优于现在正 在使用的人工调度方法得到的结果． 指标 1 反应板 坯在板坯库中等待加热的时间，时间越短，则板坯入 炉温度越高，不仅可以有效降低能耗，成材率也会显 著提高，本文采用的方法与现有方法相比，每块板坯 减少了约 20 min 的等待时间，入炉温度提高约 120 ℃，相应的加热工序节能 10% 以上，同时对缩短加 热炉加工计划板坯的工作时间也大有裨益，减少加 热炉的工作时间对于加热工序节能具有最直接的效 果，若采用优化结果进行生产，则本文所模拟的每批 次生产均可直接节约 7500 m3 以上煤气，节能效果显 著; 指标 2 为入炉温度平均离散值、入炉板坯体积平 均离散值和入炉板坯厚度平均离散值的加权平均 值，该值越小则同座加热炉内板坯加热需求差异越 小，加热炉工作更为平稳，能耗更低，同时板坯的加 热质量更好． ·845·