板坯热轧批量计划数学模型及求解算法

D0I:10.13374/.issn1001-053x.2012.04.009 第34卷第4期 北京科技大学学报 Vol.34 No.4 2012年4月 Journal of University of Science and Technology Beijing Apr.2012 板坯热轧批量计划数学模型及求解算法 杨业建四姜泽毅 张欣欣 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:zyjiang(@ustb.edu.cn 摘要根据热轧工艺特点将板坯热轧批量计划编制问题归结为不确定旅行商数的多旅行商问题，建立了以生产成本最小 化和产品质量最优化为主次目标且考虑加热区段能耗的生产调度数学模型，并采用遗传算法和禁忌搜索相结合的混合算法 进行求解.基于实际生产数据的计算结果表明：该模型充分满足了现场热轧批量计划编制的需求，在轧制单元数最优的基础 上，缩短了传搁时间，提高了热送热装率，优化了产品质量.与人机结合方式相比，本文模型的计算结果体现了更好的高产和 节能效果 关键词热轧：计划编制：旅行商问题：遗传算法：禁忌搜索算法 分类号T℉089：F406.2 Mathematical model and solving algorithm for the lot planning of slab hot rolling YANG Yejian☒，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 According to the technical demand of hot-rolling production,the lot planning of slab hot rolling was summed up as a multiple traveling salesperson problem with uncertain traveling salesman number.A production scheduling mathematical model consid- ering the energy consumption of the heating section was proposed,with minimizing the production cost as the primary objective and op- timizing the product quality as the secondary objective.A hybrid algorithm based on the genetic algorithm and the tabu search algorithm was proposed to solve the problem.Simulation results of practical data show that the mathematical model fully meets the demand of hot- rolling production.On the basis of the optimal number of rolling units,the transport time is shortened,the hot charging rate is in- creased and the product quality is optimized.Compared with a human-computer method,the results from the mathematical model and hybrid algorithm have a better performance of high production and energysaving efficiency. KEY WORDS hot rolling:planning;traveling salesman problem:genetic algorithms:tabu search 板坯热轧生产是将板坯加热后经粗轧和精轧机lm,TSP)进行求解回.在此基础上，研究者以最小 组进行轧制加工，热轧生产调度水平直接影响产品 化轧制单元的惩罚值作为优化目标，以轧制单元的 质量和生产效率.热轧批量计划的编制是热轧生产 总轧制长度为硬约束，将该问题归结为多旅行商问 调度的重要内容，主要是确定板坯在热轧工序的分 (multiple traveling salesman problem,MTSP) 组和排序，不仅要考虑本工序的工艺约束，同时还要 或车辆路径问题(vehicle routing problem,VRP)6-) 考虑与其他工序的衔接，以达到提高产量、降低能耗 进行求解.并且，考虑到加热工序能耗，部分研究者 的要求 将热送热装率纳入优化目标中进行研究00，进一 目前，热轧批量计划编制问题的主要研究方法 步实现了热轧批量计划编制问题的优化.但是，以 是基于路径优化问题和惩罚函数表建模.Kosiba等 最小化轧制单元的惩罚值作为计划编制的优化目标 首先提出限制钢板宽度、厚度和硬度跳跃的惩罚函 仅能实现产品质量的最佳化，无法有效反映生产成 数表，并采用旅行商问题(traveling salesman prob- 本，而在满足用户质量要求的前提下，降低生产成本 收稿日期：201101一17 基金项目：教有部科学技术研究重点资助项目(107008)

第 34 卷 第 4 期 2012 年 4 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 4 Apr． 2012 板坯热轧批量计划数学模型及求解算法 杨业建 姜泽毅 张欣欣 北京科技大学机械工程学院，北京 100083 通信作者，E-mail: zyjiang@ ustb． edu． cn 摘 要 根据热轧工艺特点将板坯热轧批量计划编制问题归结为不确定旅行商数的多旅行商问题，建立了以生产成本最小 化和产品质量最优化为主次目标且考虑加热区段能耗的生产调度数学模型，并采用遗传算法和禁忌搜索相结合的混合算法 进行求解． 基于实际生产数据的计算结果表明: 该模型充分满足了现场热轧批量计划编制的需求，在轧制单元数最优的基础 上，缩短了传搁时间，提高了热送热装率，优化了产品质量． 与人机结合方式相比，本文模型的计算结果体现了更好的高产和 节能效果． 关键词 热轧; 计划编制; 旅行商问题; 遗传算法; 禁忌搜索算法 分类号 TF089; F406. 2 Mathematical model and solving algorithm for the lot planning of 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 According to the technical demand of hot-rolling production，the lot planning of slab hot rolling was summed up as a multiple traveling salesperson problem with uncertain traveling salesman number． A production scheduling mathematical model consid￾ering the energy consumption of the heating section was proposed，with minimizing the production cost as the primary objective and op￾timizing the product quality as the secondary objective． A hybrid algorithm based on the genetic algorithm and the tabu search algorithm was proposed to solve the problem． Simulation results of practical data show that the mathematical model fully meets the demand of hot￾rolling production． On the basis of the optimal number of rolling units，the transport time is shortened，the hot charging rate is in￾creased and the product quality is optimized． Compared with a human-computer method，the results from the mathematical model and hybrid algorithm have a better performance of high production and energy-saving efficiency． KEY WORDS hot rolling; planning; traveling salesman problem; genetic algorithms; tabu search 收稿日期: 2011--01--17 基金项目: 教育部科学技术研究重点资助项目( 107008) 板坯热轧生产是将板坯加热后经粗轧和精轧机 组进行轧制加工，热轧生产调度水平直接影响产品 质量和生产效率． 热轧批量计划的编制是热轧生产 调度的重要内容，主要是确定板坯在热轧工序的分 组和排序，不仅要考虑本工序的工艺约束，同时还要 考虑与其他工序的衔接，以达到提高产量、降低能耗 的要求［1］． 目前，热轧批量计划编制问题的主要研究方法 是基于路径优化问题和惩罚函数表建模． Kosiba 等 首先提出限制钢板宽度、厚度和硬度跳跃的惩罚函 数表，并采用旅行商问题( traveling salesman prob￾lem，TSP) 进行求解［2］． 在此基础上，研究者以最小 化轧制单元的惩罚值作为优化目标，以轧制单元的 总轧制长度为硬约束，将该问题归结为多旅行商问 题( multiple traveling salesman problem，MTSP) ［3--5］ 或车辆路径问题( vehicle routing problem，VRP) ［6--9］ 进行求解． 并且，考虑到加热工序能耗，部分研究者 将热送热装率纳入优化目标中进行研究［10--11］，进一 步实现了热轧批量计划编制问题的优化． 但是，以 最小化轧制单元的惩罚值作为计划编制的优化目标 仅能实现产品质量的最佳化，无法有效反映生产成 本，而在满足用户质量要求的前提下，降低生产成本 DOI:10.13374/j.issn1001-053x.2012.04.009

·458 北京科技大学学报 第34卷 比单纯提高产品质量更加重要.因此，综合考虑产 (3)一个轧制单元所包含的板坯数量须达到规 品质量和生产成本的数学模型及其求解方法仍有待 定的最少板坯数 探索 在板坯热轧生产中，生产成本可分为轧制成本、 实际生产中，换辊次数和生产时间对产量和能 加热成本、生产时间和生产质量等.由于它们之间 耗等影响十分显著，减少换辊次数可以有效降低轧 有一定相关性，准确的总量定量描述有一定困难，可 制成本、提高产量，缩短板坯在工序间的停留时间可 选用一些容易量化的技术指标进行评价.与生产成 以减少热轧前加热所消耗的能量，对降低生产成本 本直接相关的常用技术指标有轧制单元数、热送热 大有裨益.因此，本文采用轧制单元数和传搁时间 装率和惩罚值等.轧制单元数反应换辊次数，更换 作为反映生产成本的优化指标，轧制单元的惩罚值 轧辊需要时间且轧辊的更换成本很高，为了降低生 作为反映生产质量的优化指标，以生产成本最小化 产成本，轧制单元数在正常生产的前提下应尽可能 和生产质量最优化为目标建立数学模型.将热轧批 小.热送热装率是统计入炉温度在热装温度之上的 量计划编制问题归结为不确定旅行商数的多旅行商 板坯所占的比率，在生产中易于实现，但该指标定量 问题，使用遗传算法和禁忌搜索相结合的混合算法 化描述的效果还不够精准，难以准确反映生产的紧 进行求解，以获得比人机结合方式结果更具有高产 凑性和能耗水平.本文采用板坯从连铸出坯到进入 和节能效果的解， 加热炉所消耗的时间作为评价指标（借用传统的钢 1问题描述 锭传搁时间概念回，本文称其为板坯的“传搁时 间”)，替代热送热装率，可以更加准确地描述板坯 热轧是通过轧辊的挤压作用使高温板坯发生形 热送过程的时间因素和加热过程的能耗成本.惩罚 变.轧辊在轧制过程中会发生磨损，到达一定程度 值是定量评价轧制质量的指标之一，在产品质量满 后继续使用会影响产品质量，需要及时更换，其中工 足用户需求且不影响成本的基础上越低越好.本文 作辊直接与板坯接触，受到的磨损相对较重，其更换 采用的三个评价指标分别是轧制单元数、传搁时间 频率要高于支撑辊。在热轧生产调度中，两次工作 和惩罚值，它们与生产成本之间的关联关系如图1 辊更换时间内生产的板坯序列称为一个轧制单元， 所示 若干个轧制单元组成一个热轧批量计划. 出于对产品质量、轧辊寿命和生产效益等因素 生户产成本 的考虑，编制热轧批量计划必须遵守一定的工艺约 轧制成本 束.例如：一个轧制单元内允许轧制板坯的总长度 (轧制单元生产能力)受到工作辊寿命的限制；一个 加热成本 制 轧制单元内板坯的宽度应该呈“倒梯形”（先宽后 传时间 窄)的变化趋势.紧邻轧制的两块板坯的宽度、厚度 生产倒问 或硬度变化称为跳跃，符合轧制单元中变化趋势的 跳跃为正跳，不符合则为反跳。根据跳跃值和惩罚 产质量 罚值 函数表（正跳和反跳的惩罚函数不同）计算得到轧 制单元的惩罚值，可作为描述该单元轧制质量的指 图1评价指标与生产成本之间的关系 标之一 Fig.1 Relation between evaluation indicators and production cost 一般来说，热轧生产中必须遵守的工艺约束主 由图1可知，这三个评价指标与生产成本之间 要包括以下几点 的关联机制并不相同，对生产成本的影响程度也有 (1)同一轧制单元中，相邻两块板坯的宽度、厚 差异.本文通过不同指标影响程度的重要性分析， 度和硬度差值限制： 采用串联方式按轧制单元数→传搁时间→惩罚值的 (a)板坯宽度需呈递减规律变化，厚度最好是 重要程度排序，在计算中分三个阶段对结果进行串 非减方向变化，而硬度渐近递增或渐近递减均可； 行寻优. (b)厚度和硬度变化要平稳，不允许反复跳跃： (©)宽度、厚度和硬度不允许同时跳跃. 2数学模型 (2)一个轧制单元轧制板坯的总长度和连续轧 板坯热轧批量计划问题可以概述为：有n块已 制相同宽度板坯的总长度均有一定限制. 知长度、宽度、厚度、硬度和到达时间的一组板坯，给

