许继影 陈仕军 郑晴

摘  要： 针对矩形件排样问题，经典的最下左填充（BLF）算法易于出现区域浪费、原材料利用率低的缺点。对此，提出一种改进的两阶段排放算法。第一阶段利用BLF算法，第二阶段设计一个改进BLF排放算法以减小区域的浪费。再以矩形件排放顺序进行编码，利用两阶段排放算法解码，设计邻域搜索算法寻找最优解。通过已有文献的多个案例，对改进的算法进行实验验证，结果与BLF算法相比，原材料利用率能提高14%，证实了改进算法的有效性。

关键词： 矩形排样; 排放算法; 两阶段; 邻域搜索

Abstract： For the rectangle packing problems， the classical bottom-left fill （BLF） algorithm may give rise to the disadvantages of waste area and low utilization of raw materials. Accordingly， an improved packing algorithm with two-stage layout is presented. At the first stage， BLF algorithm is used to pack rectangular pieces. At the second stage， an altered BLF algorithm is presented to fill the left-top corner of the big rectangle. Then the rectangular pieces are encoded in the sequence of placing， the proposed two-stage packing algorithm is used for decoding， and a neighborhood search algorithm is designed to find the optimal solution. Through several cases in the existing literature， the improved algorithm is experimentally verified， and the results show that the utilization rate of raw material can be increased by 14%， by comparing with the BLF algorithm. It confirms the effectiveness of the improved algorithm.

0 引言

矩形件排样问题（也称下料问题）广泛存在于玻璃切割、板材加工、布料裁剪等生产领域，对排样或下料方案进行优化，是企业实现降低成本、提高材料利用率的重要途径。传统的人工制定排样方案会耗费大量的人力和物力，而且材料利用率不高。因此，研究如何采用运筹和最优化方法，并辅助于计算机设备对排样方案进行优化，以提高排样方案的材料利用率，极具重要价值。

矩形件排样问题是计算领域的NP难问题，目前不存在求最优解的多项式时间算法。经典的数学规划方法复杂性太高，难以求解大规模问题。针对该问题，有些学者陆续提出一些求近似最优解的快速排放算法，例如Baker等人提出了最下左（bottom-left，BL）算法[1]，具有复杂度低易于实现的优点。但由于BL算法易产生过多的“空白区域”，考虑到排放利用率低的问题，Hopper与Turton提出一种能填充“空白区域”的最下最左填充（bottom-left-filling，BLF）[2]排放算法;贾志欣提出了一种最低水平线排放算法[3]。……