基于约束满足的板坯设计模型与求解方法

DOI:10.13374/.issn1001-053x.2011.05.015 第33卷第5期 北京科技大学学报 Vol.33 No.5 2011年5月 Journal of University of Science and Technology Beijing May 2011 基于约束满足的板坯设计模型与求解方法 张文学1,2,3)区 李铁克12) 1)北京科技大学经济管理学院，北京1000832)钢铁生产制造执行系统技术教有部工程研究中心，北京100083 3)宁夏医科大学理学院，银川750004 ☒通信作者，E-mail:wxzhang(@163.com 摘要针对客户订单的重量需求为固定值、客户订单分配过程中有最小重量限制的板坯设计问题，建立了以最小化板坯数 量为目标的约束满足模型.通过三划分问题的多项式归结，证明了该问题是强NP难的：针对问题的特殊性质，给出了变量选 择策略和值选择策略：提出了基于约束满足技术的求解算法，并证明了算法的收敛性：通过数据实验对算法的有效性进行了 验证 关键词热轧：板坯：生产计划：约束满足：变量选择；值选择 分类号TP18:F273.1 Modelling and algorithm for the slab designing problem based on constraint sat- isfaction ZHANG Wen-xue2.☒，UTie-he2) 1)School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron Steel Production,Ministry of Education of China,Beijing 100083.China 3)School of Sciences,Ningxia Medical University,Yinchuan 750004,China Corresponding author,E-mail:wxzhang@163.com ABSTRACT A constraint satisfaction model whose objective is to minimize the slab number was built for slab production in consider- ation of the slab designing problem with a fixed demand of order weight and a minimum limitation of order weight assigned in one slab. The problem was proved to be NP-hard by reducing a known NP-hard three-partition problem to the discussed problem in polynomial time.Concerning with special characteristics of the problem,variable selection strategies and value selection strategies were presented. A constraint-satisfaction-based algorithm was proposed and it was proved to be convergent.The effectiveness of the proposed algorithm was verified with simulation experiments. KEY WORDS hot rolling:slabs:production planning:constraint satisfaction:variable selection:value selection 在钢铁企业的热轧板生产中，铁水通过炼钢设 订单与板坯的关系，然后由板坯组成炉次，由炉次组 备转化为钢水，钢水通过连铸机转换为板坯，板坯通 成浇次，最后通过板坯的对应关系协调浇次与轧制 过热轧机组转换为热轧板，热轧板既可作为产品出 单元的衔接.可见，板坯设计是整个生产组织过程 售，也可作为冷轧的原料被进一步加工.从生产组 中的先行环节，是将客户订单与生产过程连接起来 织的角度来看，炼钢环节以炉次为单位、连铸环节以 的关键所在.板坯设计问题就是针对给定的客户订 浇次为单位、热轧环节以轧制单元为单位进行计划 单需求，在满足工艺限制的前提下设计出生产成本 与调度管理.在生产计划的制定过程中，通常是先 最低的板坯集合四 通过板坯设计将客户订单分配到板坯中，建立客户 板坯设计是钢铁企业生产计划管理中的关键环 收稿日期：2010-07-15 基金项目：国家自然科学基金资助项目(No.70771008):中央高校基本科研业务费专项(N。.FRF-AS-09O07B):宁夏医科大学特殊人才科 研启动基金项目

第 33 卷 第 5 期 2011 年 5 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 33 No． 5 May 2011 基于约束满足的板坯设计模型与求解方法 张文学1，2，3) 李铁克1，2) 1) 北京科技大学经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083 3) 宁夏医科大学理学院，银川 750004 通信作者，E-mail: wxzhang@ 163． com 摘 要 针对客户订单的重量需求为固定值、客户订单分配过程中有最小重量限制的板坯设计问题，建立了以最小化板坯数 量为目标的约束满足模型． 通过三划分问题的多项式归结，证明了该问题是强 NP 难的; 针对问题的特殊性质，给出了变量选 择策略和值选择策略; 提出了基于约束满足技术的求解算法，并证明了算法的收敛性; 通过数据实验对算法的有效性进行了 验证． 关键词 热轧; 板坯; 生产计划; 约束满足; 变量选择; 值选择 分类号 TP18; F273. 1 Modelling and algorithm for the slab designing problem based on constraint sat￾isfaction ZHANG Wen-xue 1，2，3) ，LI Tie-ke 1，2) 1) School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China 2) Engineering Research Center of MES Technology for Iron ＆ Steel Production，Ministry of Education of China，Beijing 100083，China 3) School of Sciences，Ningxia Medical University，Yinchuan 750004，China Corresponding author，E-mail: wxzhang@ 163． com ABSTRACT A constraint satisfaction model whose objective is to minimize the slab number was built for slab production in consider￾ation of the slab designing problem with a fixed demand of order weight and a minimum limitation of order weight assigned in one slab． The problem was proved to be NP-hard by reducing a known NP-hard three-partition problem to the discussed problem in polynomial time． Concerning with special characteristics of the problem，variable selection strategies and value selection strategies were presented． A constraint-satisfaction-based algorithm was proposed and it was proved to be convergent． The effectiveness of the proposed algorithm was verified with simulation experiments． KEY WORDS hot rolling; slabs; production planning; constraint satisfaction; variable selection; value selection 收稿日期: 2010--07--15 基金项目: 国家自然科学基金资助项目( No． 70771008) ; 中央高校基本科研业务费专项( No． FRF--AS--09--007B) ; 宁夏医科大学特殊人才科 研启动基金项目 在钢铁企业的热轧板生产中，铁水通过炼钢设 备转化为钢水，钢水通过连铸机转换为板坯，板坯通 过热轧机组转换为热轧板，热轧板既可作为产品出 售，也可作为冷轧的原料被进一步加工． 从生产组 织的角度来看，炼钢环节以炉次为单位、连铸环节以 浇次为单位、热轧环节以轧制单元为单位进行计划 与调度管理． 在生产计划的制定过程中，通常是先 通过板坯设计将客户订单分配到板坯中，建立客户 订单与板坯的关系，然后由板坯组成炉次，由炉次组 成浇次，最后通过板坯的对应关系协调浇次与轧制 单元的衔接． 可见，板坯设计是整个生产组织过程 中的先行环节，是将客户订单与生产过程连接起来 的关键所在． 板坯设计问题就是针对给定的客户订 单需求，在满足工艺限制的前提下设计出生产成本 最低的板坯集合［1］． 板坯设计是钢铁企业生产计划管理中的关键环 DOI:10.13374/j.issn1001-053x.2011.05.015

