An exact algorithm of orthogonal 2-D cutting problems using guillotine cuts

We consider the two-dimensional cutting problem which requires cutting a number of small rectangular pieces, each of a given size and value, from a large rectangular stock plate. The objective is to maximize the value of pieces cut, or (for a slightly simpler problem) to minimize the wastage. We consider the case where there is a maximum number of times that a piece may be used in a cutting pattern. We present a tree-search algorithm for this problem in which the size of the tree search is limited by using a bound derived from a state space relaxation of a dynamic programming formulation of the problem. A state space ascent method is used to optimise this bound. The computational performance of the algorithm is investigated by tests performed on randomly generated problems with constraints of varying ‘tightness’. The results indicate that the algorithm is an effective procedure capable of solving optimally practical two-dimensional cutting problems of medium size.