矩形件排样算法探讨

2015-12-02苏厚仁钟相强

科技视界 2015年33期

苏厚仁　钟相强

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

【关键词】排样；矩形零件；优化；算法

【Abstract】For optimal nesting of rectangular parts of a two dimensional problem， a new kind of algorithm is put forward. The rectangular pretreatment and automatically orthogonal configuration make the location of parts more close， the rectangular optimization nesting of complex irregular ship parts is realized， the algorithm can be extended to 3d space parts. Examples show its effectiveness.

【Key words】Parking； Rectangular parts； Optimization； Algorithm

0 引言

排样优化技术是工业产品设计、制造中如何节约原材料、优化利用资源的重要手段。现实零件形状复杂，多为不规则零件，且制造特征和方法各异，如何采用有效的算法实现最优布局、提高原材料的利用率尤为重要[1-3]。文中基于对排样零件矩形化预处理提出了矩形动态匹配算法来实现零件的定位，具有较高的材料利用率。

1 算法简介

1.1 实现算法的前提条件

将一个矩形零件排放在矩形板材中，需要解决的问题有：

（1）多个矩形零件排放时的排放次序。

（2）矩形零件的排放位置问题。

1.2 入排矩形零件必要约束条件

（1）规定矩形零件仅有横放、竖放两个状态。如图1所示，A为竖放状态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]>=0 i，j=1，2，3…N，i不等于j；

（3）排样时，各个矩形零件不得超出板材区域。

1.3 算法实现过程

在板材上的定位（排列）具体算法步骤[4-5]：

（1）输入给定板材件宽度B，确定原点（0，0）；

（2）输入各矩形零件Xi（ai，bi） i=1，2，3；

（3）计算面积Si=ai*bi；

（4）由大到小排列[Si] （即新数列S1>S2>S3……）；

（5）读入第一个矩形（最大的矩形）A1（xl1，yl1）（xh1，yh1），当xh1

（6）读入下一个矩形，检测板材是否有矩形状空穴，交叉比较矩形零件与空穴的长宽大小，若满足空穴条件，矩形零件排入空穴（优先横放状态），若不满足空穴条件，零件靠接这一层第一个矩形零件顶部排入靠近板材左端；

（7）读入下一个矩形重复上一步骤直到所有矩形零件排完。

2 零件的矩形化处理

零件组合矩形包络过程根据算法的复杂程度可以通过自动排样完成，也可以通过人工交互完成，通常采用方法有[6-9]：