·642· 北京科技大学学报 第33卷 节，因其具有重要的应用价值而受到研究者的关注 与调度的优化管理 目前，该领域的研究文献主要集中在以下几个方面. 本文考虑的板坯设计问题来自于某国有大型钢 (1)针对客户订单的规格需求为固定值的情 铁企业生产管理的实际需求，其前提条件如下： 况，Fish等园分析整理了问题的背景、特点和约束 (1)因连铸机结晶器的限制，板坯的宽度为一 条件；Hnich等回建立了问题的整数规划模型和约 定范围内的确定值： 束规划模型：Gargani等基于逻辑和全局约束，设 (2)为了降低生产组织的复杂性，板坯为定尺 计了将特殊的变量和值选择策略嵌入到大规模领域 规格，即所有板坯的重量相同： 搜索中的求解算法；Van Hentenryck等对文献4] (3)客户订单要求的产品规格与板坯规格间的 中的方法进行了改进和拓展. 对应已经确定，能够被分配到同块板坯的订单必有 (2)针对客户订单的规格需求为区间值的情 相同的板坯宽度需求，在这种情况下可以将板坯设 况，Dawande等针对重量的需求为区间值的问题， 计问题分解为多个板坯宽度相同的相互独立的子 提出了启发式算法：席阳等0在板坯大小可以任意 问题； 切割的前提下，针对客户订单对板坯宽度和重量的 (4)板坯和订单之间可以是多对多的关系，即 需求都为区间值的问题，提出了以最小化板坯数量 一个订单可以被分配到多块板坯，一块板坯也可以 和盈余重量为目标的多项式时间最优算法 包含多个订单的分配重量； (3)针对连铸机生产能力为瓶颈的情况， (5)订单在板坯中有最小分配重量限制： Denton等团研究了以最小化板坯规格数量为目标的 (6)经过前期的预处理，能够保证给定的问题 板坯设计问题；Vonderembse等图与Dash等分别 有可行解. 研究了连铸机只生产两到三种规格的母板坯，在轧 上述板坯设计问题可以抽象为订单的重量为固 制阶段再将母板坯分割成订单所需规格产品的母板 定值，板坯的规格（宽度、重量）相同，订单有最小分 坯设计问题. 配重量限制，以最小化板坯数量为目标的组合优化 近年来，随着市场客户的定制化要求越来越高， 问题.此问题可由一个三元组P=W,D,C)所表示 钢铁企业中高附加价值产品所占的比重越来越大， 的约束满足问题o来描述.V为变量集，V={V, 为了满足对交货产品单位重量约束、热轧后续的酸 V2,…,Vn};D为定义域集，D={D,D2,…,Dn},其 洗镀锌和冷轧等工艺约束要求，在将订单分配到板 中D:为V:的值域；C为约束关系集，C={C,C2, 坯的过程中，常常会有最小重量限制.这些限制破 …,Cm}. 坏了把订单分配到板坯的过程中重量赋值的连续 1.2符号定义 性，改变了问题的复杂性，从而产生了一类新的问 为了便于描述，模型中用到的符号定义如下. 题.其中，客户订单的重量和规格需求都为固定值， 1.2.1集合和索引 板坯的规格相同，具有最小分配重量限制的板坯设 一订单序号； 计问题是最为基础的问题.本文以该问题为对象， 一板坯序号： 建立其约束满足模型，分析问题的复杂性，提出基于 0一订单集合，0={1,2，…，i,…,n}; 问题特殊性质的求解策略和算法，旨在为板坯设计 S一板坯集合，S={1,2,…j,…,m}. 研究提供问题复杂性分析基础和有效的求解框架. 1.2.2参数 g:一订单i的重量； 1问题分析和约束满足模型 δ：一订单i的最小分配限制重量： 1.1问题描述 W一板坯的重量. 钢铁企业的热轧板生产包括炼钢、连铸和热轧 1.2.3变量 三个主要工艺环节，在其生产组织过程中，板坯是衔 x,一订单i分配到板坯j的重量： 接这些环节的物流单元，也是将客户需求和工艺要 y,0-1变量，值为1表示将订单i的重量分 求统一起来的关键所在.在面向订单的生产模式 配到板坯，值为0表示未将订单i的重量分配到板 中，一块板坯中可以包括多个订单，一个订单也可以 坯 被分配到多块板坯中加工生产.通常板坯设计的目 1.3约束满足模型 标是用尽可能少的板坯数给定的客户订单，从而达 基于上述符号，若将变量xy,和m映射为变 到客户需求余材的最小化，同时也有利于生产计划 量集合V:x的值域O,W],y:的值域{0,1}和m的

