连铸与热轧工序余材集成匹配模型与算法

D0I:10.13374.issn1001-053x.2012.10.006 第34卷第10期 北京科技大学学报 Vol.34 No.10 2012年10月 Journal of University of Science and Technology Beijing 0ct.2012 连铸与热轧工序余材集成匹配模型与算法 李海涛)✉李苏剑”芦永明》吴迪” 1)北京科技大学机械工程学院，北京100083 2)治金自动化研究设计院混合流程工业自动化系统及装备技术国家重点实验室，北京100071 ☒通信作者，E-mail:lihaitaojin@163.com 摘要针对钢铁企业连铸工序余材板坯及热轧工序余材钢卷对热轧生产合同的匹配问题，基于一体化的管理思想建立了 余材板坯、钢卷与合同集成匹配的多目标01非线性整数规划模型，在模型中引入板坯材质与合同要求钢种特征差异值矩阵 及钢卷钢种与合同要求钢种特征差异值矩阵，采用分段整数编码、基于启发式修复策略的改进遗传算法求解。最后，通过对 实际生产数据的仿真实验验证了所提模型和算法的有效性，为科学合理地匹配铸轧工序余材板坯、钢卷提供了有效的解决 方法 关键词连铸：热轧：存货管理：非线性规划：遗传算法 分类号T℉406.2 Integrative matching model and algorithm of inventory in continuous casting and hot rolling processes LI Hai-tao,LI Su-jian",LU Yong-ming?,WU Di 1)School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)National Key Laboratory of Hybrid Process Industrial Automation and Equipment Techniques,Automation Research and Design Institute of Metallurgi- cal Industry,Beijing 100071,China Corresponding author,E-mail:lihaitaojin@163.com ABSTRACT Aimed at the problem of matching open-order slabs and coils with hot rolling production orders in the steel industry,a multi-objective 0-nonlinear integer programming model for integrative matching of inventory in continuous casting and hot rolling processes was established on the basis of the integrative management idea.Two matrices were introduced in the model:one indicated the difference between slab material and steel grade required in orders,and the other reflected the difference between coil grade and steel grade required in orders.An improved genetic algorithm with the sub-integer encoding method and the heuristic repair strategy was proposed.Finally,the effectiveness of the proposed model and algorithm was verified by simulation based on actual production data. The results show that the integrative matching method can produce a significantly better and more scientific way for matching slabs and coils with hot rolling production orders. KEY WORDS continuous casting:hot rolling:inventory management:nonlinear programming:genetic algorithms 现代钢铁企业普遍采用高水平连续化的生产工 决库存造成的资金和场地占用问题，在编制合同计 艺形式和面向客户合同组织生产的管理方式，企业 划、作业计划之前，需要进行库存余材对合同的匹配 中的生产计划与调度问题具有规模大、目标多和约 工作) 束复杂等特征，因此对其进行建模和优化已成为国 胡琨元等网建立匹配总质量最大化和附加成 内外学者研究的热点.钢铁企业的生产计划与调度 本最小化的多目标成品匹配模型，用改进的PBL算 问题分为合同计划0、批量作业计划-)、作业调 法进行求解：孙树慧等回在钢卷与订单匹配中考虑 度和动态调度因，企业为提高及时交货能力、解 钢种的“以优充次”，以最大化钢卷匹配质量为目标 收稿日期：2011-10-10

第 34 卷 第 10 期 2012 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 10 Oct． 2012 连铸与热轧工序余材集成匹配模型与算法 李海涛1) ! 李苏剑1) 芦永明2) 吴 迪1) 1) 北京科技大学机械工程学院，北京 100083 2) 冶金自动化研究设计院混合流程工业自动化系统及装备技术国家重点实验室，北京 100071 !通信作者，E-mail: lihaitaojin@ 163． com 摘 要 针对钢铁企业连铸工序余材板坯及热轧工序余材钢卷对热轧生产合同的匹配问题，基于一体化的管理思想建立了 余材板坯、钢卷与合同集成匹配的多目标 0--1 非线性整数规划模型，在模型中引入板坯材质与合同要求钢种特征差异值矩阵 及钢卷钢种与合同要求钢种特征差异值矩阵． 采用分段整数编码、基于启发式修复策略的改进遗传算法求解． 最后，通过对 实际生产数据的仿真实验验证了所提模型和算法的有效性，为科学合理地匹配铸轧工序余材板坯、钢卷提供了有效的解决 方法． 关键词 连铸; 热轧; 存货管理; 非线性规划; 遗传算法 分类号 TF406. 2 Integrative matching model and algorithm of inventory in continuous casting and hot rolling processes LI Hai-tao 1) !，LI Su-jian1) ，LU Yong-ming2) ，WU Di 1) 1) School of Mechanical Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) National Key Laboratory of Hybrid Process Industrial Automation and Equipment Techniques，Automation Research and Design Institute of Metallurgi￾cal Industry，Beijing 100071，China !Corresponding author，E-mail: lihaitaojin@ 163． com ABSTRACT Aimed at the problem of matching open-order slabs and coils with hot rolling production orders in the steel industry，a multi-objective 0-1 nonlinear integer programming model for integrative matching of inventory in continuous casting and hot rolling processes was established on the basis of the integrative management idea． Two matrices were introduced in the model: one indicated the difference between slab material and steel grade required in orders，and the other reflected the difference between coil grade and steel grade required in orders． An improved genetic algorithm with the sub-integer encoding method and the heuristic repair strategy was proposed． Finally，the effectiveness of the proposed model and algorithm was verified by simulation based on actual production data． The results show that the integrative matching method can produce a significantly better and more scientific way for matching slabs and coils with hot rolling production orders． KEY WORDS continuous casting; hot rolling; inventory management; nonlinear programming; genetic algorithms 收稿日期: 2011--10--10 现代钢铁企业普遍采用高水平连续化的生产工 艺形式和面向客户合同组织生产的管理方式，企业 中的生产计划与调度问题具有规模大、目标多和约 束复杂等特征，因此对其进行建模和优化已成为国 内外学者研究的热点． 钢铁企业的生产计划与调度 问题分为合同计划［1］、批量作业计划［2--4］、作 业 调 度［5］和动态调度［6］． 企业为提高及时交货能力、解 决库存造成的资金和场地占用问题，在编制合同计 划、作业计划之前，需要进行库存余材对合同的匹配 工作［7］． 胡琨元等［8］建立匹配总质量最大化和附加成 本最小化的多目标成品匹配模型，用改进的 PBIL 算 法进行求解; 孙树慧等［9］在钢卷与订单匹配中考虑 钢种的“以优充次”，以最大化钢卷匹配质量为目标 DOI:10.13374/j.issn1001-053x.2012.10.006

