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

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·

·1202· 北京科技大学学报 第34卷 表2基于三种匹配方法的板坯、钢卷匹配结果 Table 2 Matching results of slabs and coils based on three matching methods 余材 可匹配 启发式常规匹配 改进遗传算法常规匹配 改进遗传算法集成匹配 优先级 质量作 种类 数量 匹配质量A匹配率/% 匹配质量 匹配率/% 匹配质量A 匹配率/% 1 42 1171.8 947.6 80.8 1035.9 88.4 1096.8 93.6 2 61 1772.5 1394.8 78.7 1480.0 83.5 1596.3 90.0 3 48 1377.6 1061.3 77.0 1119.3 81.3 1201.2 87.2 板坯 4 75 2130.0 1591.4 74.7 1675.6 78.7 1831.8 86.0 5 86 2472.3 1812.7 73.3 1868.6 75.6 2104.4 85.1 板坯合计 312 8924.2 6807.8 76.3 7179.4 80.4 7830.5 87.7 1 51 1328.1 1276.1 96.0 1276.1 96.0 1276.1 96.0 2 42 1138.2 1083.3 95.2 1087.3 95.5 1087.3 95.5 3 35 941.5 856.8 91.0 883.2 93.8 856.8 91.0 钢卷 4 41 1152.1 994.3 86.3 1048.4 91.0 955.1 82.9 5 29 800.4 690.2 86.2 717.8 89.7 634.2 79.2 钢卷合计 198 5360.3 4850.7 90.9 5012.8 93.5 4809.5 89.7 合计 510 14284.5 11658.5 81.8 12192.2 85.4 12640 88.5 表3基于三种匹配方法的合同匹配结果对比 Table 3 Matching results of orders based on three matching methods 启发式常规匹配 改进遗传算法常规匹配 改进遗传算法集成匹配 合同 可匹配合 可匹配合 优先级 同数量 同质量1 匹配 合同匹 完整 匹配 合同匹 完整 匹配 合同匹 完整 质量作 配率/% 合同数 质量作 配率/% 合同数 质量A 配率/% 合同数 1 14 4537.1 1982.9 43.7 6 2592.6 57.1 8 388.9 85.7 12 2 23 7268.6 2550.1 35.1 > 3160.2 43.5 10 4131.6 56.8 18 11880.5 3386.7 28.5 8 3412.7 28.7 11 2795.4 23.5 4 9 3410.6 950.4 27.9 0 923.1 27.1 1 721.3 21.1 5 18 8335.3 2816.4 33.8 0 2103.6 25.2 1102.8 13.2 合计 98 35432.2 11658.5 32.9 21 12192.2 34.4 31 12640.0 35.6 43 图3为三种匹配方法对板坯及钢卷的匹配率的 配更好的效果 影响，图4和图5分别为三种匹配方法对合同匹配 的匹配率和完整合同数的影响.从三幅图中可以看 ■启发式常规匹配 园改进遗传算法常规匹配 出，通过启发式常规匹配方法得到的匹配结果远不 100 ☑改进遗传算法集成匹配 如基于改进遗传算法的常规匹配和集成匹配.比较 c 基于改进遗传算法的常规匹配和集成匹配的求解结 果，可以看出：(1)从余材匹配率上看，虽然前者的 0 钢卷匹配率略高于后者，但从板坯匹配率和所有余 材的整体匹配率上看，后者远远高于前者（见图3）： (2)从合同的匹配率上看，常规匹配方法对优先级 0 较高的合同的匹配率远不如集成匹配（见图4）： 有 (3)从完整合同数上看，通过集成匹配得到的完整 余材种类 合同数目明显高于常规匹配（见图5）.综上所述， 图3 三种匹配方法对余材匹配率的影响 集成匹配在对所有余材的匹配率、所有合同的匹配 Fig.3 Influence of three matching methods on the matching rate of 率以及匹配合同的完整数方面都能够得到比常规匹 open-order slabs and coils