北 京 科 技 大 学 学 报 第 33 卷 节，因其具有重要的应用价值而受到研究者的关注． 目前，该领域的研究文献主要集中在以下几个方面． ( 1) 针对客户订单的规格需求为固定值的情 况，Frisch 等［2］分析整理了问题的背景、特点和约束 条件; Hnich 等［3］建立了问题的整数规划模型和约 束规划模型; Gargani 等［4］基于逻辑和全局约束，设 计了将特殊的变量和值选择策略嵌入到大规模领域 搜索中的求解算法; Van Hentenryck 等［5］对文献［4］ 中的方法进行了改进和拓展． ( 2) 针对客户订单的规格需求为区间值的情 况，Dawande 等［6］针对重量的需求为区间值的问题， 提出了启发式算法; 席阳等［1］在板坯大小可以任意 切割的前提下，针对客户订单对板坯宽度和重量的 需求都为区间值的问题，提出了以最小化板坯数量 和盈余重量为目标的多项式时间最优算法． ( 3) 针对连铸机生产能力为瓶颈的情况， Denton等［7］研究了以最小化板坯规格数量为目标的 板坯设计问题; Vonderembse 等［8］与 Dash 等［9］分别 研究了连铸机只生产两到三种规格的母板坯，在轧 制阶段再将母板坯分割成订单所需规格产品的母板 坯设计问题． 近年来，随着市场客户的定制化要求越来越高， 钢铁企业中高附加价值产品所占的比重越来越大， 为了满足对交货产品单位重量约束、热轧后续的酸 洗镀锌和冷轧等工艺约束要求，在将订单分配到板 坯的过程中，常常会有最小重量限制． 这些限制破 坏了把订单分配到板坯的过程中重量赋值的连续 性，改变了问题的复杂性，从而产生了一类新的问 题． 其中，客户订单的重量和规格需求都为固定值， 板坯的规格相同，具有最小分配重量限制的板坯设 计问题是最为基础的问题． 本文以该问题为对象， 建立其约束满足模型，分析问题的复杂性，提出基于 问题特殊性质的求解策略和算法，旨在为板坯设计 研究提供问题复杂性分析基础和有效的求解框架． 1 问题分析和约束满足模型 1. 1 问题描述 钢铁企业的热轧板生产包括炼钢、连铸和热轧 三个主要工艺环节，在其生产组织过程中，板坯是衔 接这些环节的物流单元，也是将客户需求和工艺要 求统一起来的关键所在． 在面向订单的生产模式 中，一块板坯中可以包括多个订单，一个订单也可以 被分配到多块板坯中加工生产． 通常板坯设计的目 标是用尽可能少的板坯数给定的客户订单，从而达 到客户需求余材的最小化，同时也有利于生产计划 与调度的优化管理． 本文考虑的板坯设计问题来自于某国有大型钢 铁企业生产管理的实际需求，其前提条件如下: ( 1) 因连铸机结晶器的限制，板坯的宽度为一 定范围内的确定值; ( 2) 为了降低生产组织的复杂性，板坯为定尺 规格，即所有板坯的重量相同; ( 3) 客户订单要求的产品规格与板坯规格间的 对应已经确定，能够被分配到同块板坯的订单必有 相同的板坯宽度需求，在这种情况下可以将板坯设 计问题分解为多个板坯宽度相同的相互独立的子 问题; ( 4) 板坯和订单之间可以是多对多的关系，即 一个订单可以被分配到多块板坯，一块板坯也可以 包含多个订单的分配重量; ( 5) 订单在板坯中有最小分配重量限制; ( 6) 经过前期的预处理，能够保证给定的问题 有可行解． 上述板坯设计问题可以抽象为订单的重量为固 定值，板坯的规格( 宽度、重量) 相同，订单有最小分 配重量限制，以最小化板坯数量为目标的组合优化 问题． 此问题可由一个三元组 P =〈V，D，C〉所表示 的约束满足问题［10］来描述． V 为变量集，V = { V1， V2，…，Vn } ; D 为定义域集，D = { D1，D2，…，Dn } ，其 中 Di 为 Vi 的值域; C 为约束关系集，C = { C1，C2， …，Cm } ． 1. 2 符号定义 为了便于描述，模型中用到的符号定义如下． 1. 2. 1 集合和索引 i—订单序号; j—板坯序号; O—订单集合，O = { 1，2，…，i，…，n} ; S—板坯集合，S = { 1，2，…，j，…，m} ． 1. 2. 2 参数 gi—订单 i 的重量; δi—订单 i 的最小分配限制重量; W—板坯的重量． 1. 2. 3 变量 xij —订单 i 分配到板坯 j 的重量; yij —0 － 1 变量，值为 1 表示将订单 i 的重量分 配到板坯 j，值为 0 表示未将订单 i 的重量分配到板 坯 j． 1. 3 约束满足模型 基于上述符号，若将变量 xij 、yij和 m 映射为变 量集合 V; xij的值域［0，W］，yij的值域{ 0，1} 和 m 的 ·642·

第5期 张文学等：基于约束满足的板坯设计模型与求解方法 ·643· 值域Z映射为变量的值域D;问题的约束映射为约 else {sum-=p:x=W-sum:p:-=x; 束集合C,板坯设计的可行解问题可以映射为约束 tot -=xt =i;i--;sum =0; 满足问题.进一步设问题的目标表示为函数F,则 if (tot >0)++;)//end if 可将板坯设计优化问题转化为约束满足优化问题 }//end for P=W,D,C,F),对应的模型如下： }//end if (tot >0) [P]min m (1) 上述算法的时间复杂度为O(n·max{g:/W}), s.t. ∑xg=g,i (2) 解的板坯数m=j（三8：)/且最多只有一 ∑，≤W (3) 块板坯有盈余，故该算法得到的解为最优.[证毕] δ≤x≤W,ifyt=1,i,j (4) 定理2问题P是强NP难的 x=0,if yi=0,Yi,j (5) 证明只需将己知是强NP难的三划分问题多 y时∈{0,1}，Vi,j (6) 项式归结为问题P,即可证明定理成立 上述约束满足模型中，目标函数(1)是最小化 对三划分问题的任一实例：给定正整数c1,c2, 板坯数量；约束(2)表示某订单分配到所有板坯的 …,cn,…,c3m,B,记集合A={1,2,…,3n},使得对 重量等于该订单的重量，约束(3)表示所有订单分 3n 配到某板坯的重量受该板坯的重量限制，约束(2) V:eA,有导0) {j++: 3求解方法 for(i=1,t =1,sum =0;i<=n;i++) 3.1算法框架及相关定义 sum +=P:: 由于板坯设计问题具有强NP难的性质，如何 if (sum<=W)(x=p::tot-=p:P:=0;} 设计有效的近似算法成为解决该问题的关键.为

