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