Algorithms to solve 2D and 3D Irregular Cutting and Packing Problems using a Semi-discrete Representation

Cutting and packing problems, whether in 2D or 3D, involve positioning a set of pieces without overlap within one or more containers. These problems occur in a wide range of industrial applications such as sheet metal and textile cutting, logistics, and additive manufacturing. This thesis provides efficient optimization methods for both 2D and 3D irregular cutting and packing problems using a semi-discrete representation of both the pieces and the container.

We develop a fast and scalable algorithm to solve 2D irregular open dimension cutting and packing problems, where the objective is to minimize the horizontal length of the container, while rotation of the pieces is allowed. The pieces and the container are represented by a set of equidistant vertical line segments. This semi-discrete representation is obtained using a sweep-line algorithm, followed by an extension algorithm. The latter constructs minimal but complete extensions to the line segments of a piece to ensure that a non-overlapping placement of the line segments, representing two pieces, guarantees non-overlapping pieces. We implement a left-bottom-fill greedy placement procedure, using an optimized ordering of the segment overlap tests. The quality of the solutions and the execution times depend on R, the distance between the vertical line segments, and the execution time increases less than linear in R^(-1). For some benchmark problems, this left-bottom-fill algorithm is approximately two orders of magnitude faster than a similar placement algorithm in the literature, using a continuous representation of the pieces. Moreover, our algorithm scales well with an increasing number of pieces or number of allowed rotations. 

To reduce the runtime we develop a parallelized version of the algorithm. When for each piece multiple rotation angles are allowed, the computation of the tentative placement for each angle is executed in parallel. However, the speedup is limited due to load imbalance. To improve solution quality, we develop a bucket-based algorithm. The set of pieces is divided into buckets; the buckets are placed using the left-bottom-fill algorithm, while computing an optimal ordering of the pieces in each bucket. The many possible orderings of the pieces in a given bucket enable the creation of many tasks that can be executed concurrently. The parallel bucket-based left-bottom-fill algorithm with bucket size 3 achieves a shorter container length than the original left-bottom-fill algorithm while the execution time is still short.

Building upon the efficiency of the 2D left-bottom-fill algorithm using semi-discretization, we extend this approach to solve 3D irregular cutting and packing problems. The pieces and the container are semi-discretized using a grid in two dimensions, resulting in line segments in the third dimension. The line segments are extended, following a similar approach to the 2D problem, to prevent overlap of the pieces when placed in the container. We present a `deepest-left-bottom-fill’ placement algorithm for semi-discretized pieces and container by iteratively using the 2D left-bottom-fill algorithm. This algorithm is scalable with an increasing number of pieces and an increasing number of allowed rotation angles. We show that when a sufficient number of rotations are allowed, the deepest-left-bottom-fill algorithm finds solutions that are competitive with those obtained with other heuristics and described in the literature, but it is orders of magnitude faster. We introduce a parallel version of the algorithm with dynamic load balancing to further reduce the execution time and we evaluate its performance on a multicore processor with different task sizes. We experimentally determine which task size maximizes the speedup due to parallelization. To further improve the solution quality, we implement a hill climbing algorithm based on reordering the pieces on top of the deepest-left-bottom-fill algorithm. Finally, we compare the performance of the deepest-left-bottom-fill algorithm both with and without hill climbing with results presented in the literature for some benchmark problems: a similar solution quality is achieved but the execution time is two orders of magnitude shorter.