第 5 期 张文学等: 基于约束满足的板坯设计模型与求解方法 值域 Z + 映射为变量的值域 D; 问题的约束映射为约 束集合 C，板坯设计的可行解问题可以映射为约束 满足问题． 进一步设问题的目标表示为函数 F，则 可将板坯设计优化问题转化为约束满足优化问题 P =〈V，D，C，F〉，对应的模型如下: ［P］min m ( 1) s． t． ∑ j xij = gi，i ( 2) ∑i xij≤W ( 3) δi≤xij≤W，if yij = 1，i，j ( 4) xij = 0，if yij = 0，i，j ( 5) yij∈{ 0，1} ，i，j ( 6) 上述约束满足模型中，目标函数( 1) 是最小化 板坯数量; 约束( 2) 表示某订单分配到所有板坯的 重量等于该订单的重量，约束( 3) 表示所有订单分 配到某板坯的重量受该板坯的重量限制，约束( 2) 和约束( 3) 共同表示订单与板坯之间为多对多关 系; 约束( 4) 表示订单分配到板坯时受该订单的最 小分配重量限制; 约束( 5) 表示某订单不分配到某 板坯; 约束( 6) 表示变量 yij的取值范围． 2 问题的复杂性 在上述模型 P 中，当i∈I，δi = 0 时，板坯的 大小可以任意切割，即订单在板坯中没有最小分配 重量限制． 针对这种特殊情况，下面的定理 1 成立; 当i∈I，δi = 0 的条件不成立，即订单在板坯中 有最小分配重量限制时，下面的定理 2 成立． 定理 1 当i∈I，δi = 0 时，问题 P 有多项式 时 间 最 优 算 法， ( 其最优解的目标函数值为 ∑ n i = 1 gi ) W ，其中「?为向上取整． 证明 当i∈I，δi = 0 时，首先订单重量 gi 除以板坯重量 W 的整数部分 W( gi /W) 恰好可生产 gi /W 块板坯; 然后将小数部分与其他订单的小数部 分进行组合与分解，安排到相应的板坯． 其求算法 的伪代码如下: for( i = 1，j = 0，tot = 0; i ＜ = n; i + + ) { pi = gi% W; tot + = pi ; for( t = 1; t ＜ = gi /W; t + + ) { j + + ; xij = W; } } / /end if( tot ＞ 0) { j + + ; for( i = 1，t = 1，sum = 0; i ＜ = n; i + + ) { sum + = pi ; if( sum ＜ = W) { xij = pi ; tot － = pi ; pi =0; } else{ sum － = pi ; xij = W － sum; pi － = xij ; tot － = xij ; t = i; i － － ; sum = 0; if( tot ＞ 0) j + + ; } / /end if } / /end for } / /end if( tot ＞ 0) 上述算法的时间复杂度为 O( n·max{ gi /W} ) ， 解的板坯数 m = j = ( ∑ n i = 1 gi ) W ，且最多只有一 块板坯有盈余，故该算法得到的解为最优． ［证毕］ 定理 2 问题 P 是强 NP 难的． 证明 只需将已知是强 NP 难的三划分问题多 项式归结为问题 P，即可证明定理成立． 对三划分问题的任一实例: 给定正整数 c1，c2， …，cn，…，c3n，B，记集合 A = { 1，2，…，3n} ，使得对 i∈A，有 B 4 ＜ ci ＜ B 2 且 ∑ 3n i = 1 ci = nB． 映射问题 P 的 一个判定实例: 每个订单的重量都不超过板坯的重 量，令 δi = gi = ci，i∈A; 板坯数为 n，板坯重量为 B． 判定存在集合 A 的一个划分 S1，S2，…，Sn，使得 对 1≤j≤n，∑i∈Sj ci = B 的充分必要条件是恰好在 n 个重量为 B 的板坯中可以装入这 3n 个订单． 充分性: 当三划分有解时，存在集合 A 的一个 划分 S1，S2，…，Sj ，…，Sn，1≤j≤n，其中板坯 j 的订 单集合 Sj 满足 ∑i∈Sj ci = B． 此时问题 P 有最优解，板 坯数为 n． 必要 性: 当 问 题 P 有 最 优 解 时，由 i ∈ A，  B 4 ＜ ci ＜ B 2 可得板坯数为 n 且每块板坯中包含三 个订单． 若令板坯 j 所包含的订单集合为 Sj ，1≤j≤ n，可得 ∑i∈Sj ci = B． 所以有 n 个不相交的子集 S1，S2， …，Sj ，…，Sn 形成对集合 A 的一个三划分． 故定理 2 得证． ［证毕］ 上述定理 2 表明本文考虑的板坯设计问题具有 强 NP 难的性质; 而定理 1 则表明将所有订单的重 量 ∑ n i = 1 gi 看成是某个订单的重量，且订单没有最小 分 配 重 量 限 制 时，可 得 问 题 P ( 的 一 个 下 界 ∑ n i = 1 gi ) W ． 3 求解方法 3. 1 算法框架及相关定义 由于板坯设计问题具有强 NP 难的性质，如何 设计有效的近似算法成为解决该问题的关键． 为 ·643·

