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 Google Scholar Google Scholar Articles by Hifi, M. Articles by Saadi, T. Search for Related Content

Algorithms for the Constrained Two-Staged Two-Dimensional Cutting Problem

Laboratoire de Recherche en Informatique d'Amiens, FRE 2733, Université de Picardie Jules Verne, 80000 Amiens, France
Department of Statistics and Operations Research, Kuwait University, Safat 13060, Kuwait
Centre de Recherche en Mathématiques, Statistique et Economie Mathématique, CNRS UMR 8095, MSE, Université Paris 1, 75013 Paris, France
hifi{at}laria.u-picardie.fr
mhallah{at}kuc01.kuniv.edu.kw
toufik.saadi{at}malix.univ-paris1.fr

This paper solves FC_2TDC, the two-staged fixed-orientation two-dimensional cutting stock problem. FC_2TDC is a variant of the constrained two-dimensional cutting problem where each piece is produced, in the final cutting pattern, by at most two cuts, and each piece has a fixed orientation. It is solved by an algorithm that combines a strip-generation procedure with beam search (BS). BS, which is a truncated branch-and-bound, investigates a subset of elite nodes and permanently fathoms the others. It chooses the elite nodes based on an evaluation operator. The importance of the evaluation operator on the performance of BS is highlighted by comparing a local beam search (LBS) that uses a priority cost-evaluation operator to a global beam search (GBS) that adopts a global cost-evaluation operator. Computational results, based on several medium and large instances, further show that LBS provides good solutions, whereas GBS gives (near) optimal solutions within reasonable computational time.

Key words: integer programming; cutting stock; deterministic dynamic programming; algorithms; heuristics
History: received May 2006; revised October 2006; accepted April 2007.