中厚板考虑母板和板坯规格不确定性的下料问题建模及求解
|
摘要
针对中厚板面向订单的生产是先设计母板及板坯后实施的生产组织模式,研究综合考虑母板、板坯允许的多种断面与长度规格及其转换关系的母板板坯集成优化设计问题,将其归结为一种同时对母板、板坯断面及长度规格不确定性进行决策的下料问题。以最小化无订单余材和热轧切边等加工过程材料损失为目标,将板坯的断面与长度设计柔性转化为模型的约束条件,建立非线性混合整数规划模型;设计结合禁忌搜索与列生成技术的混合优化求解算法:禁忌搜索编码采用一对多的映射方式降低搜索空间维数,以进行板坯断面的优化选择;解码时对母板、板坯长度和下料方法进行设计,子问题为考虑长度柔性和材料加工损耗的母板设计问题,通过设计改进的列生成方法求解;针对问题特征设计了适用的邻域结构、禁忌对象等算法要素。基于某钢铁企业生产数据进行案例计算,结果表明了所提模型及求解方法的可行性和有效性。
Aiming at the organization mode of designing mother plates and slabs before the production implementation in the demand-oriented production of medium and heavy plate,the integrated optimal design problem of mother plate and slab was investigated,in which flexibility in cross section and length of mother plate and slab and transformation relationship between mother plate and slab were taken into consideration together.It was modelled and solved as a cutting stock problem by considering making decisions on cross section and length of mother plate and slab simultaneously.The flexibility was transformed into constraints and a non linear mixed integer programming model with an objective minimizing the total quantity of surplus material and material loss in manufacturing process was built.A hybrid optimal algorithm combined tabu search and column generation was employed:tabu search was mainly used to deal with optimal choice of slab cross section.A one-to-many encoding scheme was adopted to reduce the dimensions of search space;a code string was decoded to make decisions on the length of mother plates and slabs and cutting patterns.A sub-problem was a mother plate design problem considering length flexibility and material processing loss and could be solved with a modified algorithm based on column generation.Applicable essential factors of tabu search such as neighborhood structure and tabu object were designed according to problem characteristics.The case experiments with the data instance from a steel plant showed that the modeling and solving method was feasible and effective.
Aiming at the organization mode of designing mother plates and slabs before the production implementation in the demand-oriented production of medium and heavy plate,the integrated optimal design problem of mother plate and slab was investigated,in which flexibility in cross section and length of mother plate and slab and transformation relationship between mother plate and slab were taken into consideration together.It was modelled and solved as a cutting stock problem by considering making decisions on cross section and length of mother plate and slab simultaneously.The flexibility was transformed into constraints and a non linear mixed integer programming model with an objective minimizing the total quantity of surplus material and material loss in manufacturing process was built.A hybrid optimal algorithm combined tabu search and column generation was employed:tabu search was mainly used to deal with optimal choice of slab cross section.A one-to-many encoding scheme was adopted to reduce the dimensions of search space;a code string was decoded to make decisions on the length of mother plates and slabs and cutting patterns.A sub-problem was a mother plate design problem considering length flexibility and material processing loss and could be solved with a modified algorithm based on column generation.Applicable essential factors of tabu search such as neighborhood structure and tabu object were designed according to problem characteristics.The case experiments with the data instance from a steel plant showed that the modeling and solving method was feasible and effective.
引文
[1]ZHENG Zhong,LONG Jianyu,GAO Xiaoqiang,et al.Present situation and prospect of production control technology focusing on planning and scheduling in iron and steel enterprise[J].Computer Integrated Manufacturing Systems,2014,20(11):2660-2674(in Chinese).[郑忠,龙建宇,高小强,等.钢铁企业以计划调度为核心的生产运行控制技术现状与展望[J].计算机集成制造系统,2014,20(11):2660-2674.]
[2]GILMORE P C,GOMORY R E.A linear programming approach to the cutting-stock problem[J].Operations Research,1961,9(6):849-859.
[3]WASCHER G,HAUBNER H,SCHUMANN H.An improved typology of cutting and packing problems[J].European Journal of Operational Research.2007,183(3):1109-1130.
[4]LINS L,LINS S,MORABITO R.An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an ncontainer[J].European Journal of Operational Research,2002,141(2):421-439.
[5]SCHEITHAUER G,TERNO J,MLLER A,et al.Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm[J].Journal of the Operational Research Society,2001,52(12):1390-1401.
[6]POLDI K C,ARENALES M N.Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths[J].Computers&Operations Research,2009,36(6):2074-2081.
[7]YAN Chunping,SONG Tianfeng,LIU Fei.Manufacturability-oriented one-dimensional cutting-stock problem under complex constraints status[J].Computer Integrated Manufacturing Systems,2010,16(1):195-201(in Chinese).[阎春平,宋天峰,刘飞.面向可加工性的复杂约束状态下一维优化下料[J].计算机集成制造系统,2010,16(1):195-201.]
[8]CAO Dayong,YANG Mei,KOTOV V M,et al.Two-stage heuristic algorithm for two-dimensional guillotine bin packing problem[J].Computer Integrated Manufacturing Systems,2012,18(9):1954-1963(in Chinese).[曹大勇,杨梅,科托夫·弗拉基米尔·米哈伊拉维奇,等.二维一刀切装箱问题的两阶段启发式算法[J].计算机集成制造系统,2012,18(9):1954-1963.]
[9]ZHANG Fan,LIU Qiang,ZHANG Hao,et al.Packing optimization of rectangle workpieces oriented to variable-sized bin[J].Computer Integrated Manufacturing Systems,2015,21(11):2921-2928(in Chinese).[张帆,刘强,张浩,等.面向多规格板材的矩形工件排样优化方法[J].计算机集成制造系统,2015,21(11):2921-2928.]
[10]GE Peng,QIU Yanqing,LIU Zhusheng,et al.Optimized binary tree packing of guillotine problem[J].Computer Integrated Manufacturing Systems,2011,17(2):329-337(in Chinese).[戈鹏,邱厌庆,刘柱胜,等.一刀切问题的优化二叉树排样[J].计算机集成制造系统,2011,17(2):329-337.]
[11]DASH S,KALAGNANAM J,REDDY C,et al.Production design for plate products in the steel industry[J].IBM Journal of Research&Development,2007,51(3):345-362.
[12]WY J,KIM B.Two-staged guillotine cut,two-dimensional bin packing optimisation with flexible bin size for steel mother plate design[J].International Journal of Production Research,2010,48(22):6799-6820.
[13]LYU Yana,TANG Lixin,MENG Ying,et al.Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel enterprises[J].Control and Decision,2015,30(1):17-24(in Chinese).[吕亚娜,唐立新,孟盈,等.钢铁企业板坯动态分配问题的建模与分散搜索算法求解[J].控制与决策,2015,30(1):17-24.]
[14]WASCHER G,GAU T.Heuristics for the integer one-dimensional cutting stock problem:A computational study[J].OR Spektrum,1996,18(3):131-144.
[15]KOTHARI R,GHOSH D.Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods[J].European Journal of Operational Research,2013,224(1):93-100.
[2]GILMORE P C,GOMORY R E.A linear programming approach to the cutting-stock problem[J].Operations Research,1961,9(6):849-859.
[3]WASCHER G,HAUBNER H,SCHUMANN H.An improved typology of cutting and packing problems[J].European Journal of Operational Research.2007,183(3):1109-1130.
[4]LINS L,LINS S,MORABITO R.An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an ncontainer[J].European Journal of Operational Research,2002,141(2):421-439.
[5]SCHEITHAUER G,TERNO J,MLLER A,et al.Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm[J].Journal of the Operational Research Society,2001,52(12):1390-1401.
[6]POLDI K C,ARENALES M N.Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths[J].Computers&Operations Research,2009,36(6):2074-2081.
[7]YAN Chunping,SONG Tianfeng,LIU Fei.Manufacturability-oriented one-dimensional cutting-stock problem under complex constraints status[J].Computer Integrated Manufacturing Systems,2010,16(1):195-201(in Chinese).[阎春平,宋天峰,刘飞.面向可加工性的复杂约束状态下一维优化下料[J].计算机集成制造系统,2010,16(1):195-201.]
[8]CAO Dayong,YANG Mei,KOTOV V M,et al.Two-stage heuristic algorithm for two-dimensional guillotine bin packing problem[J].Computer Integrated Manufacturing Systems,2012,18(9):1954-1963(in Chinese).[曹大勇,杨梅,科托夫·弗拉基米尔·米哈伊拉维奇,等.二维一刀切装箱问题的两阶段启发式算法[J].计算机集成制造系统,2012,18(9):1954-1963.]
[9]ZHANG Fan,LIU Qiang,ZHANG Hao,et al.Packing optimization of rectangle workpieces oriented to variable-sized bin[J].Computer Integrated Manufacturing Systems,2015,21(11):2921-2928(in Chinese).[张帆,刘强,张浩,等.面向多规格板材的矩形工件排样优化方法[J].计算机集成制造系统,2015,21(11):2921-2928.]
[10]GE Peng,QIU Yanqing,LIU Zhusheng,et al.Optimized binary tree packing of guillotine problem[J].Computer Integrated Manufacturing Systems,2011,17(2):329-337(in Chinese).[戈鹏,邱厌庆,刘柱胜,等.一刀切问题的优化二叉树排样[J].计算机集成制造系统,2011,17(2):329-337.]
[11]DASH S,KALAGNANAM J,REDDY C,et al.Production design for plate products in the steel industry[J].IBM Journal of Research&Development,2007,51(3):345-362.
[12]WY J,KIM B.Two-staged guillotine cut,two-dimensional bin packing optimisation with flexible bin size for steel mother plate design[J].International Journal of Production Research,2010,48(22):6799-6820.
[13]LYU Yana,TANG Lixin,MENG Ying,et al.Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel enterprises[J].Control and Decision,2015,30(1):17-24(in Chinese).[吕亚娜,唐立新,孟盈,等.钢铁企业板坯动态分配问题的建模与分散搜索算法求解[J].控制与决策,2015,30(1):17-24.]
[14]WASCHER G,GAU T.Heuristics for the integer one-dimensional cutting stock problem:A computational study[J].OR Spektrum,1996,18(3):131-144.
[15]KOTHARI R,GHOSH D.Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods[J].European Journal of Operational Research,2013,224(1):93-100.