北 京 科 技 大 学 学 报 第 34 卷 表 2 基于三种匹配方法的板坯、钢卷匹配结果 Table 2 Matching results of slabs and coils based on three matching methods 余材 种类 优先级 可匹配 数量 质量/t 启发式常规匹配 改进遗传算法常规匹配 改进遗传算法集成匹配 匹配质量/t 匹配率/% 匹配质量/t 匹配率/% 匹配质量/t 匹配率/% 1 42 1 171. 8 947. 6 80. 8 1 035. 9 88. 4 1 096. 8 93. 6 2 61 1 772. 5 1 394. 8 78. 7 1 480. 0 83. 5 1 596. 3 90. 0 板坯 3 48 1 377. 6 1 061. 3 77. 0 1 119. 3 81. 3 1 201. 2 87. 2 4 75 2 130. 0 1 591. 4 74. 7 1 675. 6 78. 7 1 831. 8 86. 0 5 86 2 472. 3 1 812. 7 73. 3 1 868. 6 75. 6 2 104. 4 85. 1 板坯合计 312 8 924. 2 6 807. 8 76. 3 7 179. 4 80. 4 7 830. 5 87. 7 1 51 1 328. 1 1 276. 1 96. 0 1 276. 1 96. 0 1 276. 1 96. 0 2 42 1 138. 2 1 083. 3 95. 2 1 087. 3 95. 5 1 087. 3 95. 5 钢卷 3 35 941. 5 856. 8 91. 0 883. 2 93. 8 856. 8 91. 0 4 41 1 152. 1 994. 3 86. 3 1 048. 4 91. 0 955. 1 82. 9 5 29 800. 4 690. 2 86. 2 717. 8 89. 7 634. 2 79. 2 钢卷合计 198 5 360. 3 4 850. 7 90. 9 5 012. 8 93. 5 4 809. 5 89. 7 合计 510 14 284. 5 11 658. 5 81. 8 12 192. 2 85. 4 12 640 88. 5 表 3 基于三种匹配方法的合同匹配结果对比 Table 3 Matching results of orders based on three matching methods 合同 优先级 可匹配合 同数量 可匹配合 同质量/t 启发式常规匹配 改进遗传算法常规匹配 改进遗传算法集成匹配 匹配 质量/t 合同匹 配率/% 完整 合同数 匹配 质量/t 合同匹 配率/% 完整 合同数 匹配 质量/t 合同匹 配率/% 完整 合同数 1 14 4 537. 1 1 982. 9 43. 7 6 2 592. 6 57. 1 8 3 88. 9 85. 7 12 2 23 7 268. 6 2 550. 1 35. 1 7 3 160. 2 43. 5 10 4 131. 6 56. 8 18 3 34 11 880. 5 3 386. 7 28. 5 8 3 412. 7 28. 7 11 2 795. 4 23. 5 8 4 9 3 410. 6 950. 4 27. 9 0 923. 1 27. 1 1 721. 3 21. 1 2 5 18 8 335. 3 2 816. 4 33. 8 0 2 103. 6 25. 2 1 1 102. 8 13. 2 3 合计 98 35 432. 2 11 658. 5 32. 9 21 12 192. 2 34. 4 31 12 640. 0 35. 6 43 图 3 为三种匹配方法对板坯及钢卷的匹配率的 影响，图 4 和图 5 分别为三种匹配方法对合同匹配 的匹配率和完整合同数的影响． 从三幅图中可以看 出，通过启发式常规匹配方法得到的匹配结果远不 如基于改进遗传算法的常规匹配和集成匹配． 比较 基于改进遗传算法的常规匹配和集成匹配的求解结 果，可以看出: ( 1) 从余材匹配率上看，虽然前者的 钢卷匹配率略高于后者，但从板坯匹配率和所有余 材的整体匹配率上看，后者远远高于前者( 见图 3) ; ( 2) 从合同的匹配率上看，常规匹配方法对优先级 较高的合同的匹配率远不如集成匹配( 见图 4) ; ( 3) 从完整合同数上看，通过集成匹配得到的完整 合同数目明显高于常规匹配( 见图 5) ． 综上所述， 集成匹配在对所有余材的匹配率、所有合同的匹配 率以及匹配合同的完整数方面都能够得到比常规匹 配更好的效果． 图 3 三种匹配方法对余材匹配率的影响 Fig． 3 Influence of three matching methods on the matching rate of open-order slabs and coils ·1202·