·1198 北京科技大学学报 第34卷 建立数学模型，基于约束满足技术进行求解：卢克斌 有质量缺陷或其他问题时，在工艺条件允许的情况 等0将成品匹配与生产计划问题综合考虑，建立联 下，可通过降级改判将其轧制成钢种级别较低的成 合优化模型，采用分段整数编码的遗传算法进行求 品；对于钢卷，在合同允许的条件下，也可以考虑钢 解：张涛等如建立了合同的余材匹配与车间生产同 种“以优充次”匹配 时考虑的联合优化模型，设计了对非可行解具有启 假设某企业中所有板坯材质种类数为A,钢卷 发式修复策略的粒子群算法进行求解：田志波等☒ 的钢种种类数为B,合同要求的钢种种类数为N.定 采用基于交换和插入两种合成邻域结构的蚁群算法 义板坯材质与合同要求的钢卷钢种之间的特征值差 求解无委托板坯的匹配问题：白小振等)建立了无 异矩阵PS=（psan）AxN,psn表征材质为a的板坯与 委托板坯对合同的多目标匹配模型，并采用遗传算 合同要求的钢种为n的钢卷之间在物理性质和化学 法求解 性质上的差异，为在匹配工作中考虑材质为a的板 上述文献了-13]虽然取得了一定成果，但存在 坯是否能匹配给要求钢种为n的合同作参考，psm 三个方面的不足：(1)文献7-11]仅以匹配总质量 越大，表征材质为α的板坯与钢种为n的钢卷差异 最大化、附加成本最小化对成品进行匹配，而实际的 越大，越不容易进行匹配，反之则越容易匹配：同理， 匹配工作除了考虑匹配总质量，附加成本还需考虑 定义余材钢卷与合同要求的钢卷之间的特征差异值 合同的优先级和合同的完整匹配数等因素，才能提 矩阵PC=（pcn）BxN'PCin表示钢种为b的钢卷与合 高匹配结果的质量：(2)文献2-13]在对半成品余 同要求的钢种n之间的差异.psm与pcn中各元素的 材板坯匹配的研究中虽然考虑的目标较为全面，但 取值由企业质量设计部门提供，根据钢种之间的物 在约束中仅从匹配模式和余材匹配量上进行限制， 理性质、化学成分和生产工艺参数的相似程度确定， 没有考虑轧线侧压量和板坯材质等工艺约束：(3) 相似程度越大，则其值越小 上述研究一)主要停留在独立研究成品或半成品对 在定义钢种特征差异值矩阵PS和PC的基础 合同的匹配问题，不能从整体上把握板坯库和钢卷 上，定义钢种匹配费用矩阵CS=(csm）Axx和CC= 库的库存水平以及权衡各类余材的优先级.尽管传 (cCm）Bxw用以表征单位质量某材质的余材匹配给 统的钢卷匹配和板坯匹配两项工作是分步进行的， 合同的费用：csm表示单位质量材质为a的板坯匹配 而在实际生产中，决策者要对二者进行反复协调，保 给要求钢种为n的合同所需的匹配费用；ccm表示 证优先级高的板坯、钢卷与合同之间的匹配率，才能 单位质量钢种为b的钢卷匹配给要求钢种为的合 使得各项匹配指标最优化. 同所需的匹配费用. 针对以上不足，本文提出将连铸工序余材板坯 (2)规格匹配.板坯、钢卷与合同进行匹配，需 与热轧工序余材钢卷进行联合优化匹配的方法.根 满足合同对产品厚度和宽度的要求，且不低于合同 据实际的匹配条件和工艺约束，以余材匹配量最大 要求的最小单元质量，对大于最大单元质量的余材 化和匹配费用最小化为主要目标，并考虑了各类余 必须进行切割处理，从而产生包括两部分的切损 材的优先级、合同优先级和合同完整性，建立了多目 费用 标匹配模型；结合问题特点设计了基于分段整数编 (3)合同优先级YO.主要由集批情况、流向、 码和启发式修复策略的改进遗传算法；最后通过仿 材料申请宽裕量、状态、类别和交货期等因素决定. 真对比实验验证了模型和算法的有效性和可行性. (4)板坯优先级YS,与钢卷优先级YC.·确定 1 铸轧工序余材集成匹配问题描述及数学 板坯、钢卷的匹配优先级时，需考虑其在库时间和库 位等因素，同时需兼顾板坯库和钢卷库的库存状态 模型 对在库时间长，且其所占库位为紧张资源的板坯和 1.1铸轧工序余材集成匹配问题描述 钢卷，设定较高的优先级，反之则可以设定其优先级 热轧生产合同匹配时所考虑的基本因素主要包 为较低数值. 括钢种、宽度、厚度和单位质量四个特征值.本文依 (⑤)合同完整性.匹配给合同的余材满足合同 次从钢种、规格、余材板坯和钢卷的优先级、合同优 的总量要求.若匹配给合同的余材板坯和钢卷的总 先级以及合同完整性五个方面对库存匹配问题进行 量在合同需求量的下限和上限之间，则该合同为可 分析. 完整合同：若匹配给合同的板坯和钢卷总量低于合 (1)钢种匹配.对于同一材质的板坯，通过改 同需求量下限，则此为合同匹配中的不完整合同 变轧制工艺参数，可轧制成不同钢种的成品，当板坯 (6)综上所述，对铸轧工序余材集成匹配问题

