Strip generation algorithms for constrained two-dimensional two-staged cutting stock problems

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W , as to maximize the sum of the profits of the pieces to be cut. Each piece type i , i = 1, …, n , is characterized by a length l i , a width w i , a profit (or weight) c i and an upper demand value b i . The upper demand value is the maximum number of pieces of type i which can be cut on rectangle ( L , W ). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure . We evaluate the performance of these algorithms on instances extracted from the literature.