·644· 北京科技大学学报 第33卷 此，本文提出每次选择一个订单一板坯对，并对其进 策略进行订单一板坯对的选择和订单重量分配.基 行订单重量分配的循环求解框架，进而在此框架下 于上述定义1~定义4，可以将基于约束满足技术的 开发求解算法 可分配订单一板坯对的选择以及订单重量分配方法 [循环求解框架] 的要点叙述如下. 1.Initialize 3.2.1最小自由度优先策略 2.While (not terminate-eondition)do 作为针对y:的变量选择方法：参照困难变量优 2.1 select 0;and S 先赋值的思想，并结合板坯设计问题的特点，提出下 2.2 if (not exist S,)then add a new S;for 0 述的最小自由度优先策略. 2.3 assign the weight of 0;to S. 最小自由度优先策略] 2.4 update variable 订单选择规则：计算亚：；除去I亚：|=0的订单 显然在上述求解框架中，算法的可行性和有效 外，选择min{1亚I}的O,;当l亚I=I亚l时，选择 性主要取决于在每次循环中：(1)如何选取订单一板 min{ygy}的0：当y=时，选择min{p:/6, 坯对：(2)对已选取的订单一板坯对，如何将订单重 P/6}的0g. 量分配到板坯.为了对这些问题做进一步的探讨， 板坯选择规则：对O,计算中，j∈乎：除去 给出以下相关定义. I中I=0的板坯外，优先选择1①：I小的S;当 定义1订单i的未分配重量P:是指该订单的 IΦ，I=|ΦI时，优先选择min{cc}的S· 重量g:减去该订单己经分配到板坯中的重量后所 通过上述最小自由度优先策略可确定优先赋值 剩余量：板坯j的盈余量c,是指其重量中没有订单 的变量y,并得到一个可分配订单一板坯对(， 对应的部分 ).这种选择策略具有计算量小，可以避免构造不 定义2订单i能够被分配到板坯j是指满足 可行的部分解的优点. 下面条件：板坯j尚未包含订单i(记为O:S),8≤ 3.2.2最大可行量分配策略 min{p:c},且若cG和P:-C,≥6，则x=C; 约束满足是求解大规模组合优化问题的一种有 规则3若p:>G和P:-G<6,则x=p:-6 效的智能近似方法，其用一个变量集、变量的值域和 最大可行量分配策略具有以下特点：保证解的 限制变量取值的约束集描述组合优化问题，约 可行性；每个订单一板坯对之间最多只进行一次订 束满足问题的求解是从变量的值域中寻找一组满足 单重量分配：将变量x的赋值的可行域由连续转变为 约束的值赋给变量，主要求解技术包含一致性技术、 离散这些特点为开发高效的近似算法提供了基础 约束传播技术、变量选择和值选择搜索算法@.搜 3.3算法描述 索算法通过不断选择下一个待赋值变量并为该变量 在上述分析的基础上，设O'为待分配订单集 选择一个值来逐步实现问题的求解，该过程称为变 合，S为所需板坯集合，可将本文提出的采用约束满 量选择和值选择.变量的选择顺序和值的选择顺序 足技术最小化板坯数(constraint satisfaction for 直接决定求解效率和寻优性能，通常要根据问题的 minimizing slab quantity,CSMSQ)算法描述如下. 特征构造变量选择和值选择启发式搜索算法：变量 [CSMSQ算法] 选择顺序一般遵循困难变量优先赋值的规则，值选 Step1(初始化) 择顺序遵循将最有希望构成全局解的值优先赋给 输入订单数据和相关参数：0'=0，S=☑，m= 变量 0,Φ=，Ψ：=☑，P:=g:和c=W,Vi,j 本文利用约束满足技术中的变量选择和值选择 Step2（变量选择：选取可分配订单-板坯对)