北 京 科 技 大 学 学 报 第 34 卷 建立数学模型，基于约束满足技术进行求解; 卢克斌 等［10］将成品匹配与生产计划问题综合考虑，建立联 合优化模型，采用分段整数编码的遗传算法进行求 解; 张涛等［11］建立了合同的余材匹配与车间生产同 时考虑的联合优化模型，设计了对非可行解具有启 发式修复策略的粒子群算法进行求解; 田志波等［12］ 采用基于交换和插入两种合成邻域结构的蚁群算法 求解无委托板坯的匹配问题; 白小振等［13］建立了无 委托板坯对合同的多目标匹配模型，并采用遗传算 法求解． 上述文献［7--13］虽然取得了一定成果，但存在 三个方面的不足: ( 1) 文献［7--11］仅以匹配总质量 最大化、附加成本最小化对成品进行匹配，而实际的 匹配工作除了考虑匹配总质量，附加成本还需考虑 合同的优先级和合同的完整匹配数等因素，才能提 高匹配结果的质量; ( 2) 文献［12--13］在对半成品余 材板坯匹配的研究中虽然考虑的目标较为全面，但 在约束中仅从匹配模式和余材匹配量上进行限制， 没有考虑轧线侧压量和板坯材质等工艺约束; ( 3) 上述研究［7--13］主要停留在独立研究成品或半成品对 合同的匹配问题，不能从整体上把握板坯库和钢卷 库的库存水平以及权衡各类余材的优先级． 尽管传 统的钢卷匹配和板坯匹配两项工作是分步进行的， 而在实际生产中，决策者要对二者进行反复协调，保 证优先级高的板坯、钢卷与合同之间的匹配率，才能 使得各项匹配指标最优化． 针对以上不足，本文提出将连铸工序余材板坯 与热轧工序余材钢卷进行联合优化匹配的方法． 根 据实际的匹配条件和工艺约束，以余材匹配量最大 化和匹配费用最小化为主要目标，并考虑了各类余 材的优先级、合同优先级和合同完整性，建立了多目 标匹配模型; 结合问题特点设计了基于分段整数编 码和启发式修复策略的改进遗传算法; 最后通过仿 真对比实验验证了模型和算法的有效性和可行性． 1 铸轧工序余材集成匹配问题描述及数学 模型 1. 1 铸轧工序余材集成匹配问题描述 热轧生产合同匹配时所考虑的基本因素主要包 括钢种、宽度、厚度和单位质量四个特征值． 本文依 次从钢种、规格、余材板坯和钢卷的优先级、合同优 先级以及合同完整性五个方面对库存匹配问题进行 分析． ( 1) 钢种匹配． 对于同一材质的板坯，通过改 变轧制工艺参数，可轧制成不同钢种的成品，当板坯 有质量缺陷或其他问题时，在工艺条件允许的情况 下，可通过降级改判将其轧制成钢种级别较低的成 品; 对于钢卷，在合同允许的条件下，也可以考虑钢 种“以优充次”匹配． 假设某企业中所有板坯材质种类数为 A，钢卷 的钢种种类数为 B，合同要求的钢种种类数为 N． 定 义板坯材质与合同要求的钢卷钢种之间的特征值差 异矩阵 PS = ( psan ) A × N，psan表征材质为 a 的板坯与 合同要求的钢种为 n 的钢卷之间在物理性质和化学 性质上的差异，为在匹配工作中考虑材质为 a 的板 坯是否能匹配给要求钢种为 n 的合同作参考，psan 越大，表征材质为 a 的板坯与钢种为 n 的钢卷差异 越大，越不容易进行匹配，反之则越容易匹配; 同理， 定义余材钢卷与合同要求的钢卷之间的特征差异值 矩阵 PC = ( pcbn ) B × N，pcbn表示钢种为 b 的钢卷与合 同要求的钢种 n 之间的差异． psan与pcbn中各元素的 取值由企业质量设计部门提供，根据钢种之间的物 理性质、化学成分和生产工艺参数的相似程度确定， 相似程度越大，则其值越小． 在定义钢种特征差异值矩阵 PS 和 PC 的基础 上，定义钢种匹配费用矩阵 CS = ( csan ) A × N和 CC = ( ccbn ) B × N用以表征单位质量某材质的余材匹配给 合同的费用: csan表示单位质量材质为 a 的板坯匹配 给要求钢种为 n 的合同所需的匹配费用; ccbn表示 单位质量钢种为 b 的钢卷匹配给要求钢种为 n 的合 同所需的匹配费用． ( 2) 规格匹配． 板坯、钢卷与合同进行匹配，需 满足合同对产品厚度和宽度的要求，且不低于合同 要求的最小单元质量，对大于最大单元质量的余材 必须进行切割处理，从而产生包括两部分的切损 费用． ( 3) 合同优先级YOi ． 主要由集批情况、流向、 材料申请宽裕量、状态、类别和交货期等因素决定． ( 4) 板坯优先级YSs 与钢卷优先级YCc． 确定 板坯、钢卷的匹配优先级时，需考虑其在库时间和库 位等因素，同时需兼顾板坯库和钢卷库的库存状态． 对在库时间长，且其所占库位为紧张资源的板坯和 钢卷，设定较高的优先级，反之则可以设定其优先级 为较低数值． ( 5) 合同完整性． 匹配给合同的余材满足合同 的总量要求． 若匹配给合同的余材板坯和钢卷的总 量在合同需求量的下限和上限之间，则该合同为可 完整合同; 若匹配给合同的板坯和钢卷总量低于合 同需求量下限，则此为合同匹配中的不完整合同． ( 6) 综上所述，对铸轧工序余材集成匹配问题 ·1198·

