A HEURISTIC SOLUTION OF THE RECTANGULAR CUTTING STOCK PROBLEM

The rectangular cutting stock problem is to determine how to cut a specified number of each of certain types of rectangular pieces out of a given stock of rectangular sheets, the object being to minimise the waste. A special case of this general cutting problem encountered in many practical applications is one in which all cuts have to be accomplished from one edge of the rectangle to the opposite one, i. e. the cut has to be of a 'guillotine' type. For such applications the problem can be formulated as a mathematical optimization program and the optimal solution can be found efficiently in terms of computer time only for problems of medium size. A heuristic method is described for an approximate solution of larger problems, which gives suboptimal results but presents an interesting tradeoff between computing effort and solution optimality.