Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76831
Type: Artigo
Title: Two-dimensional strip packing with unloading constraints
Author: Silveira, Jefferson L. M. da
Xavier, Eduardo C.
Miyazawa, Flávio K.
Abstract: In this paper we present approximation algorithms for the two-dimensional strip packing problem with unloading constraints. In this problem, we are given a strip S of width 1 and unbounded height, and n items of C different classes, each item a(i) with height h(a(l)), width w(a(l)) and class c(a(i)). As in the strip packing problem, we have to pack all items, minimizing the height used, but now we have the additional constraint that items of higher classes cannot block the way out of items of lower classes. For the case in which horizontal and vertical movements for removing the items are allowed, we design an algorithm whose asymptotic performance bound is 3. For the case in which only vertical movements are allowed, we design a bin packing based algorithm with an asymptotic approximation ratio of 5.745. Moreover, we also design approximation algorithms for restricted cases of both versions of the problem. These problems have practical applications in dealing with routing problems with loading/unloading constraints. (C) 2013 Elsevier B.V. All rights reserved.
In this paper we present approximation algorithms for the two-dimensional strip packing problem with unloading constraints. In this problem, we are given a strip S of width 1 and unbounded height, and n items of C different classes, each item a(i) with he
Subject: Algoritmos de aproximação
Problemas de empacotamento
Roteamento (Administração de redes de computadores)
Country: Países Baixos
Editor: Elsevier
Citation: Discrete Applied Mathematics. Elsevier Science Bv, v. 164, n. 512, n. 521, 2014.
Rights: fechado
fechado
Identifier DOI: 10.1016/j.dam.2013.08.019
Address: https://www.sciencedirect.com/science/article/pii/S0166218X13003600
Date Issue: 2014
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000332427600016.pdf574.74 kBAdobe PDFView/Open


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