Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/54825
Type: Artigo de periódico
Title: Approximation algorithms for the orthogonal Z-oriented three-dimensional packing problem
Author: Miyazawa, FK
Wakabayashi, Y
Abstract: We present approximation algorithms for the orthogonal z-oriented three-dimensional packing problem (TPPz) and analyze their asymptotic performance bound. This problem consists in packing a list of rectangular boxes L = (b(1),b(2),...,b(n)) into a rectangular box B = (l, w, infinity), orthogonally and oriented in the z-axis, in such a way that the height of the packing is minimized. We say that a packing is oriented in the z-axis when the boxes in L are allowed to be rotated (by ninety degrees) around the z-axis. This problem has some nice applications but has been less investigated than the well-known variant of it-denoted by TPP (three-dimensional orthogonal packing problem)-in which rotations of the boxes are not allowed. The problem TPP can be reduced to TPPz. Given an algorithm for TPPz, we can obtain an algorithm for TPP with the same asymptotic bound. We present an algorithm for TPPz, called R, and three other algorithms, called LS, BS, and SS, for special cases of this problem in which the instances are more restricted. The algorithm LS is for the case in which all boxes in L have square bottoms; BS is for the case in which the box B has a square bottom, and SS is for the case in which the box B and all boxes in L have square bottoms. For an algorithm A, we denote by r(A) the asymptotic performance bound of A. We show that 2.5 less than or equal to r(R) < 2.67, 2.5 less than or equal to r(LS) less than or equal to 2.528, 2.5 less than or equal to r(BS) less than or equal to 2.543, and 2.333 less than or equal to r(SS) less than or equal to 2.361. The algorithms presented here have the same complexity O(n log n) as the other known algorithms for these problems, but they have better asymptotic performance bounds.
Subject: approximation algorithms
three-dimensional packing
asymptotic performance bound
Country: EUA
Editor: Siam Publications
Rights: aberto
Identifier DOI: 10.1137/S009753979631391X
Date Issue: 2000
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.