Issue |
RAIRO-Theor. Inf. Appl.
Volume 43, Number 2, April-June 2009
|
|
---|---|---|
Page(s) | 239 - 248 | |
DOI | https://doi.org/10.1051/ita:2008027 | |
Published online | 21 October 2008 |
A note on dual approximation algorithms for class constrained bin packing problems
Institute of Computing, University of Campinas, UNICAMP,
P.O. Box 6176, 13083-970, Campinas, SP, Brazil; ecx@ic.unicamp.br; fkm@ic.unicamp.br
Received:
5
July
2006
Accepted:
21
August
2008
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1 + ε for a given ε > 0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes.
Mathematics Subject Classification: 68W25
Key words: Bin packing / approximation algorithms.
© EDP Sciences, 2008
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.