李铁克等：单一尺寸圆坯的无缝钢管坯料设计模型与算法 ·641· 问题的一般性描述并且建立了混合整数规划模型.针 6]Hentenryek P V,Michel L.The steel mill slab design problem re- 对原料库中只存在一种尺寸圆坯的常见情况，证明了 visited Integration of Al and OR Techniques in Constraint Pro- 此时最小化圆坯数量和最小化圆坯总剩余量具有一致 gramming for Combinatorial Optimization Problems.Berlin,2008: 377 性，从而简化了问题模型.结合问题特点，本文提出了 Zhang W X,Li T K.Modelling and algorithm for the slab desig- 基于贪婪策略的两阶段启发式贪婪策略的启发式算 ning problem based on constraint satisfaction.Unin Sci Technol 法，并且证明算法是收敛的.与传统贪婪策略单一目 Beijing,2011,33(5):641 标不同，贪婪策略的启发式算法在两阶段选取了不同 (张文学，李铁克.基于约束满足的板坯设计模型与求解方 的贪婪目标，并以较低的计算复杂度设置了寻优路径. 法.北京科技大学学报，2011,33(5)：641) 最后，通过实际生产数据和大量仿真数据的验证，贪婪 [8]Li Y N,Tang L X,Meng Y,et al.Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel en- 策略的启发式算法明显优于传统降序最佳适应算法. terprises.Control Decis,2015,30(1):17 本文研究成果不仅为无缝钢管坯料设计问题的进一步 (吕亚娜，唐立新，孟盈，等.钢铁企业板坯动态分配问题的 研究奠定了基础，而且本文提出的数学模型可以被用 建模与分散搜索算法求解.控制与决策，2015,30(1)：17) 于描述有最小装箱量的一维装箱问题，可以应用到物 9]Tang L X,Luo J X,Liu J Y.Modelling and a tabu search solu- 流、仓储、交通运输等各个领域. tion for the slab reallocation problem in the steel industry.Int Prod Res,2013,51(14):4405 参考文献 [10]Rohlfshagen P,Bullinaria J A.Nature inspired genetic algo- [Frisch A M,Miguel I,Walsh T.Modeling a steel mill slab design rithms for hard packing problems.Ann Oper Res,2010,179 problem /Proceedings of the IJCAl-01 Workshop on Modeling (1):393 and Solving Problems with Constraints.Seattle,2001:39 [11]Brusco M J.Kohn H F,Steinley D.Exact and approximate 2]Hnich B,Kiziltan Z,Miguel I,et al.Hybrid modeling for robust methods for a one-dimensional minimax bin-packing problem solving.Ann Oper Res,2004,130(1):19 Ann0 per Res,2013,206(1):611 Xi Y,Li T K.An optimal algorithm for slab designing of fixed [12]Crainic T G,Perboli G,Rei W.et al.Efficient lower bounds weight slabs.J Univ Sci Technol Beijing,2008,30(10):1179 and heuristics for the variable cost and size bin packing problem. (席阳，李铁克.针对固定重量板坯的板坯设计优化算法.北 Comput0 per Res,2011,38(11）:1474 京科技大学学报，2008,30(10)：1179) D3] Hemmelmayr V,Schmid V,Blum C.Variable neighborhood 4]Dawande M,Kalagnanam J,Lee H S,et al.The slab-design search for the variable sized bin packing problem.Comput Oper problem in the steel industry.Interfaces,2004,34(3):215 Res,2012,39(5):1097 5]Gargani A.Refalo P.An efficient model and strategy for the steel 04] Pereira J.Procedures for the bin packing problem with preced- mill slab design problem Proceedings of the 13th International ence constraints.Eur J Oper Res,2016,250(3):794 Conference on Principles and Practice of Constraint Programming [15]Gualandi S,Malucelli F.Constraint programming-based column Berlin,2007:77 generation.40R Q J Oper Res,2009,7(2):113李铁克等: 单一尺寸圆坯的无缝钢管坯料设计模型与算法 问题的一般性描述并且建立了混合整数规划模型． 针 对原料库中只存在一种尺寸圆坯的常见情况，证明了 此时最小化圆坯数量和最小化圆坯总剩余量具有一致 性，从而简化了问题模型． 结合问题特点，本文提出了 基于贪婪策略的两阶段启发式贪婪策略的启发式算 法，并且证明算法是收敛的． 与传统贪婪策略单一目 标不同，贪婪策略的启发式算法在两阶段选取了不同 的贪婪目标，并以较低的计算复杂度设置了寻优路径． 最后，通过实际生产数据和大量仿真数据的验证，贪婪 策略的启发式算法明显优于传统降序最佳适应算法． 本文研究成果不仅为无缝钢管坯料设计问题的进一步 研究奠定了基础，而且本文提出的数学模型可以被用 于描述有最小装箱量的一维装箱问题，可以应用到物 流、仓储、交通运输等各个领域． 参 考 文 献 ［1］ Frisch A M，Miguel I，Walsh T． Modeling a steel mill slab design problem / / Proceedings of the IJCAI--01 Workshop on Modeling and Solving Problems with Constraints． Seattle，2001: 39 ［2］ Hnich B，Kiziltan Z，Miguel I，et al． Hybrid modeling for robust solving． Ann Oper Ｒes，2004，130( 1) : 19 ［3］ 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) ［4］ Dawande M，Kalagnanam J，Lee H S，et al． The slab- design problem in the steel industry． Interfaces，2004，34( 3) : 215 ［5］ Gargani A，Ｒefalo 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． Berlin，2007: 77 ［6］ Hentenryck P V，Michel L． The steel mill slab design problem re￾visited / / Integration of AI and OＲ Techniques in Constraint Pro￾gramming for Combinatorial Optimization Problems． Berlin，2008: 377 ［7］ Zhang W X，Li T K． Modelling and algorithm for the slab desig￾ning problem based on constraint satisfaction． J Univ Sci Technol Beijing，2011，33( 5) : 641 ( 张文学，李铁克． 基于约束满足的板坯设计模型与求解方 法． 北京科技大学学报，2011，33( 5) : 641) ［8］ Lü Y N，Tang L X，Meng Y，et al． Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel en￾terprises． Control Decis，2015，30( 1) : 17 ( 吕亚娜，唐立新，孟盈，等． 钢铁企业板坯动态分配问题的 建模与分散搜索算法求解． 控制与决策，2015，30( 1) : 17) ［9］ Tang L X，Luo J X，Liu J Y． Modelling and a tabu search solu￾tion for the slab reallocation problem in the steel industry． Int J Prod Ｒes，2013，51( 14) : 4405 ［10］ Ｒohlfshagen P，Bullinaria J A． Nature inspired genetic algo￾rithms for hard packing problems． Ann Oper Ｒes，2010，179 ( 1) : 393 ［11］ Brusco M J，Khn H F，Steinley D． Exact and approximate methods for a one-dimensional minimax bin-packing problem． Ann Oper Ｒes，2013，206( 1) : 611 ［12］ Crainic T G，Perboli G，Ｒei W，et al． Efficient lower bounds and heuristics for the variable cost and size bin packing problem． Comput Oper Ｒes，2011，38( 11) : 1474 ［13］ Hemmelmayr V，Schmid V，Blum C． Variable neighborhood search for the variable sized bin packing problem． Comput Oper Ｒes，2012，39( 5) : 1097 ［14］ Pereira J． Procedures for the bin packing problem with preced￾ence constraints． Eur J Oper Ｒes，2016，250( 3) : 794 ［15］ Gualandi S，Malucelli F． Constraint programming-based column generation． 4OＲ Q J Oper Ｒes，2009，7( 2) : 113 · 146 ·