第10期 李海涛等：连铸与热轧工序余材集成匹配模型与算法 ·1203· 100 数，通过改进遗传算法求解的收敛曲线.从图中可 圆启发式常规匹配 90 园改进遗传算法常规匹配 以看出，目标值在20代以内很快收敛，在50代以内 ☑改进遗传算法集成匹配 达到收敛值. 70 78000 一一收敛曲线 60 76000 So/ 延74000 1级合 2级合同 级合 4级合同 合 所有合同 差2m 合同优先级 70000L 图4三种匹配方法对合同匹配率的影响 68000 Fig.4 Influence of three matching methods on the matching rate of 50 100 150 200 orders 迭代次数 图6对表1中数据用改进遗传算法求解的一次执行过程 50 Fig.6 Experimental process of data from Table I by the improved 圆启发式常规匹配 genetic algorithm ☒改进遗传算法常规匹配 30 ⑦改进遴传算法集成匹配 为了对算法的有效性进行进一步验证，选取六 20 组不同规模生产合同、板坯和钢卷数据，对1.3中建 立的模型分别采用约束规划软件CP和本文所提的 N. 改进遗传算法进行求解，通过实验结果的对比衡量 级合 2级合同 级合同 级合同 级合同 有合铜 算法的解的品质.CP和改进遗传算法的结果如表4 合同优先级 所示. 图5三种方法匹配对完整合同数的影响 改进遗传算法在所有六组实验中，均获得了优 Fig.5 Influence of three matching methods on the number of fully 于CP优化软件得到的解，而所消耗的计算时间远 matched orders 远小于CP所消耗的时间.考虑CP是目前最好的约 3.2算法的有效性实验 束规划软件之一，不同规模的数据实验证明了算法 图6是根据表1中数据和3.1中所设置的参 的有效性 表4不同规模算例改进遗传算法与CP结果比较 Table 4 Comparison between the improved genetic algorithm and CP with different scale data 可匹配 可匹配 可匹配 CP 改进遗传算法 数据 合同数 板坯数 钢卷数 目标函数值 时间/s 目标函数值 时间/s 12 31 23 6832.2 578.43 6801.3 1.02 2 21 54 43 14573.1 5963.42 14425.3 4.01 3 26 68 56 15261.4 9758.36 15021.7 4.34 4 43 95 91 27449.6 15336.12 27101.8 6.56 5 69 162 129 38542.8 22653.60 38167.2 10.32 6 98 312 198 68531.7 34921.87 68052.3 23.34 4结论 合同进行集成匹配，建立多目标0一1非线性规划模 型；(3)采用改进遗传算法对所建模型进行求解，并 对于钢铁企业铸轧工序库存余材与合同匹配问 将结果与常规匹配方法及约束规划标准软件CP的 题的研究，本文做了如下工作：(1)引入板坯材质与 求解结果进行对比. 合同要求钢种特征差异值矩阵、钢卷钢种与合同要 通过仿真实验对比结果表明，本文所提出的连 求钢种特征差异值矩阵来表征余材与合同要求产品 铸与热轧工序余材集成匹配模型及其改进遗传算法 的钢种差异程度，为匹配过程中的“以优充次”提供 能够最大限度地满足优先级别高的合同的匹配率及 量化条件：(2)将热轧生产中的余材板坯与钢卷对 合同完整性，并且相对于启发式常规匹配，在余材匹

