刘玉娟，徐凯宏，马 岩，董本志，杨春梅

（东北林业大学 林业与木工机械工程技术中心，哈尔滨 150040）

0 引言

随着人民生活水平不断提高，人们对居住环境、生活和工作空间舒适程度的重视也在不断加强，中高档家居和办公家具产品的需求量呈上升的势头。在国内市场上，我国家具制造业很好，需求额以每年10%～15%的速度递增，人造板的需求总量也在不断迅速增加。因此能否找出切割板材下锯优化的方法，以满足板材需求现状，并尽可减少板材的浪费，显得尤为重要。家具生产所需的人造板的形状主要是矩形的，这就将下锯优化的问题转化成矩形排样优化问题。所谓矩形排样优化问题即是一个多目标优化问题，既要考虑板材的利用率，又要考虑加工时的下料。本文研究的数控裁板锯是用来加工应用在家具生产加工所需的矩形零件的。它符合“一刀切”的加工工艺要求，这就要求采用一种方法来进行下锯优化，即余料最优处理。

1 矩形件的排样优化问题的提出

为了在市场竞争中立于不败之地并创造更多的效益，企业将会不断提高其生产效率。而一个好的排样方案可以节省原材料。但如果单纯考虑材料的利用率，在矩形件种类较多时会加大排样的复杂度，这样不但会影响生产过程中的下料的效率，而且会延长生产加工的时间。因此需要找到一个既考虑到材料利用率与下料效率，又能考虑到生产效率与“一刀切”的工艺要求的排样算法。

矩形件的排样问题是指在给定的矩形板材上将一些需要排样的矩形件以最优的方式排放在其上，以使材料的利用率达到最高，从而达到节省材料的目的[1]。好的排样方式可以在经济上制造非常可观的效益。从理论角度来看，矩形排样优化问题具有最高计算复杂性的问题，即NP完全问题[2]。对于NP完全问题至今还未找到多项式算法求解，因此只能采用近似的算法求解。对于矩形件的排样优化，任何算法都难以保证得到的总是最优解，国内外学者已提出了一系列的近似算法[3～6]，这些算法也达到了所期望的材料利用率。本文将根据数控裁板锯和板材的自身特殊点，研究一种新矩形件优化排样的算法。并对二维矩形件的下锯优化的算法开发了可用于该设备的计算机辅助排样软件。

2 下锯优化的约束条件及数学模型的建立

2.1 下锯优化的约束条件[7]

1）各矩形件之间相互不重叠；

2）矩形件的排放不能有超出板材的区域；

3）对于已经排放好的矩形件不能再移动其位置，即符合定序原则；

4）符合最右最低原则，即第一个排放的矩形件应放在板材的右下角，其余的矩形件则尽可能的排放在剩余区域的最右最低的位置；

5）满足“一刀切”的工艺要求。

“一刀切”下料又称直线切割，所谓“一刀切”是指保持切割线平行于板材的一个边，每一次切割都必须由板材的一端沿直线至另一端，对裁开的板材继续采用这个方法切割，一直到满足需求为止。图1（a）和（b）分别是一刀切模式与非一刀切模式的示意图。

图1 “一刀切”与非“一刀切”模式示意图

2.2 数学模型的建立

根据裁板锯的切割及运动的方向，板材排样的排样次序是自右向左、自下向上的。设板材的长和宽分别为L、W，有n（一般n≤10）种矩形件，其长、宽、数量分别用 li、wi、ni（1≤ i≤ n）表示。一般wi≤li≤W≤L。可得所有要排的矩形件的个数设总共用了N长板材，目的是在互不重叠的条件下把矩形件尽可能多的排列在板材上，并提高板材的利用率，即尽量减少使用的板材数量，并使余料尽可能多。

排在板材上的第一种矩形件有n种选择。假设选择了第i种零件，则一排最多可以放L/li个矩形件，最多可以排W/wi行。设在排样中每行排了x个零件，共排了y行，即有1≤x≤min [L/li]；1 ≤ y≤ min [W/wi][2]。

2.3 下锯优化算法的基本描述及下锯优化算法及流程

所谓最低水平线法就是不断更新水平线集的一种排样算法，其主要思想就是选择水平线集合中高度最低的那条，将要排放的零件排放在最低水平线上并更新水平线集，如果排不下则搜索与最低水平线左右两边相邻的水平线，选择高度较低的一条，将最低水平线提升至该高度，判断更新后的最低水平线能否排入该零件，若依然排不下则继续执行提升水平线的操作，直至能排入为止[8]。

本文采用的是基于最低水平线的选择算法，是基于最低水平线的一种改进算法。其具体步骤如下：

