Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints

The paper examines a new problem in the irregular packingliterature that has existed in industry for decades;two-dimensional irregular (convex) bin packing with guillotineconstraints. Due to the cutting process of certain materials, cutsare restricted to extend from one edge of the stock-sheet toanother, called guillotine cutting. This constraint is commonplace in glass cutting and is an important constraints intwo-dimensional cutting and packing problems. In the literature,various exact and approximate algorithms exist for finding the twodimensional cutting patterns that satisfy the guillotine cuttingconstraint. However, to the best of our knowledge, all of thealgorithms are designed for solving rectangular cutting where cutsare orthogonal with the edges of the stock-sheet. In order tosatisfy the guillotine cutting constraint using these approaches,when the pieces are non-rectangular, practitioners implement a twostage approach. First, pieces are enclosed within rectangle shapesand then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. Thispaper aims to generate guillotine-cutting layouts of irregularshapes using a number of strategies. The investigation comparestwo two-stage approaches; one approximates pieces by rectangles,the other approximates pairs of pieces by rectangles usingphi-functions for optimal clustering. Both these approaches usestate of the art rectangle bin packing with guillotineconstraints. Further, we design and implement a one-stage approachusing a self-adapted forest search algorithm. Experimental resultsshow the one-stage strategy to produce good solutions in less timeover the two-stage approach