An asymptotic approximation algorithm for 3D-strip packing

ABSTRACT

We present an asymptotic (2 + ε)-approximation algorithm for the 3D-strip packing problem, for any ε > 0. In the 3D-strip packing problem the input is a set L = {b1, b2,. . ., bn} of 3-dimensional boxes. Each box bi has width, length, and height at most 1. The problem is to pack the boxes into a 3-dimensional bin B of width 1, length 1 and minimum height, so that the boxes do not overlap. We consider here only orthogonal packings without rotations; this means that the boxes are packed so that their faces are parallel to the faces of the bin, and rotations are not allowed. This algorithm improves on the previously best algorithm of Miyazawa and Wakabayashi which has asymptotic performance ratio of 2.64. Our algorithm can be easily modified to a (4 + ε)-approximation algorithm for the 3D-bin packing problem.

REFERENCES

• 1: Nikhil Bansal , Maxim Sviridenko, New approximability and inapproximability results for 2-dimensional Bin Packing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: Alberto Caprara, Packing 2-Dimensional Bins in Harmony, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.490-499, November 16-19, 2002
• 3: E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM Journal on Computing, 9, 1980, 808--826.
• 4: J. Csirik and A. van Vliet, An on-line algorithm for multidimensional bin packing, Operations Research Letters, 1993, 13, pp. 149--158.
• 5: José R. Correa , Claire Kenyon, Approximation schemes for multidimensional packing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: Claire Kenyon , Eric Rémila, A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem, Mathematics of Operations Research, v.25 n.4, p.645-656, November 2000 [doi>10.1287/moor.25.4.645.12118]
• 7: Keqin Li , Kam-Hoi Cheng, On three-dimensional packing, SIAM Journal on Computing, v.19 n.5, p.847-867, Oct. 1990 [doi>10.1137/0219059]
• 8: K. Li and K. H. Cheng, A Generalized HARMONIC Algorithm for On-line Multidimensional Bin Packing. University of Houston, Technical Report UH-CS-90-2, 1990.
• 9: K. Li and K. H. Cheng, Heuristic algorithms for on-line packing in three dimensions, Journal of Algorithms, 13, 1992, 589--605.
• 10: F. K. Miyazawa and Y. Wakabayashi, An algorithm for the three-dimensional packing problem with asymptotic performance analysis, Algorithmica, 18, 1997, 122--144.
• 11: F. K. Miyazawa , Y. Wakabayashi, Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem, SIAM Journal on Computing, v.29 n.3, p.1008-1029, Dec. 1999 to Jan. 2000 [doi>10.1137/S009753979631391X]
• 12: F. K. Miyazawa and Y. Wakabayashi, Packing problems with orthogonal rotations, Proceedings of the 6th Latin American Symposium on Theoretical Informatics, 2004, LNCS 2976, 359--368.
• 13: F. K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing, Electronic Notes in Discrete Mathematics, 19, 2005, 313--319.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sequencing and scheduling

General Terms:
Algorithms, Theory