矩形件排样算法探讨.doc

《矩形件排样算法探讨.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、矩形件排样算法探讨【摘要】针对二维矩形件优化排样问题，提出一种新型的算法一一矩形动态匹配算法。通过对零件的矩形化预处理，并自动正交排布使零件紧密靠接和定位，从而实现复杂不规则船体零件的矩形化排样，该算法亦可扩展用于三维空间零件的排样求解，实例证明其有效性。【关键词】排样；矩形零件；优化；算法[Abstract】Foroptiinalnestingofrectangularpartsofatwodimensionalproblem,anewkindofalgorithmisputforward.Therectangularpretreat

2、mentandautomaticallyorthogonalconfigurationmakethelocationofpartsmoreclose,therectangularoptimizationnestingofcomplexirregularshippartsisrealized,thealgorithmcanbeextendedto3dspaceparts.Examplesshowitseffectiveness.【Keywords】Parking；Rectangularparts；Optimization；Algorith

3、m0引言排样优化技术是工业产品设计、制造中如何节约原材料、优化利用资源的重要手段。现实零件形状复朵，多为不规则零件，且制造特征和方法各异，如何采用有效的算法实现最优布局、提高原材料的利用率尤为重要[1-3]o文中基于对排样零件矩形化预处理提出了矩形动态匹配算法来实现零件的定位，具有较高的材料利用率。1算法简介1・1实现算法的前提条件将一个矩形零件排放在矩形板材中，需要解决的问题有：(1)多个矩形零件排放时的排放次序。(2)矩形零件的排放位置问题。1.2入排矩形零件必要约朿条件(1)规定矩形零件仅有横放、竖放两个状态。如图1所示，A为竖放

4、状态S,C为横放状态H,B为非法放置。采用左下角和右上角两端点坐标(Xli,Yli)(Xhi,Yhi)描述一个矩形。通过比较Xhi-Xli与Yhi-Yli的大小来确定矩形零件的状态。(2)排样时，各个矩形零件之间不得相互重叠。为了满足任意两个矩形零件不重叠放置，须满足如下数学关系：假设两个短形分别为A(xli,yli)(xhi,yhi)；B(xlj,ylj)(xhj,yhj),Max[xli~xhj,xlj-xhi,yli-yhj,ylj-yhi]>=0i,j=l,2,3・・・N,i不等于j；(3)排样时，各个短形零件不得超出板材区域。

5、1.3算法实现过程在板材上的定位(排列)具体算法步骤[4-5]:(1)输入给定板材件宽度B,确定原点(0,0)；(2)输入各矩形零件Xi(ai,bi)i二1,2,3；(1)计算面积Si二ai*bi；(2)由大到小排列[Si](即新数列S1>S2>S3……)；(3)读入第一个矩形(最大的矩形)Al(xl1,yl1)(xhl,yhl),当xhl

6、一个矩形零件顶部排入靠近板材左端；(5)读入下一个矩形重复上一步骤直到所有矩形零件排完。2零件的矩形化处理零件组合矩形包络过程根据算法的复杂程度可以通过自动排样完成，也可以通过人工交互完成，通常采用方法有[6-9]:3应用实例选择板材宽度1000mm,长度不限，输入待排零件39个。基于上述排样算法，文中实现了39个零件排样定位并输出排样图。图4为39个零件的排样图，板材的利用率为89.18%04结论定位算法是求解最佳排样布局的核心技术，对于不规则零件更是难点。文中采用较为简单的定位算法，同时对待排零件进行矩形化预处理，大大降低了排样计算

7、的复杂度，能解决一般矩形件的排样问题，具有较高的原材料利用率。【参考文献】[1]贾志欣，殷国富，罗阳•二维不规则零件排样问题的遗传算法求解[J]•计算机辅助设计与图形学学报,2002,14(5)：467-470.[2]毛定山，崔先国，李行，等•简单多边形集凸包的快速算法[J]•工程图学学报，2007(6)：96-101.[3]陈端兵，黄文奇•求解矩形packing问题的贪心算法[J]•计算机工程，2007,33(4)：160-162.[4]曾敏，王乘，刘琼梅•大规模定制板材排样的多种群蚁群优化算法[J]•制造业自动化,2011,33(5

8、)：59-62.[5]曾凤华•剩余矩形匹配算法在矩形件排样中的应用[J]•机电工程技术，2006,35(3)：64-65・[6]李满江，孟祥旭•矩形件和任意多边形排样问题的算法及应用[J]・贵州工业大学学报