Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes

The irregular strip packing problem (ISP), or often called the nesting problem, is the one of the representative cutting and packing problems that emerges in a wide variety of industrial applications, such as garment manufacturing, sheet metal cutting, furniture making and shoe manufacturing [Alvarez-Valdes et al., 2018, Scheithauer, 2018]. This problem is categorized as the two-dimensional, irregular open dimensional problem in Dyckhoff [1990], Wäscher et al. [2007]. Given a set of pieces of irregular shapes and a rectangular container with a fixed width and a variable length, this problem asks a feasible layout of the pieces into the container such that no pair of pieces overlaps with each other and the container length is minimized. We note that rotations of pieces are usually restricted to a few number of degrees (e.g., 0 or 180 degrees) in many industrial applications, because textiles have grain and may have a drawing pattern. Figure 1 shows an instance of the ISP and a feasible solution. The first issue encountered when handling the ISP is how to represent the irregular shapes. In computer graphics, the irregular shapes are often represented in two models as shown in Figure 2: the vector model represents an irregular shape as a set of chained line and curve segments forming its outline, and the raster model (also known as the bitmap model) represents an irregular shape as a set of grid pixels forming its inside.