Packing Compaction Algorithm for Rectangular Cutting and Orthogonal Packing Problems

摘要

The rectangular cutting and orthogonal packing problems which have many practical applications in industry and engineering are considered. Increasing the density of placement schemes leads to reducing the material usage in solving the rectangular cutting problems and reducing the unused resources at solving the orthogonal packing problems. This article contains the description of the developed packing compaction algorithm and its investigation. This algorithm uses six object selection rules, which select objects from a container for deleting and subsequent reallocation of them into freed spaces of the container. The packing compaction algorithm iteratively applies a one-pass heuristic algorithm which finds the best placement of the deleted objects in order to increase the density of the result packing. The effectiveness of the application of the proposed algorithm is investigated on the standard two-dimensional strip packing problems which are the rectangular cutting problems with only one container of a fixed width and an infinite length. Based on the test results, the effective sequence of application of the proposed rules used as the part of the packing algorithm was determined. The packing compaction algorithm is implemented in a general form which makes it possible for application in the rectangular cutting and orthogonal packing problems of arbitrary dimension.