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 Fekete, S. P. Articles by van der Veen, J. C. Search for Related Content

An Exact Algorithm for Higher-Dimensional Orthogonal Packing

Department of Mathematical Optimization, Braunschweig University of Technology, D–38106 Braunschweig, Germany
IBM Germany, Gustav-Heinemann-Ufer 120/122, D–50968 Köln, Germany
Department of Mathematical Optimization, Braunschweig University of Technology, D–38106 Braunschweig, Germany
s.fekete{at}tu-bs.de
schepers{at}de.ibm.com
j.van-der-veen{at}tu-bs.de

Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing feasible packings with our new classes of lower bounds, and other heuristics, we develop a two-level tree search algorithm for solving higher-dimensional packing problems to optimality. Computational results are reported, including optimal solutions for all two-dimensional test problems from recent literature.

This is the third in a series of articles describing new approaches to higher-dimensional packing.

Subject classifications: production; scheduling; cutting stock; trim.
History: Received May 2000; revision received November 2005; accepted April 2006.