Portal de Periódicos da CAPES

An algorithm for the 2D guillotine cutting stock problem

1993; Elsevier BV; Volume: 68; Issue: 3 Linguagem: Inglês

10.1016/0377-2217(93)90196-t

1872-6860

Bruce MacLeod, Robert N. Moll, Mahesh Girkar, Nassim Hanifi,

Advanced Manufacturing and Logistics Optimization

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(n3) approximation algorithm for the two-dimensional guillotine cutting stock problem is presented. The algorithm considers each rectangle, in turn, and attempts 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.