Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76830
Type: Artigo de periódico
Title: Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints
Author: de Queiroz, TA
Miyazawa, FK
Abstract: In the oriented Two-Dimensional Strip Packing Problem (2SP), one has to pack a set of rectangular items into a rectangular strip and minimizes the overall strip height used to pack all items. This paper deals with the 2SP under two practical situations. In the first, feasible packings must respect the load balancing and the multi-drop constraints. That is, the center of gravity of the packing at each moment must lie in a safety region, even after a subset of items is unloaded. In the second situation, the load balancing constraint is combined with the load bearing constraint. In a packing that respect the load bearing constraint, the bearing capacity of each item must be respected. That is, there is a maximum tolerable weight that each item can bear. For both situations, we present approximate 0-1 integer linear programming models and heuristics, based on level-packing algorithms and packing on corner points. The level-packing heuristic has an asymptotic approximation ratio bounded by 1.75, when the number of orders is bounded by a constant. The heuristics have proven to be helpful when combined with the integer models. In addition, many computational experiments validate the integer models and show that they are suitable to deal with problems where the number of possible positions to arrange the items in the bin is small. (C) 2013 Elsevier B.V. All rights reserved.
Subject: Two-dimensional strip packing problem
Integer programming
Load balancing constraints
Multi-drop requirements
Load bearing constraints
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.ijpe.2013.04.032
Date Issue: 2013
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.