An algorithm for the 2D guillotine cutting stock problem

The two-dimensional guillotine cutting stock problem seeks to apply a sequence of guillotine (edge to edge) cuts to extract a collection of smaller rectangles from a stock piece. In this paper an O(n³) approximation algorithm for the two-dimensional guillotine cutting stock problem is presented. The algorithm considers each rectangle, in turn, and attmepts to locate a guillotine feasible position on the stock piece. The algorithm has the property that a position will be located for the n-th rectangle if and only if such a feasible placement exists. This paper establishes the efficiency and effectiveness of the new algorithm by presenting computational results.