北 京 科 技 大 学 学 报 第 34 卷 比单纯提高产品质量更加重要． 因此，综合考虑产 品质量和生产成本的数学模型及其求解方法仍有待 探索． 实际生产中，换辊次数和生产时间对产量和能 耗等影响十分显著，减少换辊次数可以有效降低轧 制成本、提高产量，缩短板坯在工序间的停留时间可 以减少热轧前加热所消耗的能量，对降低生产成本 大有裨益． 因此，本文采用轧制单元数和传搁时间 作为反映生产成本的优化指标，轧制单元的惩罚值 作为反映生产质量的优化指标，以生产成本最小化 和生产质量最优化为目标建立数学模型． 将热轧批 量计划编制问题归结为不确定旅行商数的多旅行商 问题，使用遗传算法和禁忌搜索相结合的混合算法 进行求解，以获得比人机结合方式结果更具有高产 和节能效果的解． 1 问题描述 热轧是通过轧辊的挤压作用使高温板坯发生形 变． 轧辊在轧制过程中会发生磨损，到达一定程度 后继续使用会影响产品质量，需要及时更换，其中工 作辊直接与板坯接触，受到的磨损相对较重，其更换 频率要高于支撑辊． 在热轧生产调度中，两次工作 辊更换时间内生产的板坯序列称为一个轧制单元， 若干个轧制单元组成一个热轧批量计划． 出于对产品质量、轧辊寿命和生产效益等因素 的考虑，编制热轧批量计划必须遵守一定的工艺约 束． 例如: 一个轧制单元内允许轧制板坯的总长度 ( 轧制单元生产能力) 受到工作辊寿命的限制; 一个 轧制单元内板坯的宽度应该呈“倒梯形”( 先宽后 窄) 的变化趋势． 紧邻轧制的两块板坯的宽度、厚度 或硬度变化称为跳跃，符合轧制单元中变化趋势的 跳跃为正跳，不符合则为反跳． 根据跳跃值和惩罚 函数表( 正跳和反跳的惩罚函数不同) 计算得到轧 制单元的惩罚值，可作为描述该单元轧制质量的指 标之一． 一般来说，热轧生产中必须遵守的工艺约束主 要包括以下几点． ( 1) 同一轧制单元中，相邻两块板坯的宽度、厚 度和硬度差值限制: ( a) 板坯宽度需呈递减规律变化，厚度最好是 非减方向变化，而硬度渐近递增或渐近递减均可; ( b) 厚度和硬度变化要平稳，不允许反复跳跃; ( c) 宽度、厚度和硬度不允许同时跳跃． ( 2) 一个轧制单元轧制板坯的总长度和连续轧 制相同宽度板坯的总长度均有一定限制． ( 3) 一个轧制单元所包含的板坯数量须达到规 定的最少板坯数． 在板坯热轧生产中，生产成本可分为轧制成本、 加热成本、生产时间和生产质量等． 由于它们之间 有一定相关性，准确的总量定量描述有一定困难，可 选用一些容易量化的技术指标进行评价． 与生产成 本直接相关的常用技术指标有轧制单元数、热送热 装率和惩罚值等． 轧制单元数反应换辊次数，更换 轧辊需要时间且轧辊的更换成本很高，为了降低生 产成本，轧制单元数在正常生产的前提下应尽可能 小． 热送热装率是统计入炉温度在热装温度之上的 板坯所占的比率，在生产中易于实现，但该指标定量 化描述的效果还不够精准，难以准确反映生产的紧 凑性和能耗水平． 本文采用板坯从连铸出坯到进入 加热炉所消耗的时间作为评价指标( 借用传统的钢 锭传搁时间概念［12］，本文称其为板坯的“传搁时 间”) ，替代热送热装率，可以更加准确地描述板坯 热送过程的时间因素和加热过程的能耗成本． 惩罚 值是定量评价轧制质量的指标之一，在产品质量满 足用户需求且不影响成本的基础上越低越好． 本文 采用的三个评价指标分别是轧制单元数、传搁时间 和惩罚值，它们与生产成本之间的关联关系如图 1 所示． 图 1 评价指标与生产成本之间的关系 Fig． 1 Relation between evaluation indicators and production cost 由图 1 可知，这三个评价指标与生产成本之间 的关联机制并不相同，对生产成本的影响程度也有 差异． 本文通过不同指标影响程度的重要性分析， 采用串联方式按轧制单元数→传搁时间→惩罚值的 重要程度排序，在计算中分三个阶段对结果进行串 行寻优． 2 数学模型 板坯热轧批量计划问题可以概述为: 有 n 块已 知长度、宽度、厚度、硬度和到达时间的一组板坯，给 ·458·

第4期 杨业建等：板还热轧批量计划数学模型及求解算法 ·459 定每个轧制单元轧制能力等限定条件，通过对板坯 进行组批和排序，确定轧制单元数以及每个轧制单 Aal≤0《eB,le0, (4) 元内按宽度“倒梯形”排列的顺序.本文选取生产成 名al,≤LkeB, (5) 本最低和质量最优为优化目标，经转化可以描述为： Aa≥NkeB. (6) 在满足各项工艺约束的前提下，首先保证最小化轧 式中：m为轧制单元数；a为轧制单元间隔判定的布 制单元数，其次最小化传搁时间，最后最小化轧制单 尔量，描述为 元的平均惩罚值.热轧批量计划数学模型可描述为 f1, 板坯i在板坯j之后紧邻轧制且d,=∞， Min ag= 0,其他， m1+三 (1) i,j∈A 1 d,为板坯j在板坯i之后紧邻轧制的惩罚值；A={1, (2) n 2,…,s}为板坯序号集合；n为板坯个数；t.为传搁 S=六AA点B4: 时间之和，min;te为板坯i入炉时间，min;ta为板坯i (3) 送达热轧工序时间，min;S为轧制单元平均惩罚值： s.t. B是同一轧制单元相邻板坯判定的布尔量，描述为 1, 板坯i和板坯j同属于轧制单元k且j在i之后紧邻轧制 Bik= ij∈A,k∈B: 0,其他， B={1,2,…,m}为轧制单元序号集合；04是相同宽 度判定的布尔量，描述为 1,板坯i属于轧制单元k且其宽度序号为l ={ 0,其他， i∈A,l∈Q,k∈B; L:为板坯i的长度，m;Q为一个轧制单元中连续 部最优.本文采用的方法是并行方法，即以板坯为 轧制相同宽度板坯的总长度上限，m;Q={1,2,…, 排序个体，从所有板坯中同时编制出若干个轧制单 w}为所有板坯宽度序号的集合；δ：是属于某一轧制 元，本文将热轧批量计划编制问题归结为不确定旅 单元判定的布尔量，描述为 行商数的多旅行商问题. d-位红不雾断不 多旅行商问题是旅行商问题的一类更具实际应 i∈A,keB; 用价值的扩展问题.所谓多旅行商问题，通常可以 L为一个轧制单元允许轧制板坯的总长度上限， 描述如下：多个旅行商分别走不同的旅行路线，使得 m;N为一个轧制单元所允许的最少板坯数. 每个城市有且仅有一个旅行商经过，且总路程最短 式(1)表示轧制单元个数最少.本文采用惩罚 本文将板坯类比为多旅行商问题中的城市，每个轧 值表示热轧生产工艺中板坯的宽度、厚度和硬度跳 制单元类比为多旅行商问题中每个旅行商的旅行路 跃对质量的影响，跳跃越大则惩罚值越大，如果违反 线，紧邻轧制板坯的跳跃惩罚值类比为两个城市之 生产工艺则惩罚值设为无穷大，作为轧制单元间隔 间的路程，从而将热轧批量计划编制问题归结为多 的判据：式(2)表示计划所需要的传搁时间最少：式 旅行商问题进行求解.多旅行商问题是NP-ard问 (3)表示所有轧制单元的平均惩罚值最小；式(4)表 题，直接根据多旅行商问题自身的特点进行求解很 示一个轧制单元中连续轧制相同宽度板坯的总长度 困难.为了能方便求解，通常把多旅行商问题转化 不能超过Qx:式(5)表示一个轧制单元允许轧制 为旅行商问题来解决.轧制单元数是热轧批量 板坯的总长度不能超过L:式(6)表示一个轧制单 计划编制中的主要优化目标，相当于多旅行商问题 元的板坯数不能小于Via· 中的旅行商数.本文通过紧邻轧制板坯的跳跃惩罚 值来划分轧制单元进而得到轧制单元数，将热轧批 3算法设计 量计划编制归结为不确定旅行商数的多旅行商问题 3.1多旅行商问题 进行求解。求解算法采用遗传算法和禁忌搜索相结 热轧批量计划编制涉及板坯的聚类和排序.钢 合的混合算法 铁企业在实际编制热轧计划时，一般都是从预选池 3.2遗传算法 的多个任务当中依次编制出若干个轧制单元，这种 遗传算法(genetic algorithms,.GA)是模仿自然 策略为串行策略，类似于贪婪方法，有可能会陷入局 界生物进化中的遗传、变异和自然选择过程，对解空

第 4 期 杨业建等: 板坯热轧批量计划数学模型及求解算法 定每个轧制单元轧制能力等限定条件，通过对板坯 进行组批和排序，确定轧制单元数以及每个轧制单 元内按宽度“倒梯形”排列的顺序． 本文选取生产成 本最低和质量最优为优化目标，经转化可以描述为: 在满足各项工艺约束的前提下，首先保证最小化轧 制单元数，其次最小化传搁时间，最后最小化轧制单 元的平均惩罚值． 热轧批量计划数学模型可描述为 Min m = 1 + ∑i∈A ∑ i≠j j∈A αij ， ( 1) tw = 1 n ·∑i∈A ( tic － tir) ， ( 2) S = 1 m ·∑k∈B ∑i∈A ∑ i≠j j∈A βijk ·dij ; ( 3) s． t． ∑i∈A θilk ·Li≤Qmax ( k∈B，l∈Q) ， ( 4) ∑i∈A δik ·Li≤Lmax ( k∈B) ， ( 5) ∑i∈A δik≥Nmin ( k∈B) ． ( 6) 式中: m 为轧制单元数; αij为轧制单元间隔判定的布 尔量，描述为 αij = 1， 板坯 i 在板坯 j 之后紧邻轧制且 dij = ∞ ， {0， 其他， i，j∈A; dij为板坯 j 在板坯 i 之后紧邻轧制的惩罚值; A = { 1， 2，…，s} 为板坯序号集合; n 为板坯个数; tw 为传搁 时间之和，min; tic为板坯 i 入炉时间，min; tir为板坯 i 送达热轧工序时间，min; S 为轧制单元平均惩罚值; βijk是同一轧制单元相邻板坯判定的布尔量，描述为 βijk = 1， 板坯 i 和板坯 j 同属于轧制单元 k 且 j 在 i 之后紧邻轧制， {0， 其他， i，j∈A，k∈B; B = { 1，2，…，m} 为轧制单元序号集合; θilk是相同宽 度判定的布尔量，描述为 θilk = 1， 板坯 i 属于轧制单元 k 且其宽度序号为 l， {0， 其他， i∈A，l∈Q，k∈B; Li 为板坯 i 的长度，m; Qmax为一个轧制单元中连续 轧制相同宽度板坯的总长度上限，m; Q = { 1，2，…， w} 为所有板坯宽度序号的集合; δik是属于某一轧制 单元判定的布尔量，描述为 δik = 1， 板坯 i 属于轧制单元 k， {0， 板坯 i 不属于轧制单元 k， i∈A，k∈B; Lmax为一个轧制单元允许轧制板坯的总长度上限， m; Nmin为一个轧制单元所允许的最少板坯数． 式( 1) 表示轧制单元个数最少． 本文采用惩罚 值表示热轧生产工艺中板坯的宽度、厚度和硬度跳 跃对质量的影响，跳跃越大则惩罚值越大，如果违反 生产工艺则惩罚值设为无穷大，作为轧制单元间隔 的判据; 式( 2) 表示计划所需要的传搁时间最少; 式 ( 3) 表示所有轧制单元的平均惩罚值最小; 式( 4) 表 示一个轧制单元中连续轧制相同宽度板坯的总长度 不能超过 Qmax ; 式( 5) 表示一个轧制单元允许轧制 板坯的总长度不能超过 Lmax ; 式( 6) 表示一个轧制单 元的板坯数不能小于 Nmin ． 3 算法设计 3. 1 多旅行商问题 热轧批量计划编制涉及板坯的聚类和排序． 钢 铁企业在实际编制热轧计划时，一般都是从预选池 的多个任务当中依次编制出若干个轧制单元，这种 策略为串行策略，类似于贪婪方法，有可能会陷入局 部最优． 本文采用的方法是并行方法，即以板坯为 排序个体，从所有板坯中同时编制出若干个轧制单 元，本文将热轧批量计划编制问题归结为不确定旅 行商数的多旅行商问题． 多旅行商问题是旅行商问题的一类更具实际应 用价值的扩展问题． 所谓多旅行商问题，通常可以 描述如下: 多个旅行商分别走不同的旅行路线，使得 每个城市有且仅有一个旅行商经过，且总路程最短． 本文将板坯类比为多旅行商问题中的城市，每个轧 制单元类比为多旅行商问题中每个旅行商的旅行路 线，紧邻轧制板坯的跳跃惩罚值类比为两个城市之 间的路程，从而将热轧批量计划编制问题归结为多 旅行商问题进行求解． 多旅行商问题是 NP-hard 问 题，直接根据多旅行商问题自身的特点进行求解很 困难． 为了能方便求解，通常把多旅行商问题转化 为旅行商问题来解决［13］． 轧制单元数是热轧批量 计划编制中的主要优化目标，相当于多旅行商问题 中的旅行商数． 本文通过紧邻轧制板坯的跳跃惩罚 值来划分轧制单元进而得到轧制单元数，将热轧批 量计划编制归结为不确定旅行商数的多旅行商问题 进行求解． 求解算法采用遗传算法和禁忌搜索相结 合的混合算法． 3. 2 遗传算法 遗传算法( genetic algorithms，GA) 是模仿自然 界生物进化中的遗传、变异和自然选择过程，对解空 ·459·

·460· 北京科技大学学报 第34卷 间点进行遗传操作的一类模拟进化算法.根据问题 定，最终可得到类似如下排序的结果： 的特征，首先随机地选择一组初始解构成初始种群， C=B275641]. 用遗传算子对其进行变换，每变换一次就会形成下 依次计算热轧批量计划中相邻两板坯的跳跃惩 一代待选种群，评价其适应性，适应性好的在下一代 罚值，若d6=∞，则在板坯5和6之间插入分割符 中优先予以选择，形成下一代种群后继续运算，直到 从而得到完整的解向量： 达到停止条件. C=B275*641] 实现优化问题的遗传算法求解，需要根据问题 3.2.4选择机制 特征设计解的编码方式和遗传算子、选择适应值函 当前种群经过遗传变异后生成子代种群，将当 数、给定合适的选择机制和停止条件.本文采用的 前种群并入到子代种群，计算适应值，然后将适应值 编码方式、遗传算子、适应值函数、选择机制和停止 最好的前几个个体直接复制到新一代种群中，剩余 条件如下， 的个体根据种群规模按照随机通用采样方法的确 3.2.1解的编码方式 定是否复制到新一代种群 每一个解表示一种热轧批量计划，采用一个向 3.2.5停止条件 量表示，在这个向量中包括板坯的加工顺序和轧制 停止条件设置为算法运行到一个预先设定的迭 单元的划分两类信息.采用板坯号的排列顺序表示 代次数时停止并取当前种群中最好的结果输出 热轧加工顺序，分隔符作为不同轧制单元的间隔标 3.3禁忌搜索算法 志.假设有7块板坯（实际生产中每次热轧批量计 禁忌搜索是解决组合优化问题的一种策略，它 划板坯数一般为150个以上)，一种可能的组批和 于1970年首先应用于非线性覆盖问题的优化过程， 排序方式可以编码为如下的向量： 后来又应用于从图论到一般纯整数规划问题和混合 023*45*67]. 整数规划问题及旅行商问题等.文献6]详细阐述 根据编码可知，板坯1、2和3为第一个轧制单元，板 了禁忌搜索算法的原理和应用.禁忌搜索的特点 坯4和5为第二个轧制单元，板坯6和7为第三个 是：为了避免搜索陷入死循环，构造了一个短期循环 轧制单元，板坯加工顺序为1、2、3、4、5、6和7. 记忆表一禁忌表，表中存放刚进行过的I引（禁忌 3.2.2适应值函数 表的长度)个邻域移动，每个移动在以后的11次循 采用式(1)、式(2)和式(3)的优化函数目标值 环内是禁止的，禁忌表在搜索过程中不断修改，使搜 作为适应度函数值.根据式(1)、式(2)和式(3)的 索向着更好的方向前进 重要性，在计算中分阶段进行寻优 本文采用的方法是：将所有板坯两两配对，形成 3.2.3遗传算子 板坯对群，针对每次遗传算法运算所得到的下一代 遗传算子采用两交换启发交叉算法.其基 种群中的每一个解，依次交换每对板坯对，得到新的 本思想为：以7块板坯为例，假设7块板坯分别为 解，计算其适应值，找到适应值优于原解的新解取代 1、2、3、4、5、6和7.随机选出一对未匹配的双亲去 原来的解，若无则保持不变.具体方法为：假设下一 除分隔符后， 代种群中的一个解0=B275*641],去除分隔 F=7264153], 符后0。=B275641],则会有C=21对板坯 M=B217564]. 对，依次交换每对板坯对形成21个新的解向量，假 随机选出初始板坯的位置号j=3,板坯号S,= 设选取的板坯对为(6,5)，则新的解向量为O,=B 7,左转动使两双亲的第三个位置的板坯号为7， 276541],计算紧邻轧制的两块板坯跳跃的惩罚 F=5372641], 值，若d.6=∞则在板坯7和6之间插入分隔符，从 M1=2175643], 而得到新的解0=B27*6541].重复上述过 C=xx7xxxx]. 程，会得到21个新解，计算其适应值与原有的解进 然后，选择位置号j=4处的板坯.若d2>ds, 行比较，选取最优的解取代原有的解 则F,以5为中心左转得到如下中间代： 3.4混合算法 F=41x5326], 在大多数工程优化问题中，由于常常带有复杂 M2=21x5643], 的约束条件，简单的遗传算法往往不能很好地解决 C2=xx75xxx 这类工程优化问题.在遗传算法中增加所求解问题 重复上述过程直到子代中所有位置的板坯都确 的先验知识对于求解效果的影响很大叼.本文选

北 京 科 技 大 学 学 报 第 34 卷 间点进行遗传操作的一类模拟进化算法． 根据问题 的特征，首先随机地选择一组初始解构成初始种群， 用遗传算子对其进行变换，每变换一次就会形成下 一代待选种群，评价其适应性，适应性好的在下一代 中优先予以选择，形成下一代种群后继续运算，直到 达到停止条件． 实现优化问题的遗传算法求解，需要根据问题 特征设计解的编码方式和遗传算子、选择适应值函 数、给定合适的选择机制和停止条件． 本文采用的 编码方式、遗传算子、适应值函数、选择机制和停止 条件如下． 3. 2. 1 解的编码方式 每一个解表示一种热轧批量计划，采用一个向 量表示，在这个向量中包括板坯的加工顺序和轧制 单元的划分两类信息． 采用板坯号的排列顺序表示 热轧加工顺序，分隔符作为不同轧制单元的间隔标 志． 假设有 7 块板坯( 实际生产中每次热轧批量计 划板坯数一般为 150 个以上) ，一种可能的组批和 排序方式可以编码为如下的向量: ［1 2 3 * 4 5 * 6 7］． 根据编码可知，板坯 1、2 和 3 为第一个轧制单元，板 坯 4 和 5 为第二个轧制单元，板坯 6 和 7 为第三个 轧制单元，板坯加工顺序为 1、2、3、4、5、6 和 7． 3. 2. 2 适应值函数 采用式( 1) 、式( 2) 和式( 3) 的优化函数目标值 作为适应度函数值． 根据式( 1) 、式( 2) 和式( 3) 的 重要性，在计算中分阶段进行寻优． 3. 2. 3 遗传算子 遗传算子采用两交换启发交叉算法［14］． 其基 本思想为: 以 7 块板坯为例，假设 7 块板坯分别为 1、2、3、4、5、6 和 7． 随机选出一对未匹配的双亲去 除分隔符后， F =［7 2 6 4 1 5 3］， M =［3 2 1 7 5 6 4］． 随机选出初始板坯的位置号 j = 3，板坯号 Sj = 7，左转动使两双亲的第三个位置的板坯号为 7， F =［5 3 7 2 6 4 1］， M1 =［2 1 7 5 6 4 3］， C1 =［x x 7 x x x x］． 然后，选择位置号 j = 4 处的板坯． 若 d72 ＞ d75， 则 F1以 5 为中心左转得到如下中间代: F =［4 1 x 5 3 2 6］， M2 =［2 1 x 5 6 4 3］， C2 =［x x 7 5 x x x］． 重复上述过程直到子代中所有位置的板坯都确 定，最终可得到类似如下排序的结果: C =［3 2 7 5 6 4 1］． 依次计算热轧批量计划中相邻两板坯的跳跃惩 罚值，若 d56 = ∞ ，则在板坯 5 和 6 之间插入分割符 从而得到完整的解向量: C =［3 2 7 5 * 6 4 1］． 3. 2. 4 选择机制 当前种群经过遗传变异后生成子代种群，将当 前种群并入到子代种群，计算适应值，然后将适应值 最好的前几个个体直接复制到新一代种群中，剩余 的个体根据种群规模按照随机通用采样方法［15］确 定是否复制到新一代种群． 3. 2. 5 停止条件 停止条件设置为算法运行到一个预先设定的迭 代次数时停止并取当前种群中最好的结果输出． 3. 3 禁忌搜索算法 禁忌搜索是解决组合优化问题的一种策略，它 于 1970 年首先应用于非线性覆盖问题的优化过程， 后来又应用于从图论到一般纯整数规划问题和混合 整数规划问题及旅行商问题等． 文献［16］详细阐述 了禁忌搜索算法的原理和应用． 禁忌搜索的特点 是: 为了避免搜索陷入死循环，构造了一个短期循环 记忆表———禁忌表，表中存放刚进行过的 | θ | ( 禁忌 表的长度) 个邻域移动，每个移动在以后的 | θ | 次循 环内是禁止的，禁忌表在搜索过程中不断修改，使搜 索向着更好的方向前进． 本文采用的方法是: 将所有板坯两两配对，形成 板坯对群，针对每次遗传算法运算所得到的下一代 种群中的每一个解，依次交换每对板坯对，得到新的 解，计算其适应值，找到适应值优于原解的新解取代 原来的解，若无则保持不变． 具体方法为: 假设下一 代种群中的一个解 O =［3 2 7 5 * 6 4 1］，去除分隔 符后 O0 =［3 2 7 5 6 4 1］，则会有 C2 7 = 21 对板坯 对，依次交换每对板坯对形成 21 个新的解向量，假 设选取的板坯对为( 6，5) ，则新的解向量为 O1 =［3 2 7 6 5 4 1］，计算紧邻轧制的两块板坯跳跃的惩罚 值，若 d7，6 = ∞ 则在板坯 7 和 6 之间插入分隔符，从 而得到新的解 O =［3 2 7 * 6 5 4 1］． 重复上述过 程，会得到 21 个新解，计算其适应值与原有的解进 行比较，选取最优的解取代原有的解． 3. 4 混合算法 在大多数工程优化问题中，由于常常带有复杂 的约束条件，简单的遗传算法往往不能很好地解决 这类工程优化问题． 在遗传算法中增加所求解问题 的先验知识对于求解效果的影响很大［17］． 本文选 ·460·

第4期 杨业建等：板还热轧批量计划数学模型及求解算法 ·461· 用遗传算法和禁忌搜索相结合的混合算法求解，其 一个结果产生影响.惩罚值在上述两个指标未达到 详细步骤如下. 稳定时，一直处于起伏状态，总的趋势看，其随轧制 STEP1生成解的初始种群.一部分解按照板 单元数的减少而增加，在轧制单元数稳定时，传搁时 坯的宽度、厚度、硬度和到达时间排列生成，其余的 间也会对其产生影响.在轧制单元数和传搁时间一 解随机生成.初始种群的规模为50， 定的情况下，其优化余地已不大，继续寻优的目的是 STEP2采用两交换启发交叉算法，生成子代 在不增加成本的基础上，进一步提高产品质量，实现 待选种群. 生产成本最小基础上产品质量最优的目标.根据上 STEP3合并当前种群和子代待选种群，去除 述三个目标的收敛情况可以看出，本文采用的混合 相同解，然后从中选出50个解形成下一次计算的初 算法对于模型的求解较为理想 始种群 图3为优化计算得到的批量计划中一个较大轧 STEP4对下一次计算的初始种群中的每个个 制单元(136块板坯)内板坯宽度、厚度和硬度的变 体进行禁忌搜索，得到的最优解取代相应的初始种 化趋势.从图中可以看出，板坯宽度递减变化呈“倒 群中的个体，形成下一次计算的种群.禁忌搜索算 梯形”，厚度递增，无反复跳跃，存在一定的反跳，硬 法根据禁忌表对所有板坯对搜索一次，并更新禁 度递减，宽度、厚度和硬度未同时跳跃，符合轧制工 忌表 艺要求 STEP5判断是否满足停止条件，如满足，算法 2000 一板坏宽度 0 终止，输出当前种群中的最优解：如不满足，则转 一·-板坯硬度 1900 STEP2. …板坏厚 4求解过程分析 1700 选取某时间段内的实际生产合同计划（共250 1600 块板坯)进行优化计算，计算步数为100步，求解过 1500 程中三个优化目标值的变化趋势如图2所示.图中 21 416181101 121 轧制单元内的板坯顺序号 的三条曲线分别对应着三个优化目标，其中轧制单 元数为实际值，传搁时间和惩罚值为了便于展现收 图3单个轧制单元内板坯宽度、厚度、硬度的变化 Fig.3 Changes of slab width,thickness and hardness in a rolling unit 敛趋势，转化为相对值.计算采用普通P℃机，所需 时间约为l5min,计算速度满足现场完成批量计划 5应用实例 编制计算的需求 10 轧制单元数 本文根据某厂热轧生产线的实际生产数据进行 传搁时问相对值 了多批次的热轧批量计划编制工作，并与现场采用 惩罚值相对位 的人机结合编制方式进行了对比分析.连铸区段的 多座连铸机均可以直接将连铸坯送达该轧线，且轧 线中的加热工序配有板坯库.其中4组有代表性的 40 60 80 100 生产数据为：(1)批次1,250块板坯，共有13种规 求解步数 格（规格变化较大）：(2)批次2,156块板坯，共有8 图2评价指标的变化趋势 种规格（规格变化较大）；(3)批次3,250块板坯，共 Fig.2 Trend of evaluation indicators 有7种规格（规格变化较小）；(4)批次4,156块板 由图2可以看出，轧制单元数随着求解步数的 坯，共有4种规格（规格变化较小）. 增加而逐渐收敛，优化效果较好.传搁时间随着求 本文将所有板坯都编入批量计划，种群规模为 解步数的增加，并非一直收敛，而是轧制单元数减少 50,禁忌长度为6，计算步数为200，其结果与人机结 时增大，轧制单元数稳定时收敛.这是由于轧制单 合方式结果的对比如表1所示，两种方式的计算结 元数主要是由轧制板坯的规格和轧制工艺决定的， 果均是在假设加热工序为理想炉区（不考虑炉群调 而平均传搁时间主要是由连铸生产顺序及轧制生产 度)下得到的.表中的热送热装率是根据板坯传搁 顺序的差异决定的，因此轧制单元数和传搁时间的 时间和高温时温降速率计算得到入炉温度，再通过 优化方向呈一定角度，一个结果的优化必然会对另 板坯数量统计得到的