第10期 李海涛等：连铸与热轧工序余材集成匹配模型与算法 ·1199· 概括如下：假定在给定的一个合同计划期内，存在S G0:的合同所需匹配费用；WC.,钢卷c的宽度；TC, 块余材板坯、C个余材钢卷和I份合同，对任意余材 钢卷c的厚度；P。,切削钢卷产生的固定切削费用； 板坯s或钢卷c匹配给合同i,需满足如下约束：(1) Y。,切削单位质量的钢卷c产生的损失费用；YC。,合 任意一余材板坯或钢卷至多匹配一份合同：(2)合 同c的优先级. 同；可匹配多个钢卷或板坯，但不能超过合同要求 (4)权重系数.P1,规格和钢种匹配费用权重 的最大需求量：(3)板坯和钢卷在合同及工艺条件 系数：P2,未被匹配板坯和钢卷的总惩罚费用权重系 允许的范围内，可进行钢种“以优充次”匹配：(4)板 数P3,合同的优先级奖励费用权重系数；P4,己匹配 坯轧制成合同要求宽度和厚度的钢卷需满足轧线侧 余材的优先级奖励费用权重系数；Ps,未完成合同的 压量的工艺约束：(5)钢卷匹配需满足合同的宽度 欠量惩罚及未完成合同惩罚费用权重系数. 和厚度要求：(6)要求板坯、钢卷的单元质量不小于 (5)决策变量 合同要求的最小单元质量.优化时有如下目标：(1) 1 若板坯s匹配给合同i, 最小化库存余材与合同要求的规格和钢种匹配费 xw=0 否则， 用：(2)最小化钢卷及板坯未被匹配的总惩罚费用： i∈{1,2，…，I},s∈{1,2，…，S}; (3)最大化以匹配合同优先级：(4)最大化己匹配库 若钢卷c匹配给合同i, 存余材优先级：(5)最小化未完成合同的欠量总惩 y=0 否则， 罚费用. i∈{1,2，…，}，c∈{1,2，…，C} 1.2符号定义 1.3铸轧工序余材集成匹配数学模型 (1)与合同相关的符号说明.1，合同数：i∈{1， 2,…,I},合同编号：Qx,合同i要求的产品最大总 mmf=p(A名Ex+合E小+ 质量：Q,合同i可接受的需求下限；QUm,合同i 要求的最小单元质量；QU,合同i要求的最大单 三-名+2 1-各川- 元质量；G0,合同i要求的钢种代码；WO,合同i要 求的产品宽度：TO,合同i要求的产品厚度；G,合 p(A0+A0)- 同i要求的产品宽度公差范围：，合同i要求的产 p(三名s+名名C)+ 品厚度公差范围；s,合同i对与之匹配板坯的材质 要求；rC:,合同i对与之匹配钢卷的钢种的差异值要 含a,la,+4 unFni). Ps (1) 求；q:,合同i的单位欠量惩罚费用：d:,合同i的未完 Subject to 整匹配惩罚费用；YO,合同i的优先级. (2)与板坯相关的符号说明.S,余材板坯数； x+ Q.y≤Q,ie{1,2,…,l; s∈{1,2，…，S},余材板坯的编号；Q,余材板坯s的 (2) 质量；MS,板坯s的材质代码；PS,板坯材质与合同 要求钢种的特征差异值矩阵；PS(MS,G0),板坯s xa≤1，s∈{1,2，…，S}: (3) 与合同i要求钢种的特征差异值：CS,板坯材质与钢 种的匹配费用矩阵：CS(MS,G0:),单位质量材质为 cl2 (4) MS,的板坯s轧制成钢种为GO:的钢卷所需匹配费 0≤PS(MS,G0)xa≤rs, 用：WS,板坯s的宽度；△d,轧线的侧压量；p,切削 i∈{1,2，…，I},s∈{1,2，…，S}; (5) 板坯产生的固定费用；y,切削单位质量的板坯s产 0≤PC(GC.,GO;)ye≤rc 生的损失费用；YS,板坯s的优先级. ie{1,2,,I},c∈{1,2，…，C}: (6) (3)与钢卷相关的符号说明.C,余材钢卷数； IT0,-TClyie≤t:, c∈{1,2，…，C},余材钢卷的编号；Q,余材钢卷c i∈{1,2，…，I},ce{1,2,…,C}: (7) 的质量；GC,钢卷c的钢种代码：PC,钢卷钢种与合 0≤(WS,-W0,)x≤△d, 同要求钢种的特征差异值矩阵；PC(GC,GO:),钢 ie{1,2,,I},s∈{1,2，，S}: (8) 卷钢种与合同要求钢种的特征差异值：CC,钢卷钢 IWO,-WC.ly≤o:, 种与合同要求钢种的匹配费用矩阵；CC(GC, ie{1,2,,l},ce{1,2,…,C}: (9) GO),单位质量钢种为GC。的钢卷c匹配给钢种为 Q.x-QUin≥0

第 10 期 李海涛等: 连铸与热轧工序余材集成匹配模型与算法 概括如下: 假定在给定的一个合同计划期内，存在 S 块余材板坯、C 个余材钢卷和 I 份合同，对任意余材 板坯 s 或钢卷 c 匹配给合同 i，需满足如下约束: ( 1) 任意一余材板坯或钢卷至多匹配一份合同; ( 2) 合 同 i 可匹配多个钢卷或板坯，但不能超过合同要求 的最大需求量; ( 3) 板坯和钢卷在合同及工艺条件 允许的范围内，可进行钢种“以优充次”匹配; ( 4) 板 坯轧制成合同要求宽度和厚度的钢卷需满足轧线侧 压量的工艺约束; ( 5) 钢卷匹配需满足合同的宽度 和厚度要求; ( 6) 要求板坯、钢卷的单元质量不小于 合同要求的最小单元质量． 优化时有如下目标: ( 1) 最小化库存余材与合同要求的规格和钢种匹配费 用; ( 2) 最小化钢卷及板坯未被匹配的总惩罚费用; ( 3) 最大化以匹配合同优先级; ( 4) 最大化已匹配库 存余材优先级; ( 5) 最小化未完成合同的欠量总惩 罚费用． 1. 2 符号定义 ( 1) 与合同相关的符号说明． I，合同数; i∈{ 1， 2，…，I} ，合同编号; Qi max，合同 i 要求的产品最大总 质量; Qi min，合同 i 可接受的需求下限; QUi min，合同 i 要求的最小单元质量; QUi max，合同 i 要求的最大单 元质量; GOi，合同 i 要求的钢种代码; WOi，合同 i 要 求的产品宽度; TOi，合同 i 要求的产品厚度; wi，合 同 i 要求的产品宽度公差范围; ti，合同 i 要求的产 品厚度公差范围; rsi，合同 i 对与之匹配板坯的材质 要求; rci，合同 i 对与之匹配钢卷的钢种的差异值要 求; qi，合同 i 的单位欠量惩罚费用; di，合同 i 的未完 整匹配惩罚费用; YOi，合同 i 的优先级． ( 2) 与板坯相关的符号说明． S，余材板坯数; s∈{ 1，2，…，S} ，余材板坯的编号; Qs，余材板坯 s 的 质量; MSs，板坯 s 的材质代码; PS，板坯材质与合同 要求钢种的特征差异值矩阵; PS( MSs，GOi ) ，板坯 s 与合同 i 要求钢种的特征差异值; CS，板坯材质与钢 种的匹配费用矩阵; CS( MSs，GOi ) ，单位质量材质为 MSs 的板坯 s 轧制成钢种为GOi 的钢卷所需匹配费 用; WSs，板坯 s 的宽度; Δd，轧线的侧压量; φs，切削 板坯产生的固定费用; γs，切削单位质量的板坯 s 产 生的损失费用; YSs，板坯 s 的优先级． ( 3) 与钢卷相关的符号说明． C，余材钢卷数; c∈{ 1，2，…，C} ，余材钢卷的编号; Qc，余材钢卷 c 的质量; GCc，钢卷 c 的钢种代码; PC，钢卷钢种与合 同要求钢种的特征差异值矩阵; PC( GCc，GOi ) ，钢 卷钢种与合同要求钢种的特征差异值; CC，钢卷钢 种与 合 同 要 求 钢 种 的 匹 配 费 用 矩 阵; CC ( GCc， GOi ) ，单位质量钢种为GCc 的钢卷 c 匹配给钢种为 GOi 的合同所需匹配费用; WCc，钢卷 c 的宽度; TCc， 钢卷 c 的厚度; φc，切削钢卷产生的固定切削费用; γc，切削单位质量的钢卷 c 产生的损失费用; YCc，合 同 c 的优先级． ( 4) 权重系数． ρ1，规格和钢种匹配费用权重 系数; ρ2，未被匹配板坯和钢卷的总惩罚费用权重系 数; ρ3，合同的优先级奖励费用权重系数; ρ4，已匹配 余材的优先级奖励费用权重系数; ρ5，未完成合同的 欠量惩罚及未完成合同惩罚费用权重系数． ( 5) 决策变量． xis = 1 若板坯 s 匹配给合同 i， {0 否则， i∈{ 1，2，…，I} ，s∈{ 1，2，…，S} ; yic = 1 若钢卷 c 匹配给合同 i， {0 否则， i∈{ 1，2，…，I} ，c∈{ 1，2，…，C} ． 1. 3 铸轧工序余材集成匹配数学模型 min f = ρ1 ( ∑ I i = 1 ∑ S s = 1 Eisxis + ∑ I i = 1 ∑ C c = 1 Eicyic ) + ρ2 [ ∑ S s = ( 1 1 － ∑ I i = 1 xis ) + ∑ C c = ( 1 1 － ∑ I i = 1 yic ) ] － ρ3 ( ∑ I i = 1 ∑ S s = 1 YOixis + ∑ I i = 1 ∑ C c = 1 YOiyic ) － ρ4 ( ∑ S s = 1 ∑ I i = 1 YSsxis + ∑ C c = 1 ∑ I i = 1 YCcyic ) + ρ5 ∑ N i = 1 ( qi Lacki + di unFinishi ) ． ( 1) Subject to ∑ S s = 1 Qsxis + ∑ C c = 1 Qcyic≤Qi max，i∈{ 1，2，…，I} ; ( 2) ∑ I i = 1 xis≤1，s∈{ 1，2，…，S} ; ( 3) ∑ I i = 1 yic≤1，c∈{ 1，2，…，C} ; ( 4) 0≤PS( MSs，GOi ) xis≤rsi， i∈{ 1，2，…，I} ，s∈{ 1，2，…，S} ; ( 5) 0≤PC( GCc，GOi ) yic≤rci， i∈{ 1，2，…，I} ，c∈{ 1，2，…，C} ; ( 6) | TOi － TCc | yic≤ti， i∈{ 1，2，…，I} ，c∈{ 1，2，…，C} ; ( 7) 0≤( WSs － WOi ) xis≤Δd， i∈{ 1，2，…，I} ，s∈{ 1，2，…，S} ; ( 8) | WOi － WCc | yic≤wi， i∈{ 1，2，…，I} ，c∈{ 1，2，…，C} ; ( 9) Qsxis － QUi min≥0， ·1199·

·1200· 北京科技大学学报 第34卷 i∈{1,2，…，}，s∈{1,2，，S}; (10) 效性. Q.ye-QU≥0， 针对己经建立的具有多约束的非线性目标的 i∈{1,2，…，I},c∈{1,2，…，C}. (11) 0一1整数规划模型，本文提出一种计算复杂性较低、 目标函数(1)中，E为板坯s匹配给合同i的切 求解性能较好的改进遗传算法，并设计了对非可行 损费用及钢种匹配费用， 解具有启发式修复功能的求解策略.改进遗传算法 Ei= 流程见图1. 「y.(Q.-Q0）+重，+QUCS(aMS,c0,）Q.-QUm>0, 确定实际问题参数 1Q.CS(MS,,GO,) Q.-QU≤0. 出约束5-(11)产生 E为钢卷c匹配给合同i的切损费用及钢种匹配 每一个余材的可选合同集合 1 费用， 随机尘成初始种群 Eie= 「y.(Q.-QUmn）+重.+QUCC(GCe,G0,）Q.-QUx>0, 种群中个体 通过贪心策略对 满见约束(2)？ 种群中个体进行修复 1Q.CC(GC.,GO,) Q.-QUnx≤0. 计算种昨中个体适应度 Lack, 1 mr{Q-(言x.+0o}, 满足停止条件？ >算法结束 N unFinish,= 按照轮盘赌规则选择 个体进行交义操作 有 0 Q-（0+0x≤0. 以概率对个体进行变异操作 1 1否则 变异后产生的 对不清足约束的 目标函数(1)中第一项为板坯和钢卷规格和钢 新个体满足釣束？ 个体进行修复 种总匹配费用，第二项为未被匹配板坯和钢卷的总 惩罚费用，第三项为己匹配合同的优先级奖励费用， 图1改进遗传算法流程图 第四项为己匹配余材的优先级奖励费用，第五项为 Fig.1 Flow chart of the improved GA algorithm 未完成合同的欠量惩罚及未完成合同惩罚费用；约 改进遗传算法的详细设计如下. 束(2)表示匹配给生产合同的钢卷与板坯质量之和 (1)编码.为满足约束条件(3)和(4)，采用分 不超过合同要求的最大总质量：约束(3)表示每块 段整数编码方式，把染色体按照板坯和钢卷分成两 无委托板坯至多匹配给一个合同：约束(4)表示一 段，前段有S个基因位，后段有C个基因位，即染色 个钢卷至多匹配给一个合同：约束(5)表示与板坯s 体Chrom={s1,s2,…,sslc1,c2,…,cc},共计S+C 匹配的合同所要求的钢种要在板坯s可轧制钢种的 个基因位，每个基因位代表一个余材.s,和c。分别 集合范围内；约束(6)表示钢卷与合同的钢种匹配 表示板坯s和钢卷c的匹配情况： 要在合同要求可接受的钢种匹配范围内；约束(7) ri 板坯s匹配给合同i, 表示钢卷的厚度要在合同要求的公差范围内；约束 5,=0没有合同与板坯s匹配： (8)表示生产工艺约束，合同要求的宽度与板坯的 钢卷c匹配给合同i, 宽度要满足轧线的侧压量限制要求：约束(9)表示 =0没有合同与钢卷c优海 钢卷的宽度要在合同要求的宽度公差范围内：约束 (2)初始种群生成.为缩小解的搜索空间，首 (10)和(11)表示与合同匹配的余材的质量须不小 先根据约束条件(5)~(11)生成每个余材可匹配的 于合同要求的最小单元质量. 合同集合OM{}(表示余材j可匹配的合同集合，若 2算法描述 不能匹配给任何合同，则为空集).在每个基因位 上，从其对应的可匹配合同集合中随机选择一个合 遗传算法在解决旅行商问题4-、流水作业调 同（当可匹配合同集合为空集时，产生的合同号为 度问题、柔性作业车间调度问题切和包装问 0,表示没有合适的合同与该余材进行匹配).随机 题图等都有很好的效果，对于解决多背包问 生成Popsize个满足约束(3)~(11)的初始可行解. 题90也比较适合，足见其解决组合优化问题的有 (3)初始种群修复策略.将初始解代入约束条

北 京 科 技 大 学 学 报 第 34 卷 i∈{ 1，2，…，I} ，s∈{ 1，2，…，S} ; ( 10) Qcyic － QUi min≥0， i∈{ 1，2，…，I} ，c∈{ 1，2，…，C} ． ( 11) 目标函数( 1) 中，Eis为板坯 s 匹配给合同 i 的切 损费用及钢种匹配费用， Eis = γs ( Qs － QUi max ) + Φs + QUi maxCS( MSs，GOi ) Qs － QUi max ＞ 0， QsCS( MSs，GOi ) Qs － QUi { max≤0． Eic为钢卷 c 匹配给合同 i 的切损费用及钢种匹配 费用， Eic = γc( Qc － QUi max ) + Φc + QUi maxCC( GCc，GOi ) Qc － QUi max ＞ 0， QcCC( GCc，GOi ) Qc － QUi { max≤0． Lacki = max { Qi min － ( ∑ S s = 1 Qsxis + ∑ C c = 1 Qcyic ) ，0 } ， unFinishi = 0 Qi min － ( ∑ S s = 1 Qsxis + ∑ C c = 1 Qcyic ) ≤ 0， 1 否则 { ． 目标函数( 1) 中第一项为板坯和钢卷规格和钢 种总匹配费用，第二项为未被匹配板坯和钢卷的总 惩罚费用，第三项为已匹配合同的优先级奖励费用， 第四项为已匹配余材的优先级奖励费用，第五项为 未完成合同的欠量惩罚及未完成合同惩罚费用; 约 束( 2) 表示匹配给生产合同的钢卷与板坯质量之和 不超过合同要求的最大总质量; 约束( 3) 表示每块 无委托板坯至多匹配给一个合同; 约束( 4) 表示一 个钢卷至多匹配给一个合同; 约束( 5) 表示与板坯 s 匹配的合同所要求的钢种要在板坯 s 可轧制钢种的 集合范围内; 约束( 6) 表示钢卷与合同的钢种匹配 要在合同要求可接受的钢种匹配范围内; 约束( 7) 表示钢卷的厚度要在合同要求的公差范围内; 约束 ( 8) 表示生产工艺约束，合同要求的宽度与板坯的 宽度要满足轧线的侧压量限制要求; 约束( 9) 表示 钢卷的宽度要在合同要求的宽度公差范围内; 约束 ( 10) 和( 11) 表示与合同匹配的余材的质量须不小 于合同要求的最小单元质量． 2 算法描述 遗传算法在解决旅行商问题［14--15］、流水作业调 度问题［16］、柔性作业车间调度问题［17］ 和 包 装 问 题［18］等都有很好的效果，对 于 解 决 多 背 包 问 题［19--20］也比较适合，足见其解决组合优化问题的有 效性． 针对已经建立的具有多约束的非线性目标的 0--1 整数规划模型，本文提出一种计算复杂性较低、 求解性能较好的改进遗传算法，并设计了对非可行 解具有启发式修复功能的求解策略． 改进遗传算法 流程见图 1． 图 1 改进遗传算法流程图 Fig． 1 Flow chart of the improved GA algorithm 改进遗传算法的详细设计如下． ( 1) 编码． 为满足约束条件( 3) 和( 4) ，采用分 段整数编码方式，把染色体按照板坯和钢卷分成两 段，前段有 S 个基因位，后段有 C 个基因位，即染色 体 Chrom = { s1，s2，…，sS | c1，c2，…，cC } ，共计 S + C 个基因位，每个基因位代表一个余材． ss 和 cc 分别 表示板坯 s 和钢卷 c 的匹配情况: ss = i 板坯 s 匹配给合同 i， {0 没有合同与板坯 s 匹配; cc = i 钢卷 c 匹配给合同 i， {0 没有合同与钢卷 c 匹配． ( 2) 初始种群生成． 为缩小解的搜索空间，首 先根据约束条件( 5) ～ ( 11) 生成每个余材可匹配的 合同集合 OM{ j} ( 表示余材 j 可匹配的合同集合，若 不能匹配给任何合同，则为空集) ． 在每个基因位 上，从其对应的可匹配合同集合中随机选择一个合 同( 当可匹配合同集合为空集时，产生的合同号为 0，表示没有合适的合同与该余材进行匹配) ． 随机 生成 Popsize 个满足约束( 3) ～ ( 11) 的初始可行解． ( 3) 初始种群修复策略． 将初始解代入约束条 ·1200·

第10期 李海涛等：连铸与热轧工序余材集成匹配模型与算法 ·1201· 件(2)，若匹配给某一合同i的余材不满足该约束， 规模数据对集成匹配模型的有效性进行实验，将改 则对该初始解进行修复，参见步骤(8)，最终得到满 进遗传算法集成匹配方法与改进遗传算法常规匹配 足约束条件(2)~(11)的初始种群 方法和启发式常规匹配方法进行对比，验证基于 (4)计算适应度.直接将目标函数作为适应度 改进遗传算法的铸轧工序余材集成匹配模型解决实 函数 际问题的能力；二是算法的有效性实验，即通过人工 (5)选择操作.采用轮盘赌选择方法，即在原 产生的小规模数据检验算法解的品质.为验证改进 种群和经过交叉、变异和修复产生的新种群中，选择 遗传算法的品质，使用LOG公司的约束规划标准 Popsize个个体作为下一代种群. 软件CP求解不同规模数据，并将CP产生的结果与 (6)交叉操作阿.只对可匹配钢卷和板坯上 改进遗传算法产生的结果相比较. 的基因进行对应交叉操作.为了有效地保持群体的 3.1模型的有效性实验 多样性，使算法具有较强的搜索能力，采用均匀交叉 为了验证集成匹配模型的有效性，以从某企业 算子.设1和2为两个待交叉的父个体，然后随机 生产现场采集的余材板坯、钢卷及热轧生产合同原 地产生与父个体等长的两个0-一H掩码Y和Y2(掩码 始数据进行仿真，并与工厂现行的启发式常规匹配 中的0表示从父个体I中提取基因值，1表示从父 以及改进遗传算法常规匹配进行对比. 个体2中提取基因值)，利用掩码形成两个新个体 启发式常规匹配步骤四：(1)将钢卷和合同按 X和X2,如图2所示 照优先级排序；(2)将钢卷与合同进行逐一匹配并 父个体 掩码 子个体 更新合同匹配数据：(3)将余材板坯与更新后仍有 1=2445216 Y=0101101 X=2644612 欠量的合同进行匹配，即首先将余材板坯按同钢种 1,=3624632 Y2=1110100 X,=3625616 宽度排序，同宽度板坯按质量由大到小排序，然后将 生产合同按宽度排序，同宽度合同按欠量从小到大 图2交叉操作举例 排序，最后将板坯与合同进行匹配. Fig.2 Example of the crossover operator 改进遗传算法常规匹配：基于改进遗传算法，首 (7)变异操作.对基因位上为0的元素进行变 先只把钢卷和合同通过1.3中的匹配模型进行匹 异，变异范围为该基因位所对应的可匹配合同集，随 配，输出匹配结果，更新合同数据，再将板坯和仍有 机选择可匹配合同集中的一个作为新的基因值 欠量的合同通过1.3中的匹配模型进行匹配 (8)个体修复策略.由于执行交叉和变异操作 改进遗传算法集成匹配：基于改进遗传算法，把 后产生的个体仍然满足约束条件(3)~(11)，因此 钢卷、板坯和合同通过1.3中的集成匹配模型进行 不可行解须依据约束条件(2)进行修复，采用贪心 匹配 策略修复.步骤为：①计算大于合同需求的余材数 采用matlab7.0编程，程序运行的硬件环境为： 量M:②将个体对应的合同方案产生的超过合同中 3CPUM370,2.40GHz,内存2G.参数设置：热轧工 子合同数量约束中的余材，按照质量升序排列：③依 序轧线侧压量为300mm,种群规模Popsize=20,最 次减去质量最小的M个库存余材 大迭代次数MaxGen=200.根据现场实际需要，预 (9)终止条件.算法运行到设定的最大迭代次 设目标函数权重系数p1p2:p3p4ps=3:1:2:1:3, 数时终止 将不同数据规模下合同与余材进行匹配.采用从实 际生产过程中抽取的覆盖30个钢种的105个热轧 3 数值实验 生产合同、384块板坯余材和309个钢卷余材数据 本文的数值实验分为两部分：一是采用实际大 见表1. 表1热轧生产合同、板坯余材和钢卷余材统计数据 Table 1 Statistic data of hot rolling production orders,open-order slabs and open-order coils 类别 原始合同 原始板坯 原始钢卷 可匹配合同 可匹配板坯 可匹配钢卷 数量 105 384 309 98 312 198 质量A 19750.0 10790.4 8384.9 19110.0 8924.2 5360.3 在实际生产中，难以对匹配方法的优劣做出精 匹配率以及合同完整性等方面对匹配结果进行评 确的评价，本文从匹配时间、不同等级余材和合同的 价.库存余材与合同匹配结果分别见表2和表3

第 10 期 李海涛等: 连铸与热轧工序余材集成匹配模型与算法 件( 2) ，若匹配给某一合同 i 的余材不满足该约束， 则对该初始解进行修复，参见步骤( 8) ，最终得到满 足约束条件( 2) ～ ( 11) 的初始种群． ( 4) 计算适应度． 直接将目标函数作为适应度 函数． ( 5) 选择操作． 采用轮盘赌选择方法，即在原 种群和经过交叉、变异和修复产生的新种群中，选择 Popsize 个个体作为下一代种群． ( 6) 交叉操作［19］． 只对可匹配钢卷和板坯上 的基因进行对应交叉操作． 为了有效地保持群体的 多样性，使算法具有较强的搜索能力，采用均匀交叉 算子． 设 I1和 I2为两个待交叉的父个体，然后随机 地产生与父个体等长的两个 0--1 掩码 Y1和 Y2 ( 掩码 中的 0 表示从父个体 I1中提取基因值，1 表示从父 个体 I2 中提取基因值) ，利用掩码形成两个新个体 X1和 X2，如图 2 所示． 图 2 交叉操作举例 Fig． 2 Example of the crossover operator ( 7) 变异操作． 对基因位上为 0 的元素进行变 异，变异范围为该基因位所对应的可匹配合同集，随 机选择可匹配合同集中的一个作为新的基因值． ( 8) 个体修复策略． 由于执行交叉和变异操作 后产生的个体仍然满足约束条件( 3) ～ ( 11) ，因此 不可行解须依据约束条件( 2) 进行修复，采用贪心 策略修复． 步骤为: ①计算大于合同需求的余材数 量 M; ②将个体对应的合同方案产生的超过合同中 子合同数量约束中的余材，按照质量升序排列; ③依 次减去质量最小的 M 个库存余材． ( 9) 终止条件． 算法运行到设定的最大迭代次 数时终止． 3 数值实验 本文的数值实验分为两部分: 一是采用实际大 规模数据对集成匹配模型的有效性进行实验，将改 进遗传算法集成匹配方法与改进遗传算法常规匹配 方法和启发式常规匹配方法［21］进行对比，验证基于 改进遗传算法的铸轧工序余材集成匹配模型解决实 际问题的能力; 二是算法的有效性实验，即通过人工 产生的小规模数据检验算法解的品质． 为验证改进 遗传算法的品质，使用 ILOG 公司的约束规划标准 软件 CP 求解不同规模数据，并将 CP 产生的结果与 改进遗传算法产生的结果相比较． 3. 1 模型的有效性实验 为了验证集成匹配模型的有效性，以从某企业 生产现场采集的余材板坯、钢卷及热轧生产合同原 始数据进行仿真，并与工厂现行的启发式常规匹配 以及改进遗传算法常规匹配进行对比． 启发式常规匹配步骤［21］: ( 1) 将钢卷和合同按 照优先级排序; ( 2) 将钢卷与合同进行逐一匹配并 更新合同匹配数据; ( 3) 将余材板坯与更新后仍有 欠量的合同进行匹配，即首先将余材板坯按同钢种 宽度排序，同宽度板坯按质量由大到小排序，然后将 生产合同按宽度排序，同宽度合同按欠量从小到大 排序，最后将板坯与合同进行匹配． 改进遗传算法常规匹配: 基于改进遗传算法，首 先只把钢卷和合同通过 1. 3 中的匹配模型进行匹 配，输出匹配结果，更新合同数据，再将板坯和仍有 欠量的合同通过 1. 3 中的匹配模型进行匹配． 改进遗传算法集成匹配: 基于改进遗传算法，把 钢卷、板坯和合同通过 1. 3 中的集成匹配模型进行 匹配． 采用 matlab7. 0 编程，程序运行的硬件环境为: i3 CPU M370，2. 40 GHz，内存2 G． 参数设置: 热轧工 序轧线侧压量为 300 mm，种群规模 Popsize = 20，最 大迭代次数 MaxGen = 200． 根据现场实际需要，预 设目标函数权重系数 ρ1 ∶ ρ2 ∶ ρ3 ∶ ρ4 ∶ ρ5 = 3∶ 1∶ 2∶ 1∶ 3， 将不同数据规模下合同与余材进行匹配． 采用从实 际生产过程中抽取的覆盖 30 个钢种的 105 个热轧 生产合同、384 块板坯余材和 309 个钢卷余材数据 见表 1． 表 1 热轧生产合同、板坯余材和钢卷余材统计数据 Table 1 Statistic data of hot rolling production orders，open-order slabs and open-order coils 类别 原始合同 原始板坯 原始钢卷 可匹配合同 可匹配板坯 可匹配钢卷 数量 105 384 309 98 312 198 质量/t 19 750. 0 10 790. 4 8 384. 9 19 110. 0 8 924. 2 5 360. 3 在实际生产中，难以对匹配方法的优劣做出精 确的评价，本文从匹配时间、不同等级余材和合同的 匹配率以及合同完整性等方面对匹配结果进行评 价． 库存余材与合同匹配结果分别见表 2 和表 3． ·1201·