1）首先将矩形件按宽度从大到小的顺序进行排列，并同时列举出矩形件的边长数据；

2）设置初始最低水平线段为板材最下面的边和设置初始最大高度Hmax为0[9]；

3）排入待排序列的第一个待排板材的矩形件，并更新最低水平线段与最大高度Hmax，如果最低水平线有数段则选择从最右边的那段开始排；

4） 每当要再排入一个矩形件时，测试其宽度是否既小于或等于最低水平线段的宽度又小于或等于最低水平线与最大高度Hmax之间的距离；

（1）若都小于或等于，则判断其长度是否小于或等于最低水平线的宽度；

①若小于或等于则将该矩形件在此位置横放，并其从待排有序矩形件集中删除，同时更新最低水平线段和最大高度Hmax；

②否则判断其长度是否小于或等于最低水平线与最大高度Hmax之间的距离；若小于或等于则将该矩形件在此位置竖放，并其从待排有序矩形件集中删除，同时更新最低水平线段和最大高度Hmax。否则转至（2）；

（2）依次从待排有序矩形件集中查找宽度小于该最低水平线段宽度的矩形件，如果找到则转至（1）。如果没有找到则更新最低水平线，直至最低水平线与最大高度Hmax重合，转至3）；

5）最低水平线的最大高度是否达到板材边界，若达到则更换一张新板材并转至2），否则转至6）；

6）重复4）到5）的过程，直至排入所有矩形件，并求出此时的最大高度即为所需板材的高度。

下锯优化算法流程图如图2所示。

3 计算实例及分析

本文的目的是使最大高度Hmax以下的部分没有填充的面积最小，并且Hmax以上的部分面积尽可能的大，以此提高整体的利用率。下面以下列规格的矩形件为例，应用上述优化算法进行排样。表1为10种需要切割的矩形件。设原板材的尺寸大小为2440×1220mm，其中表是按矩形件宽度的递减顺序排列的。

应用上述方法对表1进行排样，首先，先把同种的矩形件拼成一个大矩形，然后再宽度递减的顺序排列新的矩形件。其排样结果如图3和图4所示。

图2 下锯优化的流程图

第三块板材剩下的板材下次排样的时候可以继续使用。实践证明，排样的矩形件的种类、个数及板材的尺寸都会对板材的利用率有很大的影响。矩形件的种类越多，板材的尺寸越多利用率就越大。加工的时候要注意批量生产可以大大的提高板材的利用率。

4 结论

通过对实例的分析表明本研究的矩形件排样方法能够良好的解决数控裁板锯的下锯问题，它符合多种尺寸的板材的排样，并且既可以达到优化的效果又可以使可用余料面积相对较大。且操作比较简单，效果明显并适合解决较大规模的排样问题。同时，还可以应用到比较相似的切割问题上，具有较强的灵活性与应用性。

表1 10种待排矩形件的尺寸列表（单位：mm）

图3 第一块板材的利用率：98.32%，最大高度Hmax为1200mm

图4 第二块板材的利用率：93.88%，最大高度Hmax为1210mm

图5 第三块板材的利用率：59.96%，最大高度Hmax为720mm

[1] 杨传华, 吴锦文, 李亚芹, 郭士清. 定序列矩形件优化排样的二维搜索算法[J]. 佳木斯大学学报(自然科学),2010, 28(3): 354-356.

[2] 李勇, 曹炬, 梅晚霞, 方仍存. 矩形件排样优化的十字线法[J]. 锻压装备与制造技术, 2004, (6): 98-100.

[3] 曹炬, 周济, 余俊. 矩形件排样优化的背包算法[J]. 武汉:中国机械工程, 1994, 5(2).

[4] 方仍存, 曹炬, 陈学松. 矩形件排样优化的一种近似算法[J]. 锻造技术, 2005(6): 19-20.

[5] Yanasee HH. Two-dimensional cutting stock with multiple stock sizes. The Journal of Operational Research Society.1991, 42 (8): 673-683.

[6] Chaung F A. Two-Phase Heuristic for the Two-Dimensional Cutting Stock Problems. The Journal of Operational Research Society, 1991, 42 (1): 39-47.

[7] 吕俊丰, 马岩, 喻虎德. 人造板一刀切数控下锯优化的编程模型研究[J]. 木材加工机械, 2009(5): 12-15.

[8] 王竹婷, 刘林, 程浩, 刘心报. 改进的最低水平线搜索算法求解矩形排样问题[J]. 工程设计学报, 2009, 16(2): 98-102.

[9] 朱冠华. 矩形件排样中基于最低水平线的改进算法[J].茂名学院学报, 2006, 16(1): 28-32.