第 10 期 李海涛等: 连铸与热轧工序余材集成匹配模型与算法 图 4 三种匹配方法对合同匹配率的影响 Fig． 4 Influence of three matching methods on the matching rate of orders 图 5 三种方法匹配对完整合同数的影响 Fig． 5 Influence of three matching methods on the number of fully matched orders 3. 2 算法的有效性实验 图 6 是根据表 1 中数据和 3. 1 中所设置的参 数，通过改进遗传算法求解的收敛曲线． 从图中可 以看出，目标值在 20 代以内很快收敛，在 50 代以内 达到收敛值． 图 6 对表 1 中数据用改进遗传算法求解的一次执行过程 Fig． 6 Experimental process of data from Table 1 by the improved genetic algorithm 为了对算法的有效性进行进一步验证，选取六 组不同规模生产合同、板坯和钢卷数据，对 1. 3 中建 立的模型分别采用约束规划软件 CP 和本文所提的 改进遗传算法进行求解，通过实验结果的对比衡量 算法的解的品质． CP 和改进遗传算法的结果如表 4 所示． 改进遗传算法在所有六组实验中，均获得了优 于 CP 优化软件得到的解，而所消耗的计算时间远 远小于 CP 所消耗的时间． 考虑 CP 是目前最好的约 束规划软件之一，不同规模的数据实验证明了算法 的有效性． 表 4 不同规模算例改进遗传算法与 CP 结果比较 Table 4 Comparison between the improved genetic algorithm and CP with different scale data 数据 可匹配 合同数 可匹配 板坯数 可匹配 钢卷数 CP 改进遗传算法 目标函数值 时间/s 目标函数值 时间/s 1 12 31 23 6 832. 2 578. 43 6 801. 3 1. 02 2 21 54 43 14 573. 1 5 963. 42 14 425. 3 4. 01 3 26 68 56 15 261. 4 9 758. 36 15 021. 7 4. 34 4 43 95 91 27 449. 6 15 336. 12 27 101. 8 6. 56 5 69 162 129 38 542. 8 22 653. 60 38 167. 2 10. 32 6 98 312 198 68 531. 7 34 921. 87 68 052. 3 23. 34 4 结论 对于钢铁企业铸轧工序库存余材与合同匹配问 题的研究，本文做了如下工作: ( 1) 引入板坯材质与 合同要求钢种特征差异值矩阵、钢卷钢种与合同要 求钢种特征差异值矩阵来表征余材与合同要求产品 的钢种差异程度，为匹配过程中的“以优充次”提供 量化条件; ( 2) 将热轧生产中的余材板坯与钢卷对 合同进行集成匹配，建立多目标 0--1 非线性规划模 型; ( 3) 采用改进遗传算法对所建模型进行求解，并 将结果与常规匹配方法及约束规划标准软件 CP 的 求解结果进行对比． 通过仿真实验对比结果表明，本文所提出的连 铸与热轧工序余材集成匹配模型及其改进遗传算法 能够最大限度地满足优先级别高的合同的匹配率及 合同完整性，并且相对于启发式常规匹配，在余材匹 ·1203·

