企业生产实践中圆形零件的优化排样深入研究
导读：在圆形件这种冲裁零件的生产成本中材料费用通常占60%以上,即便只稍微提高原材料的利用率，也势必给企业带来非常可观的经济效益。将圆形片排样技术应用于企业生产实践，可以有效提高原材料利用率，降低生产成本，提高企业在同行业中的竞争力。由本站硕士论文中心整理。
绪论
问题概述
排样问题在加工生产中广泛存在，属十下料、布局问题。排样就是以提高材料利用率和加工效率为目的，求取多个相同或不同的样件(零件)在原材料(板材)上的合理布置方案的过程。优化排样问题是指已知各种原材料和毛坯的信息，在满足毛坯需求和不超出原材料范围的条件下，实现毛坯在板材上的合理布局，使板材原料消耗最少，达到材料利用率和加工效率、降低生产成本的目的。
本文研究的是圆形零件的优化排样问题，即在各种原材料上对圆形件进行排样，使得原材料利用率最高。在这里，原材料的形状不一，有规则的和不规则的，规则的又分为矩形、圆形、正多边形、平行四边形等。本文主要研究圆形零件在矩形原材料上的优化排样。
机械制造、船舶、车辆、电机以及航空航天等行业都存在圆形件下料问题例如，电机行业使用硅钢圆片制作中小型电机的定子和转子铁芯，不锈钢制品业使用不锈钢圆片制造锅碗杯}i‘等产品，仅这两个行业就有数千甚至上万家制造企业，每年消耗的硅钢和不锈钢板材或卷材数百万吨，在圆形件这种冲裁零件的生产成本中材料费用通常占60%以上,即便只稍微提高原材料的利用率，也势必给企业带来非常可观的经济效益。将圆形片排样技术应用十企业生产实践，可以有效提高原材料利用率，降低生产成本，提高企业在同行业中的竞争力。
2优化排样问题的分类
根据原材料和毛坯的维数的不同，排样问题可以分为二种排样类型[2]:
(1)一维排样问题
一维排样问题，又称为线性排样问题，是最早得到研究的排样问题，Kantorovich在1939年就讨论了一维下料1问题,1965年美国学者Gilmore不II Gomory采用运筹学中著名的背包运输方法第一次解决了一维优化切割问题，提高了运输速度。一维排样问题是指在优化排样时只考虑原材料和毛坯的长度方向。这类问题主要应用十将较长的型材、线材、棒材等，分割成各种长度的毛坯，用十各类生产。求解一维排样问题可以应用线性规划、动态规划、遗传算法以及线性规
划方法与遗传算法相结合的混合型算法.
2)一维半排样问题
一维半排样问题又称为卷材排样问题，是指被分割的板材为宽度较小、IfIJ长度远远大十毛坯尺寸的卷材。一般有二种排样情况:连续条带排样、冲裁条带排样、矩形毛坯排样，通常情况下这种问题可视板材的长度为无限长，从只需考虑板材宽度方向的尺寸，这样便可以把卷材排样看作是一维排样问题，排样方法则可以在借鉴一维排样问题的解决方法的基础上结合自己的特点进行特定处理。下料时一般是首先沿卷材的长度方向切割成条带，再将条带切割成各种型号的毛坯。这种下料方式主要应用十服装业、皮革制品、纸制品、塑料制品等行业。
(3)二维排样问题
二维排样问题[7]，又称为板材排样问题，是指将平面零件在板材上按最优方式进行排布，即将给定二维零件pi" pz" 1s"... p，置十板材p上，使得板材的利用率最高。二维排样问题根据排入毛坯形状的不同分为矩形件排样问题、二维不规则形排样问题和圆形件排样问题，家具制造业、金属制品业、印刷业种书刊、报纸的排版、集成电路的排布等都属十二维排样问题。解决二维排样问题除了一些经典常规如线性规划、动态规划和背包算法等以外，一些经典的近似算法、启发式算法不I I智能算法也常常应用其中，如BFD算法(Best Fit DEC-reusing)、AD算法.CAlienate Direct)、遗传算法、模拟退火算法等智能优化算法用十解决二维不规则件的下料问题。如文献中将模拟退火算法和粒子群算法相结合，提出了一种基十模拟退火的粒子群算法[fgl;文献中将遗传算法和矩形包络法相结合用十解决二维不规则件的排样问题.
(4)二维布局问题
二维布局问题是指原材料和所需毛坯的长、宽、高都有特定要求的情况，下料时需考虑毛坯的立体形状的下料问题。根据装载目的的不同，二维装箱问题又可分为以下二类:箱柜装载问题、容器装载问题和背包装载问题yob。箱柜装载问题是指给定一些不同类型的方形箱子和一些规格统一的方形容器，把所有箱子装入到最少数量的容器中。容器装载问题是将所有箱子装入一个不限尺寸的容器中，目标是要找一个装填方式，使得容器体积最小。背包装载问题是给定若干具有一定价值的箱子，在这些箱子中选择一部分装入容器中，使得装入容器中的箱子总价值最大。装箱问题普遍应用十物流行业中。对十这类问题的下料多采用启发式算法，例如文献中通过组合拟人启发式算法和模拟退火算法，提出了二维装箱问题的组合启发式算法.
对十单张板材排样，可分为无约束排样和有约束排样。无约束排样是指已知要排入毛坯的尺寸和价值，实现其在单张板材上的排样，使得排入毛坯的总价值最大，这种排样算法通常与线性规划技术相结合，求解排样问题。有约束排样也是实现毛坯在单张板材上的排样，使得排入毛坯的总价值最大，但要求板材中所含各种毛坯的数量，不超过各自的上限;有约束排样算法通常和顺序法相结合，求解排样问题。
3.国内夕卜研究现状
由十优化排样技术可以明显提高经济效益，国内外学者对该问题进行了大量的研究与分析，在许多国际著名的学术期刊中，都对排样算法的研究成果进行了报道，但是大部分为二维矩形零件和二维不规则性零件的排样与下料问题，对圆形零件排样问题的研究却很少。根据所查文献，目前圆形件下料问题根据板材原料1的不同大致可以分为两个研究方向:
(1>原材料为定宽不定长卷材的圆形件排样问题。
针对这类排样问题Mhand Hifi提出了BLP(Best-Local Position) ,RBLP(Re-ordered Best-Local Position拜II GA-BH等几种方法[”，’2], B LP方法首先将第一个毛坯置十板材最左最下位置，根据已放入毛坯的位置确定下一个将要放入毛坯的五个可能放入点，将不会产生毛坯重合的位置称为该毛坯的可行放入位置，并用一个表来保存每个毛坯的可行位置，再从中删除重复的位置，根据此表得出可行解，最后在可行解当中找到最优解:RBLP方法以BLP方法为基础，通过更改圆形片放入顺序，减少BLP方法生成的排样方式中可能存在的板材准确位置;GA-BH方法则是以改进后的BLP方法作为基础的排样算法，再利用遗传算法进一步优化;宋晓霞在Mhand Hifi提出的方法上的基础上提出了圆弧搜索算法CASA)，用十实现卷材上的圆形件有约束排样「’3]。ASA首先将可行位置的搜索范围进行离散，也就是选择搜索范围的一个子集进行搜索，然后利用圆形件的形状特性、排样方式的性质等，避免对搜索范围中部分不可行区域的搜索，以缩短求解时间。该算法可以在较短时间内产生GA-BH方法相媲美的利用率，同时，采用混合遗传算法(HGA)指导搜索，考虑多种毛坯顺序，进一步提高材料利用率;Sonya和Yaks采用分支定界法和逐次逼近的方法，将不同尺寸的圆形毛坯放入卷材上，使得所消耗的卷材长度最短「’5];凌少东等针对圆形毛坯剪冲下料问题，从单板的利用率角度讨论了卷材上的切割下料，介绍了并排、品排和基十品排的斜排的二种卷材上圆形件排法，通过分析实际下料过程中相邻圆形件之间和卷材边界与圆形件间的空隙，得出基十品排的斜排在大部分情况下都优十其他两种方法，并目_从理论分析、数据模拟和实例计算二个方面得出结论一一最大行数斜排法又是基十品排的斜排中最优的;崔耀东教授等提出在卷材上选择最好的板材切割长度，使得板材下料问题利用率最高.
C2)原材料为给定尺寸板材的圆形件排样问题。
Locatable和Raber}}g]提出分支定界法来解决以冲裁下料为工艺基础的同尺寸圆形片在方形板材上的无约束最优排样，Hifi teals.设计了基十启发式的模拟退火算法将圆形零件排在矩形原材料的左下角;崔耀东教授提出一系列典型的排样方式来满足实际生产中不同的工艺即利用率的要求，包括T型排样方式、多段排样方式及多级排样方式[[20-22]等，对十有约束下料问题Harkin又提出树搜索方法解决不同尺寸圆形件在圆形原材料上的放置问题A. George在文献中，设计算法用十解决将不同直径的管道放入到船舶等容器内，他将该问题简化为圆形件在矩形板材上的冲裁问题，并将其定义为非线性混合整数规划问题，采用启发式算法解决此问题[24]。陈菲在文提出圆形毛坯的二块排样方式在满足圆形毛坯需求的前提下，使板材的消耗尽可能少，达到节约生产原材料的目的[[25]。对十在多张板材上进行下料，选择最优的排样方案，使得板材的利用率最高，目前所采用算法的大部分是线性规划算法(LP)来解决此类问题，所区别的只是采用的排样方式不同。
近年来，随着科学技术的进步以及人们对制造业的要求越来越高，使得对原材料为板材的圆形件问题的研究越来越多，但由十该问题相对来说比较复杂，目前虽然国内外学者对该问题进行了研究，但却没有明显的效果。
本文主要研究原材料为给定尺寸的矩形板材的圆形件排样问题。
参考文献
[1].洪灵，徐云杰.计算机辅助排样算法综述[fJl.锻压装备与制造技术，2007,4:16一19
[2].崔耀东.计算机排样技术及其应用「M].北京:机械工业出版社，2004,1.戴瑞，陈炳森.单一形状冲裁件的优化排样算法.机械制造，2002,40(2):33一3 _5.
[3].戴瑞，陈炳森.单一形状冲裁件的优化排样算法[[J].机械制 造，2002,40(2):33一3 _5.
[4]. Valeria de Carvel J M. LP models for bin packing and cutting stock problems[J].European Journal of Operational Research,2002,141:253一273.
[5]. Starker B.R.An optimum solution for one dimensional slitting problems:A Dynamic Programming Approach[J].Journal of Operational Research Societv.1988,39(8):749一7 _5 _5.
[6].李兀香，张进波.基十变长编码求解一维下料问题的演化算法[J].武汉大学学报.2001,47(3):289-293.
[8].郭江建，罗阳，刘胜青等.二维零件排样问题的研究「J].机械设计与制 造，2006,7:77一79.李明，宋成芳，周泽魁一种二维不规则零件优化排样算法「J].四川大学学报，2005,37(4):134一138.
[9]. Ramset B A, Rimes B N.A generic approach for nesting of 2一D parts in 2一D sheets using genetic and heuristic algorithms [J].Computer-Aided Design,2001，33(12):879一891.
[10].张德富，魏丽军.二维装箱问题的组合启发式算法「J].Journal of Software,2007，18(9):2083一2089.
[11].Hifi M, M'Hallah R.A beat-local position procedure一based heuristic for the two dimensional layout problem[J].Studio Informatics Universal is International Journal on Informatics,2002,2(1):33一_5 6.
[12].Hifi M, M’Hallah R.Approximate algorithms for constrained circular cutting problems [J].Computers&Operations 67 _5一694.
Research, 2004, 31 (5):
[13].宋晓霞，李勇一种求解圆形下料问题的快速算法[J}.微计算机信息，2002,2(1):33一_5 6 .
[ 14].宋晓霞.圆形件优化排样系统研究与开发「D]，杜林:广西师范大学，200_5.
[15].Sonya Y G, Yaks G N.Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints[J].International Transactions in Operational Research,1998,5(1):4 _5一_5 7.
[16].凌少东，曹炬，刘毅.卷材上的圆形件优化排样[[J].锻压技 术，2005,30(5):30一32.
[17].Cui丫Chen Y, Wu J.Selecting the best sheet length for the steel stock used in circular blank production [J].IIE Transactions，2006, 38(10):829一836.
[18].Locatable M, Raber U.Packing equal circles in a square: a deterministic global optimization approach [J].Discrete Applied Mathematics，2002 122,139一166.
[19].Hifi M, Pasco's V T, Zissimopou V.A simulated annealing approach for the circular cutting problem [J].European Journal of Operational Research,2004,159:430一448.
[20].Cui Y. Generating optimal T-shape cutting patterns for circular blanks [J]Computers&Operations Research,2005，32(1):143一152.
[21].Cui Y. Generating optimal multi一segment cutting patterns for circularblanks in the manufacturing of electric motors [J].European Journal of
[31].熊慧.二维矩形切割问题的研究与实现「D].辽宁科技大学，2007.
[32].施佳琦，魏祖宽.材料切割优化问题的特殊解法「J].计算机与现代化，2010,3:173一175.
[33].胡运权.运筹学教程(第二版)[M].北京:清华大学出版社，2007.
[34].何坚勇.运筹学基础[M].北京:清华大学出版社，2000.
[35].黄文奇，许如初，陈卫东等.解packing及CNF-SAT问题的拟物拟人方法[J].华中理工大学学报，1998,26(9):5-7.
[36].许如初，黄文奇.解不等圆packing问题拟物拟人算法初态选取「J].华中理工大学学报，1998,26(4):1-3.
中文摘要 4-6
ABSTRACT 6-7
1. 绪论 9-14
1.1 问题概述 9
1.2 优化排样问题的分类 9-11
1.3 国内外研究现状 11-12
1.4 本文的目标和主要工作 12-14
1.4.1 本文的目标 12
1.4.2 本文的主要工作 12-14
2. 圆形件优化排样基础 14-21
2.1 圆片无约束排样与有约束排样 14
2.1.1 圆片无约束排样 14
2.1.2 有约束排样 14
2.2 排样方式与排样方案 14-15
2.3 剪冲排样和非剪冲排样 15
2.4 套裁排样方式和单一排样方式 15-16
2.5 几种典型的排样方式 16-19
2.5.1 直接排样 16-17
2.5.2 利用条形带排样 17-19
2.6 根据原材料和圆片的规格进行分类 19-20
2.7 本章小结 20-21
3. 单一矩形原材料圆形件的单一排样 21-27
3.1 问题描述及模型建立 21-22
3.2 两种排样模式 22-25
3.3 实例分析 25-26
3.4 本章小结 26-27
4. 单一矩形原材料圆形件的套裁排样 27-50
4.1 圆形零件排样问题描述及模型建立 27-28
4.2 圆形零件排样方式 28-40
4.2.1 NEST 排样过程 29-35
4.2.2 BLOCK 排样 35-38
4.2.3 半径搜索法 38-40
4.3 实例分析 40-48
4.4 本章小结 48-50
5. 总结与展望 50-51
参考文献 51-56
致谢 56
您可能有工程硕士学位论文方面的购买需求，请到工程论文硕士论文频道选取：