AN EXACT ALGORITHM FOR 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 maximise th e value of pieces cut, or (for a slightly simpler problem) to minimise 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 searc h is limited by using a bound derived from a state space relaxation of a dynamic programming formulation of the problem. A state space ascen t method is used to optimise this bound. The computational performance of the algorithm is investigated by tests performed on randomly gener ated problems with constraints of varying 'tightness'. The results ind icate that the algorithm is an effective procedure capable of solving optimally practical two-dimensional cutting problems of medium size.