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 Caprara, A. Articles by Monaci, M. Search for Related Content

Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing

DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
acaprara{at}deis.unibo.it
alodi{at}deis.unibo.it
mmonaci{at}deis.unibo.it

We present an asymptotic fully polynomial time approximation scheme for the two-dimensional generalization of Bin Packing, which requires packing (or cutting) a given set of rectangles from the minimum number of square bins, with the further restriction that packing the rectangles in the bins is done in two stages, as is frequently the case in real-world applications. To the best of our knowledge, this is the first approximation scheme for a nontrivial two-dimensional (and real-world) generalization of a classical one-dimensional packing problem in which rectangles have to be packed in (finite) squares. In addition to the approximability result, we obtain as a byproduct of our analysis an interesting structural result, namely the asymptotic optimality of the lower bound provided by the natural linear programming relaxation of the problem, having one variable for each bin pattern, that can be solved effectively by column generation techniques. Besides its practical relevance, a main reason to concentrate on the two-stage version of the problem is that its study continues to shed light on the general version. In particular, we strongly conjecture that the approximation guarantee of our algorithm for two-dimensional Bin Packing without the two-stage restriction is better than the best known ones. A simplification of the method leads to an approximation scheme for the two-stage version of two-dimensional Strip Packing.

Key Words: two-dimensional bin packing; two-dimensional strip packing; two-stage packing; asymptotic fully polynomial time approximation scheme; fractional two-dimensional bin packing
History: Received: June 4, 2003; revision received: April 23, 2004;