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

Mhand Hifi () and Rym M'Hallah ()
Additional contact information
Mhand Hifi: 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
Rym M'Hallah: Department of Statistics and Operations Research, Kuwait University, P.O. Box 5969, Safat 13060, State of Kuwait

Operations Research, 2005, vol. 53, issue 1, 140-150

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 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.

Keywords: dynamic programming; industries; programming:algorithms—branch-and-bound; simulation:applications; efficiency (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0154 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:53:y:2005:i:1:p:140-150

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().