·1204· 北京科技大学学报 第34卷 配率、匹配总质量和匹配时间等方面都具有明显优 (孙树慧，肖拥军，李铁克，基于约束满足方法求解热轧带钢 势，为钢铁企业余材匹配问题提供了更为有效的匹 库存匹配问题.北京科技大学学报，2008,30(6)：680) 配方法 [10]Lu K B,Huang K W,Wang D W,et al.Integrated optimization approach of contract planning and surplus inventory matching of steel mill.Control Decis,2009,24(1)71 参考文献 (卢克斌，黄可为，汪定伟，等.钢铁企业合同计划与余材匹 [Yu C Y,Wang C N.Multi-objective order-planning model and al- 配的集成优化方法.控制与决策，2009,24(1)：71) gorithm for integrated steel production.Control Theory Appl, [11]Zhang T,Cheng H G,Zhang Y J,et al.A method based on 2009,26(12):1452 MTO-MTS for the order planning of the steel plant.Syst Eng The- (於春月，王成恩.钢铁一体化生产多目标合同计划建模与算 ory Pract,2008,28(11):85 法.控制理论与应用，2009,26(12)：1452) (张涛，程海刚，张钥杰，等.基于MTO-MTS的钢厂合同计 2]Lv Z M,Zhang W J,Xu J W.Optimization method for operation 划方法.系统工程理论与实践，2008,28(11)：85) planning of special fumace hot charge mode.Unie Sci Technol [12]Tian Z B,Tang L X,Ren Y M,et al.Solving open-order slab Beijing,2009,31(7):929 matching problem by ACO with compound neighborhood.Acta (吕志民，张武军，徐金悟.专用炉混装模式下作业计划优化 Autom Sin,2009,35(2):186 方法.北京科技大学学报，2009,31(7)：929) (田志波，唐立新，任一鸣，等.基于合成邻域的蚁群算法求 B3]Lu Y M,Xu A J.He D F,et al.Hot-tolling batch planning meth- 解无委托板坯匹配问题.自动化学报，2009,35(2)：186) od available to improve DHCR proportion.JUni Sci Technol Bei- D3] Bai X Z,Ji S L.Application of genetic algorithm to the match of ing,2011,33(10):1301 no-entrusted slabs and contracts.Control Eng China,2008,15 (芦永明，徐安军，贺东风，等.一种有利于提高DHCR比例 (1):97 的热轧批量计划编制方法.北京科技大学学报，2011,33 (白小振，吉守龙.遗传算法在无委托板坯与合同匹配中的 (10):1301) 应用.控制工程，2008,15(1)：97) 4]Xue Y C,Zheng D L,Yang Q W.Optimum steel making cast 04] Ugur A,Korukoglu S,Caliskan A,et al.Genetic algorithm plan with unknown cast number based on the modified discrete par- based solution for TSP on a sphere.Math Comput Appl,2009,14 ticle swarm optimization.Control Theory Appl,2010,27(2):273 (3):219 (薛云灿，郑东亮，杨启文.基于改进离散粒子群算法的炼钢 [15]Xing L N,Chen Y W,Yang K W,et al.A hybrid approach 连铸最优浇次计划.控制理论与应用，2010,27(2)：273) combining an improved genetic algorithm and optimization strate- 5]Zhu B L,Yu H B.Production scheduling model and algorithm for gies for the asymmetric traveling salesman problem.Eng Appl Ar- steelmaking-continuous casting-hot rolling processes.Comput Inte- tif Intell,2008,21(8):1370 gr Manuf Syst,2003,9(1)33 16] Rajkumar R,Shahabudeen P.An improved genetic algorithm for (朱宝琳，于海斌.炼钢一连铸一热轧生产调度模型及算法研 the flowshop scheduling problem.Int J Prod Res,2009,47(1): 究.计算机集成制造系统，2003,9(1)：33) 233 [6 Wang H B,Xu A J,Yao L,et al.Appling an improved genetic al- [17]Pezzella F,Morganti G,Ciaschetti G.A genetic algorithm for the gorithm for solving the production scheduling problem of steelmak- flexible job-shop scheduling problem.Comput Oper Res,2008 ing and continuous casting.J Unir Sci Technol Beijing,2010,32 35(10):3202 (9):1232 [18]Goncalves J F.A hybrid genetic algorithm-heuristic for a two-di- (汪红兵，徐安军，姚琳，等.应用改进遗传算法求解炼钢连 mensional orthogonal packing problem.Eur Oper Res,2007, 铸生产调度问题.北京科技大学学报，2010,32(9)：1232) 183(3):1212 Hu K Y,Zhu Y L,Wang D W.Adaptive PBIL algorithms for or- 19] Song H S,Fu R Y,Xu R S,et al.Hybrid genetic algorithm for der optimal matching problems.Syst Eng,2004,22 (12):87 multi-knapsack problem.Comput Eng Appl,2009.45(20):45 (胡琨元，朱云龙，汪定伟.自适应PBL算法求解合同优化 (宋海生，傅仁毅，徐瑞松，等.求解多背包问题的混合遗传 匹配问题.系统工程，2004,22(12)：87) 算法.计算机工程与应用，2009,45(20)：45) [8]Hu K Y,Gao Z W,Wang D W.Optimal multibjective model 20] Rahman K M,Ahmed S I.Performance analysis of genetic algo- and algorithm for order matching problems in iron steel plants.J rithm for solving the multiple-choice multi-dimensional knapsack Northeast Univ Nat Sci,2004,25(6):527 problem.Int J Recent Trends Eng,2009,2(2):103 (胡琨元，高政威，汪定伟.钢铁企业合同匹配多目标优化模 D1]Li S J,Chang Z M.Continuous Casting and Rolling Production 型与算法.东北大学学报：自然科学版，2004,25(6)：527) Logistics Management.Beijing:Metallurgical Industry Press, [9]Sun S H,Xiao Y J,Li T K.Solving the inventory matching prob- 2001 lem of hot rolling strips based on the constraint satisfaction meth- (李苏剑，常志明.连铸一连轧生产物流管理.北京：治金工 od.J Unig Sci Technol Beijing,2008,30(6):680 业出版社，2001)）

