A Solution of the Rectangular Cutting-Stock Problem

Abstract
A method of solving a version of the two-dimensional cutting-stock problem is presented. In this version of the problem one is given a number of rectangular sheets and an order for a specified number of each of certain types of rectangular shapes. The goal is to cut the shapes out of the sheets in such a way as to minimize the waste. However, in many practical applications computation time is also an important economic consideration. For such applications the goal may be to obtain the best solution possible without using excessive amounts of computation time. The method of solution described here avoids exhaustive search procedures by employing an approach utilizing a constrained dynamic programming algorithm to lay out groups of rectangles called strips. This paper also describes the results obtained when the algorithm was tested with some typical rectangular layout problems.

This publication has 7 references indexed in Scilit: