面向可制造性的条材优化下料技术的研究与应用
|
摘要
条材优化下料技术广泛应用于机械、建筑等行业的下料过程中,是企业提高原材料利用率、降低资源消耗的重要手段之一。目前国内外对条材优化下料问题大多从算法改进角度进行研究以期提高材料利用率,尚未系统地研究下料过程中原材料采购、优化排样及下料切割等各环节的特征及其相互影响关系,导致得到的下料方案可制造性差,影响下料切割的便捷性,增加了人力资源、能源的消耗。本文围绕企业优化下料存在的问题,对既维持高的原材料利用率又使下料方案可制造性好的条材优化下料方法进行了研究,并开发了面向可制造性的条材优化下料系统。
首先分析了国内外条材优化下料技术的研究现状,针对现有研究的不足和企业优化下料存在的问题,研究了优化下料问题各环节复杂约束状态,给出了复杂约束状态下优化下料问题的求解策略,提出了一种以综合资源消耗最小为目标函数的复杂约束状态下优化下料问题的简化数学模型;分析了条材优化下料问题的主要约束状态并给出了各约束状态的处理方法。
然后针对面向可制造性的条材优化下料关键技术进行了研究。分析了条材优化下料算法,构造了条材优化下料问题的列生成算法;研究了条材优化下料问题的可制造性,给出了下料方案可制造性评价体系,提出了一种下料方案可制造性评价方法;提出非定长优化和定长优化相结合的两阶段一维优化下料方法,首先采用非定长优化方式,充分利用零件和原材料的尺寸关系,以下料方案的可制造性好和高的原材料利用率为目标,由零件尺寸反推出适当的原材料尺寸,向厂家定购,完成大部分的零件下料。然后采用定长优化方式,对未下完的剩余零件以下料方案的高原材料利用率为目标完成最终下料;针对两阶段一维优化下料方法设计了一种基于整数分解的两阶段列生成算法。
最后,设计了面向可制造性的条材优化下料系统的工作流程和体系结构,划分了功能模块,开发了应用系统。该系统在数十家企业得到应用,取得了良好的应用效果。
One-dimensional cutting stock technology, as one important method to improve material utilization ratio and to reduce resource consumption, is now widely used in industries of mechanical and building. Although, most study on the one-dimensional cutting stock problem are concentrating only on high material utilization ratio by means of algorithm improvement rather than holistic application effect by studying characteristics and international relationship of stages of material procurement, optimization calculation and material cut systematically, which leads to poor manufacturability of the cutting plan and increase of resources and energy consumption. In this paper, an optimization method aiming at high material utilization ratio and fine manufacturability will be studied and a one-dimensional optimization system oriented to manufacturability will also be developed.
Firstly, research status of one-dimensional cutting stock problem at home and abroad was analyzed. Complex constraint status of cutting stock problem was studied according to insufficiency of the research and application and a method for cutting stock problem under complex constraint status was given. Then, a simplified mathematical model with objective function of minimal comprehensive resources consumption was proposed. For one-dimensional cutting stock problem, the constraint status was analyzed and processing methods were put forward.
Secondly, key technologies of one-dimensional cutting stock problem oriented to manufacturability were studied. Mathematical algorithm for one-dimensional cutting stock problem was analyzed and a kind of column generation algorithm was constructed. Then, manufacturability of one-dimensional cutting stock problem was researched, manufacturability evaluation system of cutting plan was established and an evaluation method was also proposed. A two-stage optimization method combined non-fixed-length optimization and fixed-length optimization for one-dimensional cutting stock problem was put forward. In the non-fixed-length optimization stage which aims at fine manufacturability, characteristics such as sizes of parts and raw material are main basis of the inverse calculation of optimized raw material sizes. When the optimized sizes of raw material were determined, the demand quantity can also be calculated and most of the blanking task would be finished in this stage. In the fixed-length optimization stage, residual blanking task was dealt with by some mathematical algorithm with objective of high material utilization ratio. At last, a two-stage column generation algorithm based on integer factorization was also designed.
Finally, working flow and architecture of the one-dimensional cutting stock optimization system oriented to manufacturability were designed, the function module was given and the software system was developed eventually. This system aims at high material utilization ratio and fine manufacturability of cutting plan, practice shows that it is in accordance with enterprise requirement.
首先分析了国内外条材优化下料技术的研究现状,针对现有研究的不足和企业优化下料存在的问题,研究了优化下料问题各环节复杂约束状态,给出了复杂约束状态下优化下料问题的求解策略,提出了一种以综合资源消耗最小为目标函数的复杂约束状态下优化下料问题的简化数学模型;分析了条材优化下料问题的主要约束状态并给出了各约束状态的处理方法。
然后针对面向可制造性的条材优化下料关键技术进行了研究。分析了条材优化下料算法,构造了条材优化下料问题的列生成算法;研究了条材优化下料问题的可制造性,给出了下料方案可制造性评价体系,提出了一种下料方案可制造性评价方法;提出非定长优化和定长优化相结合的两阶段一维优化下料方法,首先采用非定长优化方式,充分利用零件和原材料的尺寸关系,以下料方案的可制造性好和高的原材料利用率为目标,由零件尺寸反推出适当的原材料尺寸,向厂家定购,完成大部分的零件下料。然后采用定长优化方式,对未下完的剩余零件以下料方案的高原材料利用率为目标完成最终下料;针对两阶段一维优化下料方法设计了一种基于整数分解的两阶段列生成算法。
最后,设计了面向可制造性的条材优化下料系统的工作流程和体系结构,划分了功能模块,开发了应用系统。该系统在数十家企业得到应用,取得了良好的应用效果。
One-dimensional cutting stock technology, as one important method to improve material utilization ratio and to reduce resource consumption, is now widely used in industries of mechanical and building. Although, most study on the one-dimensional cutting stock problem are concentrating only on high material utilization ratio by means of algorithm improvement rather than holistic application effect by studying characteristics and international relationship of stages of material procurement, optimization calculation and material cut systematically, which leads to poor manufacturability of the cutting plan and increase of resources and energy consumption. In this paper, an optimization method aiming at high material utilization ratio and fine manufacturability will be studied and a one-dimensional optimization system oriented to manufacturability will also be developed.
Firstly, research status of one-dimensional cutting stock problem at home and abroad was analyzed. Complex constraint status of cutting stock problem was studied according to insufficiency of the research and application and a method for cutting stock problem under complex constraint status was given. Then, a simplified mathematical model with objective function of minimal comprehensive resources consumption was proposed. For one-dimensional cutting stock problem, the constraint status was analyzed and processing methods were put forward.
Secondly, key technologies of one-dimensional cutting stock problem oriented to manufacturability were studied. Mathematical algorithm for one-dimensional cutting stock problem was analyzed and a kind of column generation algorithm was constructed. Then, manufacturability of one-dimensional cutting stock problem was researched, manufacturability evaluation system of cutting plan was established and an evaluation method was also proposed. A two-stage optimization method combined non-fixed-length optimization and fixed-length optimization for one-dimensional cutting stock problem was put forward. In the non-fixed-length optimization stage which aims at fine manufacturability, characteristics such as sizes of parts and raw material are main basis of the inverse calculation of optimized raw material sizes. When the optimized sizes of raw material were determined, the demand quantity can also be calculated and most of the blanking task would be finished in this stage. In the fixed-length optimization stage, residual blanking task was dealt with by some mathematical algorithm with objective of high material utilization ratio. At last, a two-stage column generation algorithm based on integer factorization was also designed.
Finally, working flow and architecture of the one-dimensional cutting stock optimization system oriented to manufacturability were designed, the function module was given and the software system was developed eventually. This system aims at high material utilization ratio and fine manufacturability of cutting plan, practice shows that it is in accordance with enterprise requirement.
引文
[1]阎春平,刘飞,刘颖,等.基于ASP模式的多软件协同优化下料方法及其实现技术[J].中国机械工程, 2002, 13(24):2144-2147.
[2]阎春平,刘飞.基于网格的远程优化下料系统研究[J].计算机工程与应用, 2008, 44(14) :242-245.
[3]刘飞,张晓冬,杨丹.制造系统工程[M].北京:国防工业出版社, 2000.
[4] Sandhu R, Coyne E J, Feinstein H L. Role based access control models[J]. IEEE Computer, 1996, 29 (2) : 38-46.
[5]熊善清,张颖江.基于角色的访问控制模型分析及实现研究[J].武汉理工大学学报(信息与管理工程版), 2006, 28 (2):29-35.
[6]陈凤珍,洪帆.基于任务的访问控制(TBAC)模型[J].小型微型计算机系统, 2003, 24 (3): 621-624.
[7]贵经网.广西工业重点产业发展“十一五”规划[EB/OL]. http://www.gxi.gov.cn/fzgh/fzgh_zcwj/fzgh_zcwj_gx/200710/t20071015_12881.htm, 2007-10-15.
[8]万芳.“绿色造船”离中国造船业有多远[N].中国水运报, 2008, 1-21.
[9]聪慧网.多方面解答新政下钢铁贸易应怎么做[EB/OL]. http://info.steel.hc360.com/2005/09/29141517452.shtml, 2005-09-29.
[10]贾志欣.排样问题的分类研究[J].锻压技术, 2004, 4: 8-10.
[11]李友如.面向工程项目型制造企业的板材下料系统的研究与应用[D].重庆:重庆大学.硕士学位论文, 2003.
[12]卫丽敏.面向纸质品包装材料加工企业的优化下料问题研究[D].广东:暨南大学.硕士学位论文, 2006.
[13] Gilmore P.C, Gomory R.E. A Linear programming approach to the cutting stock problem[J]. Operations Research, 1961, 9: 849-859.
[14] Gilmore P.C, Gomory R.E. A Linear programming approach to the cutting stock problem-partⅡ[J].Operations Research, 1963, 11: 863-888.
[15] Gilmore P.C, Gomory R.E. Multistage cutting stock problems of two and more dimensions[J]. Operations Research,1965, 13: 94-120.
[16] Gilmore P.C, Gomory R.E. The theory and computation of Knapsack functions[J]. Operations Research, 1996, 14: 849-859.
[17] Ghodsi R., Sassani F. Online cutting stock optimization with prioritized orders[J]. AssemblyAutomation, 2005, 25(1): 66-72.
[18] Lee Jon. In situ column generation for a cutting-stock problem[J]. Computers and Operations Research, 2007, 34(8): 2345-2358.
[19] Alves Claudio, Valerio de Carvalho J.M. A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem[J]. Computers and Operations Research, 2008, 35(4): 1315-1328.
[20] Fang Hui, Yin Guofu, Li Haiqing and Peng Biyou. Application of integer coding accelerating genetic algorithm in rectangular cutting stock problem[J]. Chinese Journal of Mechanical Engineering (English Edition), 2006, 19(3): 335-339.
[21]李培勇,王呈方,茅云生.基于基因群体的一维优化下料[J].上海交通大学学报, 2006, 40(6): 1015-1018.
[22] Yanasse Horacio Hideki, Limeira Marcelo Seraiva. A hybrid heuristic to reduce the number of different patterns in cutting stock problems[J]. Computers and Operations Research, 2006, 33(9): 2744-2756.
[23] Trkman Peter, Gradisar Miro Source. One-dimensional cutting stock optimization in consecutive time periods[J]. European Journal of Operational Research, 2007, 179(2): 291-301.
[24] Gramani Maria Cristina N., Franca Paulo M. The combined cutting stock and lot-sizing problem in industrial processes[J]. European Journal of Operational Research, 2006, 174(1):509-521.
[25] Song X., Chu C.B., Nie Y.Y. and Bennell J.A. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem[J]. European Journal of Operational Research, 2006, 175(3): 1870-1889.
[26]尹震飚,阎春平,刘飞,等.基于零件相似性特征的大规模下料分组优化方法[J].计算机辅助设计与图形学学报, 2007, 19(11): 1442-1446.
[27]阎春平,刘飞,刘希刚.基于Internet的二维优化下料方法及其实现技术[J].重庆大学学报(自然科学版), 2001, 24(5): 1-4.
[28]朱波,阎春平,刘飞,等.一种基于Web Service的网络化优化下料系统[J].重庆大学学报(自然科学版), 2005, 28(1): 19-23.
[29]冯培恩,邱清盈,潘双夏,等.机械广义优化设计的理论框架[J].中国机械工程, 2000, 11(1-2): 126-129.
[30]王颖,周骥平,魏孝斌.虚拟设计在产品广义优化设计中的应用[J].机电产品开发与创新, 2006, 19(2): 60-62.
[31]徐有忠,潘双夏,邱清盈.面向广义优化的参数化设计方法研究[J].中国机械工程, 2003,14(17): 1485-1488.
[32] Heldenrelch P. Design for manufacturability[J]. Quality Progress, 1988, (3): 41-44.
[33] Tanner J P. Manufacturing engineering[M]. Florida: MarcelDekker Inc, 1991.
[34] Shah J J. A framework for manufacturaility evaluation in a feature based CAD system[C]. In: Arozona State university eds. Proc of NSF Design and Manufacturing Systems Conference. Arozona: Arozona State University Publisher, 1990: 61-66.
[35] Shankar S R, Jansson D G. A generalized methodology for evaluating manufacturabilty[C]. In: Parsaei H R, Sullivan W G, eds. Concurrent Engineering. London: Chapman &Hall, 1993: 248-263.
[36] Chu X, Holm H. Product manufacturing control for concurrent engineering[J]. Computers inIndustry, 1994, 24(6) : 29-38
[37] Suh N P, Rinderle J R. Qualitative and quantitative use of design and manufacturing axioms[J]. Annals of the CIRP, 1982, 31 (1) : 333-338
[38]宋玉银,肖亦辉,成烨,等.产品可制造性及评价方法的研究[J].清华大学学报(自然科学版), 1998, 38(7): 111-114.
[39]王润孝,盛义军,姜小鹏,等.产品可制造性评价方法研究.先进制造技术, 2006, 35(3): 31-34.
[40]吴瑞荣,张玉云,王先逵,等.面向对象的可制造性评价系统.清华大学学报(自然科学版), 1998, 38(2): 72-75.
[41] Dagli C H. A simulated annealing approach for solving stock problem[J]. Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 1990: 221-223.
[42] Dagli C H, Poshyannda P. New approaches to nesting rectangular patterns [J]. Journal of Intelligent Manufacturing, 1997, (8): 177-190.
[43]薛声家,左小德.管理运筹学[M].暨南大学出版社, 2000.
[44] D Sculli. A stochastic cutting stock procedure: cutting rolls of insulating tape[J]. Management Science, 1981, 27(8): 946-952.
[45] Gau T, Wascher G. A problem generator for the standard one-dimensional cutting stock problem [J]. European Journal of Operational Research, 1995, (84): 572-579.
[46]王伯成,施锦丹,王凯.粒子群优化算法的研究现状与发展概述[J].电视技术, 2008, 48(5): 7-11.
[47]沈显君,杨进才,应伟勤,等.一维下料问题的自适应广义粒子群优化求解[J].华南理工大学学报(自然科学版), 2007, 35(9): 113-117.
[48] Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem [J]. Operations Research, 1961, 9(5): 849-859
[49]高尚,杨静宇,吴小俊,等.基于模拟退火算法思想的粒子群优化算法[J].计算机应用与软件, 2005, 22(1): 103-104.
[50]李宁,孙德宝,岑翼则,等.带变异算子的粒子群优化算法[J].计算机工程与应用, 2004, 40 (17): 12-14.
[51]肖东喜,朱金福.飞机排班中航班环的动态构建方法[J].系统工程, 2007, 25(11): 19-25.
[52]刘希刚.多原材二维Guillotine优化下料技术及应用系统研究[D].重庆:重庆大学.硕士学位论文, 2001.
[53]朱波.面向数控下料加工的集成化板材优化下料系统的研究与开发[D].重庆:重庆大学.硕士学位论文, 2005.
[54]龚坚,刘飞,徐宗俊.定长条材优化下料的实用算法研究[J].重庆大学学报(自然科学版), 1997, 20(1): 92-97.
[55]尹震彪.面向多原料多零件的大规模优化下料技术研究[D].重庆:重庆大学.硕士学位论文, 2007.
[2]阎春平,刘飞.基于网格的远程优化下料系统研究[J].计算机工程与应用, 2008, 44(14) :242-245.
[3]刘飞,张晓冬,杨丹.制造系统工程[M].北京:国防工业出版社, 2000.
[4] Sandhu R, Coyne E J, Feinstein H L. Role based access control models[J]. IEEE Computer, 1996, 29 (2) : 38-46.
[5]熊善清,张颖江.基于角色的访问控制模型分析及实现研究[J].武汉理工大学学报(信息与管理工程版), 2006, 28 (2):29-35.
[6]陈凤珍,洪帆.基于任务的访问控制(TBAC)模型[J].小型微型计算机系统, 2003, 24 (3): 621-624.
[7]贵经网.广西工业重点产业发展“十一五”规划[EB/OL]. http://www.gxi.gov.cn/fzgh/fzgh_zcwj/fzgh_zcwj_gx/200710/t20071015_12881.htm, 2007-10-15.
[8]万芳.“绿色造船”离中国造船业有多远[N].中国水运报, 2008, 1-21.
[9]聪慧网.多方面解答新政下钢铁贸易应怎么做[EB/OL]. http://info.steel.hc360.com/2005/09/29141517452.shtml, 2005-09-29.
[10]贾志欣.排样问题的分类研究[J].锻压技术, 2004, 4: 8-10.
[11]李友如.面向工程项目型制造企业的板材下料系统的研究与应用[D].重庆:重庆大学.硕士学位论文, 2003.
[12]卫丽敏.面向纸质品包装材料加工企业的优化下料问题研究[D].广东:暨南大学.硕士学位论文, 2006.
[13] Gilmore P.C, Gomory R.E. A Linear programming approach to the cutting stock problem[J]. Operations Research, 1961, 9: 849-859.
[14] Gilmore P.C, Gomory R.E. A Linear programming approach to the cutting stock problem-partⅡ[J].Operations Research, 1963, 11: 863-888.
[15] Gilmore P.C, Gomory R.E. Multistage cutting stock problems of two and more dimensions[J]. Operations Research,1965, 13: 94-120.
[16] Gilmore P.C, Gomory R.E. The theory and computation of Knapsack functions[J]. Operations Research, 1996, 14: 849-859.
[17] Ghodsi R., Sassani F. Online cutting stock optimization with prioritized orders[J]. AssemblyAutomation, 2005, 25(1): 66-72.
[18] Lee Jon. In situ column generation for a cutting-stock problem[J]. Computers and Operations Research, 2007, 34(8): 2345-2358.
[19] Alves Claudio, Valerio de Carvalho J.M. A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem[J]. Computers and Operations Research, 2008, 35(4): 1315-1328.
[20] Fang Hui, Yin Guofu, Li Haiqing and Peng Biyou. Application of integer coding accelerating genetic algorithm in rectangular cutting stock problem[J]. Chinese Journal of Mechanical Engineering (English Edition), 2006, 19(3): 335-339.
[21]李培勇,王呈方,茅云生.基于基因群体的一维优化下料[J].上海交通大学学报, 2006, 40(6): 1015-1018.
[22] Yanasse Horacio Hideki, Limeira Marcelo Seraiva. A hybrid heuristic to reduce the number of different patterns in cutting stock problems[J]. Computers and Operations Research, 2006, 33(9): 2744-2756.
[23] Trkman Peter, Gradisar Miro Source. One-dimensional cutting stock optimization in consecutive time periods[J]. European Journal of Operational Research, 2007, 179(2): 291-301.
[24] Gramani Maria Cristina N., Franca Paulo M. The combined cutting stock and lot-sizing problem in industrial processes[J]. European Journal of Operational Research, 2006, 174(1):509-521.
[25] Song X., Chu C.B., Nie Y.Y. and Bennell J.A. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem[J]. European Journal of Operational Research, 2006, 175(3): 1870-1889.
[26]尹震飚,阎春平,刘飞,等.基于零件相似性特征的大规模下料分组优化方法[J].计算机辅助设计与图形学学报, 2007, 19(11): 1442-1446.
[27]阎春平,刘飞,刘希刚.基于Internet的二维优化下料方法及其实现技术[J].重庆大学学报(自然科学版), 2001, 24(5): 1-4.
[28]朱波,阎春平,刘飞,等.一种基于Web Service的网络化优化下料系统[J].重庆大学学报(自然科学版), 2005, 28(1): 19-23.
[29]冯培恩,邱清盈,潘双夏,等.机械广义优化设计的理论框架[J].中国机械工程, 2000, 11(1-2): 126-129.
[30]王颖,周骥平,魏孝斌.虚拟设计在产品广义优化设计中的应用[J].机电产品开发与创新, 2006, 19(2): 60-62.
[31]徐有忠,潘双夏,邱清盈.面向广义优化的参数化设计方法研究[J].中国机械工程, 2003,14(17): 1485-1488.
[32] Heldenrelch P. Design for manufacturability[J]. Quality Progress, 1988, (3): 41-44.
[33] Tanner J P. Manufacturing engineering[M]. Florida: MarcelDekker Inc, 1991.
[34] Shah J J. A framework for manufacturaility evaluation in a feature based CAD system[C]. In: Arozona State university eds. Proc of NSF Design and Manufacturing Systems Conference. Arozona: Arozona State University Publisher, 1990: 61-66.
[35] Shankar S R, Jansson D G. A generalized methodology for evaluating manufacturabilty[C]. In: Parsaei H R, Sullivan W G, eds. Concurrent Engineering. London: Chapman &Hall, 1993: 248-263.
[36] Chu X, Holm H. Product manufacturing control for concurrent engineering[J]. Computers inIndustry, 1994, 24(6) : 29-38
[37] Suh N P, Rinderle J R. Qualitative and quantitative use of design and manufacturing axioms[J]. Annals of the CIRP, 1982, 31 (1) : 333-338
[38]宋玉银,肖亦辉,成烨,等.产品可制造性及评价方法的研究[J].清华大学学报(自然科学版), 1998, 38(7): 111-114.
[39]王润孝,盛义军,姜小鹏,等.产品可制造性评价方法研究.先进制造技术, 2006, 35(3): 31-34.
[40]吴瑞荣,张玉云,王先逵,等.面向对象的可制造性评价系统.清华大学学报(自然科学版), 1998, 38(2): 72-75.
[41] Dagli C H. A simulated annealing approach for solving stock problem[J]. Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 1990: 221-223.
[42] Dagli C H, Poshyannda P. New approaches to nesting rectangular patterns [J]. Journal of Intelligent Manufacturing, 1997, (8): 177-190.
[43]薛声家,左小德.管理运筹学[M].暨南大学出版社, 2000.
[44] D Sculli. A stochastic cutting stock procedure: cutting rolls of insulating tape[J]. Management Science, 1981, 27(8): 946-952.
[45] Gau T, Wascher G. A problem generator for the standard one-dimensional cutting stock problem [J]. European Journal of Operational Research, 1995, (84): 572-579.
[46]王伯成,施锦丹,王凯.粒子群优化算法的研究现状与发展概述[J].电视技术, 2008, 48(5): 7-11.
[47]沈显君,杨进才,应伟勤,等.一维下料问题的自适应广义粒子群优化求解[J].华南理工大学学报(自然科学版), 2007, 35(9): 113-117.
[48] Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem [J]. Operations Research, 1961, 9(5): 849-859
[49]高尚,杨静宇,吴小俊,等.基于模拟退火算法思想的粒子群优化算法[J].计算机应用与软件, 2005, 22(1): 103-104.
[50]李宁,孙德宝,岑翼则,等.带变异算子的粒子群优化算法[J].计算机工程与应用, 2004, 40 (17): 12-14.
[51]肖东喜,朱金福.飞机排班中航班环的动态构建方法[J].系统工程, 2007, 25(11): 19-25.
[52]刘希刚.多原材二维Guillotine优化下料技术及应用系统研究[D].重庆:重庆大学.硕士学位论文, 2001.
[53]朱波.面向数控下料加工的集成化板材优化下料系统的研究与开发[D].重庆:重庆大学.硕士学位论文, 2005.
[54]龚坚,刘飞,徐宗俊.定长条材优化下料的实用算法研究[J].重庆大学学报(自然科学版), 1997, 20(1): 92-97.
[55]尹震彪.面向多原料多零件的大规模优化下料技术研究[D].重庆:重庆大学.硕士学位论文, 2007.