A new graph-theoretical model for the guillotine-cutting problem

摘要

The two-dimensional orthogonal guillotine-cutting problem (2SP) is deciding whether a given set of rectangles can be cut from a larger rectangle using guillotine cuts that goes from one edge all the way to the opposite edge of a currently available rectangle. The problem occurs in industry if pieces of steel, wood, or paper need to be cut out of larger pieces and is called unconstrained two-dimensional guillotine-cutting problem that is strongly NP-complete. A cutting pattern is a set of coordinates for the items to be cut and the pattern is called guillotine if it can be obtained by guillotine cuts only. One method of solving the two-dimensional guillotine cutting problem is to use restrictions on cutting patterns like staged cutting patterns. This paper addresses the standard guillotine cutting problem using graph theoretical approach called guillotine graph approach and is based on arc-colored graph in which circuits are based on horizontal and vertical builds and can be extended to more than three dimensional cases. It is shown that each guillotine graph can be associated with a specific class of pattern solutions known as a guillotine-cutting class and by the use of guillotine graphs; the dominant subsets of solutions are focused to avoid redundancies in search methods. (22 refs.)