Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut (also called an edge-to-edge cut) is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine. Guillotine cutting is particularly common in the glass industry. Glass sheets are scored along horizontal and vertical lines, and then broken along these lines to obtain smaller panels. It is also useful for cutting steel plates, cutting of wood sheets to make furniture, and cutting of cardboard into boxes. There are various optimization problems related to guillotine cutting, such as: maximize the total area of the produced pieces, or their total value; minimize the amount of waste (unused parts) of the large sheet, or the total number of sheets. They have been studied in combinatorial geometry, operations research and industrial engineering. In microelectronics, in floorplanning, a "sliceable floorplan" is the one that can be produced by guillotine cutting. A related but different problem is guillotine partition. In that problem, the dimensions of the small rectangles are not fixed in advance. The challenge comes from the fact that the original sheet might not be rectangular - it can be any rectilinear polygon. In particular, it might contain holes (representing defects in the raw material). The optimization goal is usually to minimize the number of small rectangles, or minimize the total length of the cuts.
Terminology and assumptions The following terms and notations are often used in the literature on guillotine cutting.
The large rectangle, also called the stock sheet, is the raw rectangular sheet which should be cut. It is characterized by its width W0 and height H0, which are the primary inputs to the problem The small rectangles, also called items, are the required outputs of the cutting. They are characterized by their width wi and height hi and for i in 1,...,m, where m is the number of rectangles. Often, it is allowed to have several rectangles of the same dimensions; in this case, the pair of dimensions (wi,hi) is often called a type. A cutting-pattern, often called just pattern, is an arrangement of small rectangles on the stock sheet. It may be given as a sequence of points (xi,yi), for i in 1,...,m, where (xi,yi) is the bottom-left coordinate of rectangle i. In such a pattern, rectangle i occupies a horizontal segment (xi, xi+wi) and a vertical segment (yi, yi+hi). A build refers to constructing a new rectangle by attaching two smaller rectangles. Due to the guillotine constraint, there are only two types of builds: in a horizontal build the combined rectangle has width wi+wj and height max(hi,hj); in a vertical build the combined rectangle has width max(wi,wj) and height hi+hj. Every pattern can be represented as a recursive sequence of builds. Every recursive sequence of builds corresponds to many different patterns, which have an equivalent combinatorial structure; the set of all patterns corresponding to the same recursive-build is called a guillotine-cutting class. Some problems accept additional inputs, as explained below. The goal is to cut, from the raw rectangle, some smaller rectangles having the target dimensions. The following assumptions are often made:
All cuts have zero width. This does not lose much generality, since if each cut has a fixed width of d>0, then the problem can be reduced to the zero-width variant by just adding d to wi and hi for i in 0,...,m. The target dimensions cannot be rotated, i.e., w-by-h is not the same type as h-by-w. This does not lose much generality, since the variant in which rectangles can be rotated, can be reduced to the non-rotatable variant by adding the rotated patterns explicitly.
Checking a given pattern In the pattern verification problem, there is a cutting-pattern given as a sequence of points (xi,yi), for i in 1,...,m, where (xi,yi) is the bottom-left coordinate of rectangle i (there is a single rectangle of each target-dimension). The goal is to decide whether this pattern can be implemented using only guillotine cuts, and if so, find a sequence of such cuts. An obvious necessary condition is that no two input rectangles overlap in both dimensions. Ben Messaoud, Chengbin and Espinouse present a stronger condition, which is both necessary and sufficient. The input rectangles are ordered from left to right, such that x1 ≤ ... ≤ xm. There is a permutation p on the indices such that, with this permutation, the rectangles would be ordered from bottom to top, i.e., yp(1) ≤ ... ≤ yp(m). Given four indices i1 ≤ i2 and j1 ≤ j2, the set E(i1,i2,j1,j2) contains the indices of all rectangles whose bottom-left corner is in the rectangle [xi1,xi2] X [yp(j1),yp(j2)]. A cutting pattern is a guillotine pattern if and only if, for all quadruplets of indices i1 ≤ i2 and j1 ≤ j2, at least one of the following conditions is fulfilled for E(i1,i2,j1,j2):
E(i1,i2,j1,j2) contains at most one element; The union of the horizontal segments (xi, xi+wi), over all i in E(i1,i2,j1,j2), is made up of at least two disjoint intervals; The union of the vertical segments (yi, yi+hi), over all i in E(i1,i2,j1,j2), is made up of at least two disjoint intervals. Condition 2 implies that the rectangles in E(i1,i2,j1,j2) can be separated by a vertical cut (going between the two disjoint horizontal intervals); condition 3 implies the rectangles in E(i1,i2,j1,j2) can be separated by a horizontal cut. All conditions together imply that, if any set of adjacent rectangles contains more than one element, then they can be separated by some guillotine cut. This condition can be checked by the following algorithm.
At each iteration, divide a given pattern, containing at least two rectangles, into two disjoint sub-patterns using a guillotine cut, and recurse on each sub-pattern. Stop when either all subpatterns contain one rectangle (in which case the answer is "yes") or no more guillotine cuts are possible (in which case the answer is "no"). Finding a guillotine cut for a given pattern is done as follows:
… excerpt ends here. Continue reading the full article.
