·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·