北 京 科 技 大 学 学 报 第 34 卷 配率、匹配总质量和匹配时间等方面都具有明显优 势，为钢铁企业余材匹配问题提供了更为有效的匹 配方法． 参 考 文 献 ［1］ Yu C Y，Wang C N． Multi-objective order-planning model and al￾gorithm for integrated steel production． Control Theory Appl， 2009，26( 12) : 1452 ( 於春月，王成恩． 钢铁一体化生产多目标合同计划建模与算 法． 控制理论与应用，2009，26( 12) : 1452) ［2］ Lv Z M，Zhang W J，Xu J W． Optimization method for operation planning of special furnace hot charge mode． J Univ Sci Technol Beijing，2009，31( 7) : 929 ( 吕志民，张武军，徐金悟． 专用炉混装模式下作业计划优化 方法． 北京科技大学学报，2009，31( 7) : 929) ［3］ Lu Y M，Xu A J，He D F，et al． Hot-rolling batch planning meth￾od available to improve DHCR proportion． J Univ Sci Technol Bei￾jing，2011，33( 10) : 1301 ( 芦永明，徐安军，贺东风，等． 一种有利于提高 DHCR 比例 的热轧批量计划 编 制 方 法． 北京科技大学学报，2011，33 ( 10) : 1301) ［4］ Xue Y C，Zheng D L，Yang Q W． Optimum steel making cast plan with unknown cast number based on the modified discrete par￾ticle swarm optimization． Control Theory Appl，2010，27( 2) : 273 ( 薛云灿，郑东亮，杨启文． 基于改进离散粒子群算法的炼钢 连铸最优浇次计划． 控制理论与应用，2010，27( 2) : 273) ［5］ Zhu B L，Yu H B． Production scheduling model and algorithm for steelmaking-continuous casting-hot rolling processes． Comput Inte￾gr Manuf Syst，2003，9( 1) : 33 ( 朱宝琳，于海斌． 炼钢--连铸--热轧生产调度模型及算法研 究． 计算机集成制造系统，2003，9( 1) : 33) ［6］ Wang H B，Xu A J，Yao L，et al． Appling an improved genetic al￾gorithm for solving the production scheduling problem of steelmak￾ing and continuous casting． J Univ Sci Technol Beijing，2010，32 ( 9) : 1232 ( 汪红兵，徐安军，姚琳，等． 应用改进遗传算法求解炼钢连 铸生产调度问题． 北京科技大学学报，2010，32( 9) : 1232) ［7］ Hu K Y，Zhu Y L，Wang D W． Adaptive PBIL algorithms for or￾der optimal matching problems． Syst Eng，2004，22( 12) : 87 ( 胡琨元，朱云龙，汪定伟． 自适应 PBIL 算法求解合同优化 匹配问题． 系统工程，2004，22( 12) : 87) ［8］ Hu K Y，Gao Z W，Wang D W． Optimal multi-objective model and algorithm for order matching problems in iron ＆ steel plants． J Northeast Univ Nat Sci，2004，25( 6) : 527 ( 胡琨元，高政威，汪定伟． 钢铁企业合同匹配多目标优化模 型与算法． 东北大学学报: 自然科学版，2004，25( 6) : 527) ［9］ Sun S H，Xiao Y J，Li T K． Solving the inventory matching prob￾lem of hot rolling strips based on the constraint satisfaction meth￾od． J Univ Sci Technol Beijing，2008，30( 6) : 680 ( 孙树慧，肖拥军，李铁克． 基于约束满足方法求解热轧带钢 库存匹配问题． 北京科技大学学报，2008，30( 6) : 680) ［10］ Lu K B，Huang K W，Wang D W，et al． Integrated optimization approach of contract planning and surplus inventory matching of steel mill． Control Decis，2009，24( 1) : 71 ( 卢克斌，黄可为，汪定伟，等． 钢铁企业合同计划与余材匹 配的集成优化方法． 控制与决策，2009，24( 1) : 71) ［11］ Zhang T，Cheng H G，Zhang Y J，et al． A method based on MTO-MTS for the order planning of the steel plant． Syst Eng The￾ory Pract，2008，28( 11) : 85 ( 张涛，程海刚，张钥杰，等． 基于 MTO-MTS 的钢厂合同计 划方法． 系统工程理论与实践，2008，28( 11) : 85) ［12］ Tian Z B，Tang L X，Ren Y M，et al． Solving open-order slab matching problem by ACO with compound neighborhood． Acta Autom Sin，2009，35( 2) : 186 ( 田志波，唐立新，任一鸣，等． 基于合成邻域的蚁群算法求 解无委托板坯匹配问题． 自动化学报，2009，35( 2) : 186) ［13］ Bai X Z，Ji S L． Application of genetic algorithm to the match of no-entrusted slabs and contracts． Control Eng China，2008，15 ( 1) : 97 ( 白小振，吉守龙． 遗传算法在无委托板坯与合同匹配中的 应用． 控制工程，2008，15( 1) : 97) ［14］ Ugˇur A，Korukogˇlu S，aliskan A，et al． Genetic algorithm based solution for TSP on a sphere． Math Comput Appl，2009，14 ( 3) : 219 ［15］ Xing L N，Chen Y W，Yang K W，et al． A hybrid approach combining an improved genetic algorithm and optimization strate￾gies for the asymmetric traveling salesman problem． Eng Appl Ar￾tif Intell，2008，21( 8) : 1370 ［16］ Rajkumar R，Shahabudeen P． An improved genetic algorithm for the flowshop scheduling problem． Int J Prod Res，2009，47( 1) : 233 ［17］ Pezzella F，Morganti G，Ciaschetti G． A genetic algorithm for the flexible job-shop scheduling problem． Comput Oper Res，2008， 35( 10) : 3202 ［18］ Gonalves J F． A hybrid genetic algorithm-heuristic for a two-di￾mensional orthogonal packing problem． Eur J Oper Res，2007， 183( 3) : 1212 ［19］ Song H S，Fu R Y，Xu R S，et al． Hybrid genetic algorithm for multi-knapsack problem． Comput Eng Appl，2009，45( 20) : 45 ( 宋海生，傅仁毅，徐瑞松，等． 求解多背包问题的混合遗传 算法． 计算机工程与应用，2009，45( 20) : 45) ［20］ Rahman K M，Ahmed S I． Performance analysis of genetic algo￾rithm for solving the multiple-choice multi-dimensional knapsack problem． Int J Recent Trends Eng，2009，2( 2) : 103 ［21］ Li S J，Chang Z M． Continuous Casting and Rolling Production Logistics Management． Beijing: Metallurgical Industry Press， 2001 ( 李苏剑，常志明． 连铸—连轧生产物流管理． 北京: 冶金工 业出版社，2001) ·1204·