北 京 科 技 大 学 学 报 第 33 卷 此，本文提出每次选择一个订单--板坯对，并对其进 行订单重量分配的循环求解框架，进而在此框架下 开发求解算法． ［循环求解框架］ 1. Initialize 2. While ( not terminate-condition) do 2. 1 select Oi and Sj 2. 2 if ( not exist Sj ) then add a new Sj for Oi 2. 3 assign the weight of Oi to Sj 2. 4 update variable 显然在上述求解框架中，算法的可行性和有效 性主要取决于在每次循环中: ( 1) 如何选取订单--板 坯对; ( 2) 对已选取的订单--板坯对，如何将订单重 量分配到板坯． 为了对这些问题做进一步的探讨， 给出以下相关定义． 定义 1 订单 i 的未分配重量 pi 是指该订单的 重量 gi 减去该订单已经分配到板坯中的重量后所 剩余量; 板坯 j 的盈余量 cj 是指其重量中没有订单 对应的部分． 定义 2 订单 i 能够被分配到板坯 j 是指满足 下面条件: 板坯 j 尚未包含订单 i( 记为 OiSj ) ，δi≤ min{ pi，cj } ，且若 cj ＜ pi 时必须有 2δi≤pi ; 此时称( i， j) 为可分配订单--板坯对． 定义 3 订单 i 的自由度 | Ψi | 是指该订单能够 分配的板坯数，其中 Ψi 表示订单 i 能够被分配的板 坯集合． 定义 4 板坯 j 的自由度 | Φj | 是指能够被分配 到该板坯的订单数，其中 Φj 表示能够被分配到板坯 j 的订单集合． 3. 2 基于约束满足的求解策略 约束满足是求解大规模组合优化问题的一种有 效的智能近似方法，其用一个变量集、变量的值域和 限制变量取值的约束集描述组合优化问题［11］． 约 束满足问题的求解是从变量的值域中寻找一组满足 约束的值赋给变量，主要求解技术包含一致性技术、 约束传播技术、变量选择和值选择搜索算法［10］． 搜 索算法通过不断选择下一个待赋值变量并为该变量 选择一个值来逐步实现问题的求解，该过程称为变 量选择和值选择． 变量的选择顺序和值的选择顺序 直接决定求解效率和寻优性能，通常要根据问题的 特征构造变量选择和值选择启发式搜索算法; 变量 选择顺序一般遵循困难变量优先赋值的规则，值选 择顺序遵循将最有希望构成全局解的值优先赋给 变量． 本文利用约束满足技术中的变量选择和值选择 策略进行订单--板坯对的选择和订单重量分配． 基 于上述定义 1 ～ 定义 4，可以将基于约束满足技术的 可分配订单--板坯对的选择以及订单重量分配方法 的要点叙述如下． 3. 2. 1 最小自由度优先策略 作为针对 yij的变量选择方法: 参照困难变量优 先赋值的思想，并结合板坯设计问题的特点，提出下 述的最小自由度优先策略． ［最小自由度优先策略］ 订单选择规则: 计算 Ψi ; 除去 | Ψi | = 0 的订单 外，选择 min { | Ψi |} 的 Oi* ; 当| Ψi | = | Ψi' | 时，选择 min { yij ，yi'j'} 的 Oi* ; 当 yij = yi'j' 时，选择 min{ pi / δi， pi' / δi'} 的 Oi* ． 板坯选择规则: 对 Oi* ，计算 Φj ，j∈Ψi* ; 除去 | Φj | = 0的 板 坯 外，优 先 选 择 | Φj | 小 的 Sj* ; 当 | Φj | = | Φj' |时，优先选择 min{ cj ，cj'} 的 Sj* ． 通过上述最小自由度优先策略可确定优先赋值 的变量 yij ，并得到一个可分配订单--板 坯 对( i * ， j * ) ． 这种选择策略具有计算量小，可以避免构造不 可行的部分解的优点． 3. 2. 2 最大可行量分配策略 作为针对 xij的值选择方法: 按照最先成功原则 赋值，即给变量赋予使得尽可能多的约束成立的值． 参照最先成功原则并结合板坯设计问题的特点，提 出下述的最大可行量分配策略． 即，对已选取的可 分配订单--板坯对( i，j) ，按以下规则处理． ［最大可行量分配策略］ 规则 1 若 pi≤cj ，则 xij = pi ; 规则 2 若 pi ＞ cj 和 pi － cj≥δi，则 xij = cj ; 规则 3 若 pi ＞ cj 和 pi － cj ＜ δi，则 xij = pi － δi ． 最大可行量分配策略具有以下特点: 保证解的 可行性; 每个订单--板坯对之间最多只进行一次订 单重量分配; 将变量 xij的赋值的可行域由连续转变为 离散． 这些特点为开发高效的近似算法提供了基础． 3. 3 算法描述 在上述分析的基础上，设 O'为待分配订单集 合，S'为所需板坯集合，可将本文提出的采用约束满 足技 术 最 小 化 板 坯 数 ( constraint satisfaction for minimizing slab quantity，CSMSQ) 算法描述如下． ［CSMSQ 算法］ Step 1 ( 初始化) 输入订单数据和相关参数; O' = O，S' = ，m = 0，Φj = ，Ψi = ，pi = gi 和 cj = W，i，j． Step 2 ( 变量选择: 选取可分配订单--板坯对) ·644·

第5期 张文学等：基于约束满足的板坯设计模型与求解方法 ·645· 按最小自由度优先策略从订单和板坯中选取可 法，本文给出以下两个参照算法 分配订单-板坯对(，)：若不存在(i,j),则为 (1)问题P的下界算法(lower algorithm,LA): 0新增一块板坯S,令j=j六 根据定理1，将变量x:的取值范围放宽，变为连续变 Step3(值选择：订单重量分配) 量，即不考虑订单的最小分配重量限制，则可求出问 针对已选取的(，)，按最大可行量分配策 题的下界.当然，该算法所得结果只是一个下界，并 略为x赋值；并更新0、S、mP和c分· 不一定是可行解 Step4(终止条件) (2)降序最佳适应(best fit deceasing,.BFD)算 重复Step2到Step3,直到O'=⑦：输出结果并 法：先对订单按g:%W(%为取余运算)的值降序排 终止算法.[算法结束] 序，当该值相同时按δ：降序排序；再对每个板坯进 上述CSMSQ算法是一个循环求解的过程，下面 行标记，若己经有订单被分配到该板坯则标记为1， 的定理3表明这个循环求解过程一定是收敛的 否则标记为0：接着对每个订单，检查所有标记为1 定理3 CSMSQ算法在有限步骤内收敛. 的板坯，分配到最适合该订单的板坯中，如果没有该 证明对给定的订单集合O,其总订单重量 板坯，则开启标记为0的板坯，并将该订单分配到新 开启的板坯，直到分配完所有订单.BFD算法是针 三8，为固定值根据最大可行量分配策略，在 对装箱问题行之有效的经典算法☒ CSMSQ算法的每一次循环中，订单的未分配总重量 4.2实验结果与分析 三L都以离散值p,9-8}的形式单调递减 为了评价本文提出的CSMSQ算法的有效性，根 据钢铁企业的实际生产情况，按如下方式生成实验 因此，由CSMSQ算法的终止条件O'=☑可知，其一 数据：订单重量g:∈090,300]，单位为t,其中 定在有限步骤内收敛.证毕] U[a,b]表示在区间[a,b]上的均匀分布；板坯的固 4数据实验 定重量W=28t:订单的最小分配重量为10t每一 组实验独立运行30次，记录板坯数量平均值和运行 4.1参照算法 时间平均值.实验中采用Microsoft Visual VC++ 由于目前还未能找到针对客户订单的规格需求 6.0实现算法.实验环境为Pentium4/1GHz/ 为固定值，且订单有最小分配重量限制的板坯设计 512MB/Windows XP Professional..实验结果如表1 问题的相关文献与算法，因此为了评价CSMSQ算 所示 表1实验结果 Table 1 Experimental results LA CSMSO BFD 订单数 C CT/s CC PRD/ CT/s CB PRD/% CT/s 50 357 0.01300 360 0.84 0.01143 372 4.20 0.04458 75 531 0.02133 537 1.13 0.02133 569 7.16 0.06746 100 705 0.03280 714 1.28 0.03436 753 6.81 0.06804 125 879 0.05153 891 1.37 0.05103 950 8.08 0.09903 150 1054 0.07083 1069 1.42 0.07083 1159 9.96 0.07950 175 1230 0.09583 1248 1.46 0.09686 1374 11.71 0.12493 200 1403 0.12446 1424 1.50 0.12236 1572 12.05 0.14012 注：C、C和CB分别为算法LA、CSMSQ和BFD所得板坯数：PRDC=100%×(Ce-C)/C,PRDB=100%×(CB-CL)/CL.CT是算法所 用计算时间，s 从表1的实验结果中可以得到以下几点：(1) 下界(LA的结果)的偏差很小，在上述实验中不超 针对板坯设计问题特点开发的CSMSQ算法得到的 过1.5%.这表明本文提出的关于变量选择的最小 解，无论在板坯数上还是在相对稳定性上，都明显优 自由度优先策略、关于值选择的最大可行量分配策 于BFD算法.而且随着问题规模的增大，其优势更 略有效地利用了问题的特点.(3)CSMSQ算法具有 加显著.(2)CSMSQ算法得到的板坯数量与问题的 很高的计算效率（在上述实验中，计算时间都小于

