AN AND/OR-GRAPH APPROACH TO THE SOLUTION OF 2-DIMENSIONAL NON-GUILLOTINE CUTTING PROBLEMS

This work is concerned with unconstrained two-dimensional non-guillotine cutting problems, where a rectangular plate is cut into a number of rectangular pieces in such a way as to optimize an objective function. We reduce the state-space of the problem by considering non-guillotine cutting patterns which are combinations of guillotine and simple non-guillotine cuts. These cutting patterns are represented as complete paths in an AND/OR-graph and a branch and bound method is described. We provide rules and heuristics that reduce the graph search and present computational results from randomly generated examples as well as from the literature.