第 4 期 杨业建等: 板坯热轧批量计划数学模型及求解算法 用遗传算法和禁忌搜索相结合的混合算法求解，其 详细步骤如下． STEP1 生成解的初始种群． 一部分解按照板 坯的宽度、厚度、硬度和到达时间排列生成，其余的 解随机生成． 初始种群的规模为 50． STEP2 采用两交换启发交叉算法，生成子代 待选种群． STEP3 合并当前种群和子代待选种群，去除 相同解，然后从中选出 50 个解形成下一次计算的初 始种群． STEP4 对下一次计算的初始种群中的每个个 体进行禁忌搜索，得到的最优解取代相应的初始种 群中的个体，形成下一次计算的种群． 禁忌搜索算 法根据禁忌表对所有板坯对搜索一次，并更新禁 忌表． STEP5 判断是否满足停止条件，如满足，算法 终止，输出当前种群中的最优解; 如不满足，则转 STEP2． 4 求解过程分析 选取某时间段内的实际生产合同计划( 共 250 块板坯) 进行优化计算，计算步数为 100 步，求解过 程中三个优化目标值的变化趋势如图 2 所示． 图中 的三条曲线分别对应着三个优化目标，其中轧制单 元数为实际值，传搁时间和惩罚值为了便于展现收 敛趋势，转化为相对值． 计算采用普通 PC 机，所需 时间约为 15 min，计算速度满足现场完成批量计划 编制计算的需求． 图 2 评价指标的变化趋势 Fig． 2 Trend of evaluation indicators 由图 2 可以看出，轧制单元数随着求解步数的 增加而逐渐收敛，优化效果较好． 传搁时间随着求 解步数的增加，并非一直收敛，而是轧制单元数减少 时增大，轧制单元数稳定时收敛． 这是由于轧制单 元数主要是由轧制板坯的规格和轧制工艺决定的， 而平均传搁时间主要是由连铸生产顺序及轧制生产 顺序的差异决定的，因此轧制单元数和传搁时间的 优化方向呈一定角度，一个结果的优化必然会对另 一个结果产生影响． 惩罚值在上述两个指标未达到 稳定时，一直处于起伏状态，总的趋势看，其随轧制 单元数的减少而增加，在轧制单元数稳定时，传搁时 间也会对其产生影响． 在轧制单元数和传搁时间一 定的情况下，其优化余地已不大，继续寻优的目的是 在不增加成本的基础上，进一步提高产品质量，实现 生产成本最小基础上产品质量最优的目标． 根据上 述三个目标的收敛情况可以看出，本文采用的混合 算法对于模型的求解较为理想． 图 3 为优化计算得到的批量计划中一个较大轧 制单元( 136 块板坯) 内板坯宽度、厚度和硬度的变 化趋势． 从图中可以看出，板坯宽度递减变化呈“倒 梯形”，厚度递增，无反复跳跃，存在一定的反跳，硬 度递减，宽度、厚度和硬度未同时跳跃，符合轧制工 艺要求． 图 3 单个轧制单元内板坯宽度、厚度、硬度的变化 Fig． 3 Changes of slab width，thickness and hardness in a rolling unit 5 应用实例 本文根据某厂热轧生产线的实际生产数据进行 了多批次的热轧批量计划编制工作，并与现场采用 的人机结合编制方式进行了对比分析． 连铸区段的 多座连铸机均可以直接将连铸坯送达该轧线，且轧 线中的加热工序配有板坯库． 其中 4 组有代表性的 生产数据为: ( 1) 批次 1，250 块板坯，共有 13 种规 格( 规格变化较大) ; ( 2) 批次 2，156 块板坯，共有 8 种规格( 规格变化较大) ; ( 3) 批次 3，250 块板坯，共 有 7 种规格( 规格变化较小) ; ( 4) 批次 4，156 块板 坯，共有 4 种规格( 规格变化较小) ． 本文将所有板坯都编入批量计划，种群规模为 50，禁忌长度为 6，计算步数为 200，其结果与人机结 合方式结果的对比如表 1 所示，两种方式的计算结 果均是在假设加热工序为理想炉区( 不考虑炉群调 度) 下得到的． 表中的热送热装率是根据板坯传搁 时间和高温时温降速率计算得到入炉温度，再通过 板坯数量统计得到的． ·461·