第 5 期 张文学等: 基于约束满足的板坯设计模型与求解方法 按最小自由度优先策略从订单和板坯中选取可 分配订单--板坯对( i * ，j * ) ; 若不存在( i * ，j * ) ，则为 Oi* 新增一块板坯 Sj'，令 j * = j'． Step 3 ( 值选择: 订单重量分配) 针对已选取的( i * ，j * ) ，按最大可行量分配策 略为 xi* j* 赋值; 并更新 O'、S'、m、pi* 和 cj* ． Step 4 ( 终止条件) 重复 Step 2 到 Step 3，直到 O' = ; 输出结果并 终止算法． ［算法结束］ 上述 CSMSQ 算法是一个循环求解的过程，下面 的定理 3 表明这个循环求解过程一定是收敛的． 定理 3 CSMSQ 算法在有限步骤内收敛． 证明 对给定的订单集合 O，其总订单重量 ∑ n i = 1 gi 为固 定 值． 根据最大可行量分配策略，在 CSMSQ 算法的每一次循环中，订单的未分配总重量 ∑ n i = 1 pi 都以离散值{ pi，cj ，pi － δi} 的形式单调递减． 因此，由 CSMSQ 算法的终止条件 O' = 可知，其一 定在有限步骤内收敛． ［证毕］ 4 数据实验 4. 1 参照算法 由于目前还未能找到针对客户订单的规格需求 为固定值，且订单有最小分配重量限制的板坯设计 问题的相关文献与算法，因此为了评价 CSMSQ 算 法，本文给出以下两个参照算法． ( 1) 问题 P 的下界算法( lower algorithm，LA) : 根据定理 1，将变量 xij的取值范围放宽，变为连续变 量，即不考虑订单的最小分配重量限制，则可求出问 题的下界． 当然，该算法所得结果只是一个下界，并 不一定是可行解． ( 2) 降序最佳适应( best fit deceasing，BFD) 算 法: 先对订单按 gi% W( % 为取余运算) 的值降序排 序，当该值相同时按 δi 降序排序; 再对每个板坯进 行标记，若已经有订单被分配到该板坯则标记为 1， 否则标记为 0; 接着对每个订单，检查所有标记为 1 的板坯，分配到最适合该订单的板坯中，如果没有该 板坯，则开启标记为 0 的板坯，并将该订单分配到新 开启的板坯，直到分配完所有订单． BFD 算法是针 对装箱问题行之有效的经典算法［12］． 4. 2 实验结果与分析 为了评价本文提出的 CSMSQ 算法的有效性，根 据钢铁企业的实际生产情况，按如下方式生成实验 数据: 订 单 重 量 gi ∈ U［90，300］，单 位 为 t，其 中 U［a，b］表示在区间［a，b］上的均匀分布; 板坯的固 定重量 W = 28 t; 订单的最小分配重量为 10 t． 每一 组实验独立运行 30 次，记录板坯数量平均值和运行 时间平均值． 实验中采用 Microsoft Visual VC + + 6. 0 实 现 算 法． 实 验 环 境 为 Pentium4 /1 GHz/ 512 MB /Windows XP Professional． 实验结果如表 1 所示． 表 1 实验结果 Table 1 Experimental results 订单数 LA CSMSQ BFD CL CT /s CC PRDC /% CT /s CB PRDB /% CT /s 50 357 0. 013 00 360 0. 84 0. 011 43 372 4. 20 0. 044 58 75 531 0. 021 33 537 1. 13 0. 021 33 569 7. 16 0. 067 46 100 705 0. 032 80 714 1. 28 0. 034 36 753 6. 81 0. 068 04 125 879 0. 051 53 891 1. 37 0. 051 03 950 8. 08 0. 099 03 150 1 054 0. 070 83 1 069 1. 42 0. 070 83 1 159 9. 96 0. 079 50 175 1 230 0. 095 83 1 248 1. 46 0. 096 86 1 374 11. 71 0. 124 93 200 1 403 0. 124 46 1 424 1. 50 0. 122 36 1 572 12. 05 0. 140 12 注: CL、CC 和 CB 分别为算法 LA、CSMSQ 和 BFD 所得板坯数; PRDC = 100% × ( CC － CL ) /CL，PRDB = 100% × ( CB － CL ) /CL ． CT 是算法所 用计算时间，s． 从表 1 的实验结果中可以得到以下几点: ( 1) 针对板坯设计问题特点开发的 CSMSQ 算法得到的 解，无论在板坯数上还是在相对稳定性上，都明显优 于 BFD 算法． 而且随着问题规模的增大，其优势更 加显著． ( 2) CSMSQ 算法得到的板坯数量与问题的 下界( LA 的结果) 的偏差很小，在上述实验中不超 过 1. 5% ． 这表明本文提出的关于变量选择的最小 自由度优先策略、关于值选择的最大可行量分配策 略有效地利用了问题的特点． ( 3) CSMSQ 算法具有 很高的计算效率( 在上述实验中，计算时间都小于 ·645·

·646· 北京科技大学学报 第33卷 1s),即使是对200个订单分配到1403个板坯的较 solving.Ann Oper Res,2004,130 (1-4)19 大规模的问题，计算时间仅为0.12236s,完全能够 4]Gargani A,Refalo P.An efficient model and strategy for the steel mill slab design problem//Proceedings of the 13th International 满足生产实际的需要. Conference on Principles and Practice of Constraint Programming. 5结论 Providence,2007:77 [5] Van Hentenryck P,Michel L.The steel mill slab design problem 在钢铁企业的生产过程中，板坯是衔接各个关 revisited//Proceedings of the 13th International Conference on Inte- 键工序的物流单元，也是将客户需求和工艺要求统 gration of Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems.Paris,2008:377 一起来的关键所在，合理的板坯设计对提高生产效 [6]Dawande M.Kalagnanam J,Lee H S,et al.The slab-design 率起着重要的作用.本文从钢铁企业生产管理的实 problem in the steel industry.Interfaces,2004,34(3):215 际需求出发，针对板坯的规格相同、客户订单分解过 [Denton B,Gupta D,Jawahir K.Managing increasing product va- 程中有最小重量限制的板坯设计问题，建立了以最 riety at integrated steel mills.Interfaces,2003,33(2):41 小化板坯数量为目标的约束满足模型：通过三划分 [8]Vonderembse M A,Haessler R W.A mathematical programming 问题的多项式归结，证明了该问题是强NP难的.进 approach to schedule master slab casters in the steel industry. Manage Sci,,1982,28(12):1450 而，结合问题的特殊性质提出了基于约束满足的求 Dash S,Kalagnanam J,Reddy C,et al.Production design for 解算法，并证明了该算法的收敛性.数据实验表明 plate products in the steel industry.IBM J Res Dev,2007,51(3/ 本文提出的算法具有很好的效果和能够满足实际应 4):345 用的计算效率 [10]Sun S H,Xiao Y J,Li T K.Solving the inventory matching problem of hot rolling strips based on the constraint satisfaction 参考文献 method.J Univ Sci Technol Beijing,2008,30(6):680 [Xi Y,Li T K.An optimal algorithm for slab designing of fixed (孙树慧，肖拥军，李铁克。基于约束满足方法求解热轧带钢 weight slabs.J Unig Sci Technol Beijing,2008,30(10):1179 库存匹配问题.北京科技大学学报，2008,30(6)：680) (席阳，李铁克.针对固定重量板坯的板坯设计优化算法.北京 [11]Sapena O,Onaindia E,Garrido A,et al.A distributed CSP ap- 科技大学学报，2008,30(10)：1179) proach for collaborative planning systems.Eng Appl Artif Intell, 2] Frisch A M,Miguel I,Walsh T.Modeling a steel mill slab design 2008,21(5):698 problem//Proceedings of the IJCAI1 Workshop on Modelling and [12]Johnson D S,Demers A,Ullman J D,et al.Worst-ease perform- Solring Problems with Constraints.Seattle,2001:39 ance bounds for simple one-dimensional packing algorithms.S/ [3]Hnich B,Kiziltan Z,Miguel I,et al.Hybrid modelling for robust AM J Comp,1974,3(4):299

