Packing problems consist in placing a collection of objects inside recipients in an economical way. These problems can be of two types depending on the objective under consideration. In the first case, the objective is to minimize the number of recipients used to pack the objects. In the second case, the objects must be packed into only one recipient--whose dimensions are all bounded, except one--and the objective is to minimize the `size' of the packing, measured with respect to the unbounded dimension of the recipient.
In this thesis we consider packing problems where the objects and recipients are 2- or 3-dimensional, and of `orthogonal shape'. Thus, the objects are rectangles or rectangular boxes and the recipients are rectangular strips, rectangular bins, rectangular boxes of unbounded height or rectangular boxes of bounded dimensions (containers). Furthermore, all packings must be orthogonal. We consider the following problems: the strip packing problem, the two-dimensional bin packing problem, the three dimensional packing problem and the container packing problem. These problems are NP-hard, not approximable--in the absolute sense--within certain constants. We present (polynomial) approximation algorithms for these problems and study their asymptotic performance. We describe on-line and off-line algorithms for the oriented case and for the case where orthogonal rotations are allowed.
For the strip packing problem, we present an algorithm with asymptotic performance bound at most 1.62 and an on-line algorithm with asymptotic performance bound 1.75. Both algorithms are for the case where orthogonal rotations are allowed. For the two-dimensional bin packing problem allowing orthogonal rotations, we present an algorithm with asymptotic performance bound at most 2.64 and an on-line algorithm with an asymptotic performance bound of 3.25. For the three-dimensional packing problem, we present an algorithm for the oriented case, with asymptotic performance bound at most 2.67. For the case where orthogonal rotations around the height axis are allowed, we present an algorithm whose asymptotic performance bound is at most 2.67 and another on-line algorithm with an asymptotic performance bound of 3.25. For the container packing problem where orthogonal rotations are allowed, we present an algorithm with asymptotic performance bound at most 4.89 and an on-line algorithm with asymptotic performance bound at most 6.25.
All the bounds above are either new or are improvements of the existing ones in the literature. Moreover, we present results relating the complexity of these problems in the oriented version with the version where orthogonal rotations are allowed. We also present several approximation algorithms for special cases of these problems: packing of squares, of cubes and of `small' objects. For these cases, we describe algorithms whose asymptotic performance bounds are better than those mentioned above.
Keywords: packing problems, approximation algorithms, asymptotic performance bound.
Thesis supervisor: YOSHIKO WAKABAYASHI.
Back to Flávio Keidi Miyazawa's Homepage
This document was generated using the LaTeX2HTML translator Version 96.1-h (September 30, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.