This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Hifi, M. Articles by M'Hallah, R. Search for Related Content

An Exact Algorithm for Constrained Two-Dimensional Two-Staged Cutting Problems

LaRIA, Laboratoire de Recherche en Informatique d'Amiens, 5 rue du Moulin Neuf, 80000 Amiens, France; CERMSEM-CNRS UMR 8095, Maison des Sciences Economiques, Université Paris 1 Panthéon-Sorbonne, France; and LRIA-LPBD, EA 3387, EPHE, Paris, France
Department of Statistics and Operations Research, Kuwait University, P.O. Box 5969, Safat 13060, State of Kuwait
hifi{at}univ-paris1.fr
mhallah{at}kuc01.kuniv.edu.kw

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 S with length L and width W, 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 that can be cut on S. In this paper, we study the two-staged C_TDC problem, noted C_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two cuts. We solve the C_2TDC problem using an exact algorithm that is mainly based on a bottom-up strategy. We introduce new lower and upper bounds and propose new strategies that eliminate several duplicate patterns. We evaluate the performance of the proposed exact algorithm on problem instances extracted from the literature and compare it to the performance of an existing exact algorithm.

Subject classifications: dynamic programming; industries; programming:algorithms—branch-and-bound; simulation:applications; efficiency.
History: Received August 2002; revision received October 2003; accepted November 2003.

This article has been cited by other articles:

				M. Hifi, R. M'Hallah, and T. Saadi Algorithms for the Constrained Two-Staged Two-Dimensional Cutting Problem INFORMS Journal on Computing, January 1, 2008; 20(2): 212 - 221. [Abstract] [PDF]