北 京 科 技 大 学 学 报 第 33 卷 1 s) ，即使是对 200 个订单分配到 1 403 个板坯的较 大规模的问题，计算时间仅为 0. 122 36 s，完全能够 满足生产实际的需要． 5 结论 在钢铁企业的生产过程中，板坯是衔接各个关 键工序的物流单元，也是将客户需求和工艺要求统 一起来的关键所在，合理的板坯设计对提高生产效 率起着重要的作用． 本文从钢铁企业生产管理的实 际需求出发，针对板坯的规格相同、客户订单分解过 程中有最小重量限制的板坯设计问题，建立了以最 小化板坯数量为目标的约束满足模型; 通过三划分 问题的多项式归结，证明了该问题是强 NP 难的． 进 而，结合问题的特殊性质提出了基于约束满足的求 解算法，并证明了该算法的收敛性． 数据实验表明 本文提出的算法具有很好的效果和能够满足实际应 用的计算效率． 参 考 文 献 ［1］ Xi Y，Li T K． An optimal algorithm for slab designing of fixed weight slabs． J Univ Sci Technol Beijing，2008，30( 10) : 1179 ( 席阳，李铁克． 针对固定重量板坯的板坯设计优化算法． 北京 科技大学学报，2008，30( 10) : 1179) ［2］ Frisch A M，Miguel I，Walsh T． Modeling a steel mill slab design problem/ /Proceedings of the IJCAI-01 Workshop on Modelling and Solving Problems with Constraints． Seattle，2001: 39 ［3］ Hnich B，Kiziltan Z，Miguel I，et al． Hybrid modelling for robust solving． Ann Oper Res，2004，130( 1-4) : 19 ［4］ Gargani A，Refalo P． An efficient model and strategy for the steel mill slab design problem/ /Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming． Providence，2007: 77 ［5］ Van Hentenryck P，Michel L． The steel mill slab design problem revisited / /Proceedings of the 13th International Conference on Inte￾gration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems． Paris，2008: 377 ［6］ Dawande M，Kalagnanam J，Lee H S，et al． The slab-design problem in the steel industry． Interfaces，2004，34( 3) : 215 ［7］ Denton B，Gupta D，Jawahir K． Managing increasing product va￾riety at integrated steel mills． Interfaces，2003，33( 2) : 41 ［8］ Vonderembse M A，Haessler R W． A mathematical programming approach to schedule master slab casters in the steel industry． Manage Sci，1982，28( 12) : 1450 ［9］ Dash S，Kalagnanam J，Reddy C，et al． Production design for plate products in the steel industry． IBM J Res Dev，2007，51( 3 / 4) : 345 ［10］ Sun S H，Xiao Y J，Li T K． Solving the inventory matching problem of hot rolling strips based on the constraint satisfaction method． J Univ Sci Technol Beijing，2008，30( 6) : 680 ( 孙树慧，肖拥军，李铁克． 基于约束满足方法求解热轧带钢 库存匹配问题． 北京科技大学学报，2008，30( 6) : 680) ［11］ Sapena O，Onaindia E，Garrido A，et al． A distributed CSP ap￾proach for collaborative planning systems． Eng Appl Artif Intell， 2008，21( 5) : 698 ［12］ Johnson D S，Demers A，Ullman J D，et al． Worst-case perform￾ance bounds for simple one-dimensional packing algorithms． SI￾AM J Comput，1974，3( 4) : 299 ·646·