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

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

0.00 Avg rating0 Votes
Article ID: iaor20083870
Country: Netherlands
Volume: 172
Issue: 2
Start Page Number: 515
End Page Number: 527
Publication Date: Jul 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: dynamic, programming: integer
Abstract:

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 li, a width Wi, a profit (or weight) ci and an upper demand value bi. 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.

Reviews

Required fields are marked *. Your email address will not be published.