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 , and items of different classes, each item with class and size . 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 . 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 bins, such that, the total size of all items and shelf divisors packed in any bin is at most for a given and 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 different classes.
Mots-clés : bin packing, approximation algorithms
@article{ITA_2009__43_2_239_0,
author = {Xavier, Eduardo C. and Miyazawa, Fl\`avio Keidi},
title = {A note on dual approximation algorithms for class constrained bin packing problems},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {239--248},
publisher = {EDP-Sciences},
volume = {43},
number = {2},
year = {2009},
doi = {10.1051/ita:2008027},
mrnumber = {2512257},
zbl = {1166.68368},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2008027/}
}
TY - JOUR AU - Xavier, Eduardo C. AU - Miyazawa, Flàvio Keidi TI - A note on dual approximation algorithms for class constrained bin packing problems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2009 SP - 239 EP - 248 VL - 43 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2008027/ DO - 10.1051/ita:2008027 LA - en ID - ITA_2009__43_2_239_0 ER -
%0 Journal Article %A Xavier, Eduardo C. %A Miyazawa, Flàvio Keidi %T A note on dual approximation algorithms for class constrained bin packing problems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 239-248 %V 43 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2008027/ %R 10.1051/ita:2008027 %G en %F ITA_2009__43_2_239_0
Xavier, Eduardo C.; Miyazawa, Flàvio Keidi. A note on dual approximation algorithms for class constrained bin packing problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 239-248. doi : 10.1051/ita:2008027. http://www.numdam.org/articles/10.1051/ita:2008027/
[1] , and , Variable sized bin packing with color constraints, in Proceedings of the 1th Brazilian Symposium on Graph Algorithms and Combinatorics. Electronic Notes in Discrete Mathematics 7 (2001). | Zbl
[2] , and , A two-phase roll cutting problem. Eur. J. Oper. Res. 44 (1990) 185-196. | Zbl
[3] and , Design and implementation of scalable continous media servers. Parallel Comput. 24 (1998) 91-122. | Zbl
[4] , , , and , Approximation algorithms for data placement on parallel disks, in Proceedings of SODA (2000) 223-232. | MR | Zbl
[5] and , Using dual approximation algorithms for schedulling problems: practical and theoretical results. J. ACM 34 (1987) 144-162. | MR
[6] , and , The one dimensional compartmentalized cutting stock problem: a case study. Eur. J. Oper. Res. 183 (2007) 1183-1195. | MR | Zbl
[7] , , and , The surplus inventory matching problem in the process industry. Oper. Res. 48 (2000) 505-516.
[8] and , Algorithms for non-uniform size data placement on parallel disks. J. Algorithms 60 (2006) 144-167. | MR | Zbl
[9] and , The constrained compartmentalized knapsack problem. Comput. Oper. Res. 34 (2007) 2109-2129. | MR | Zbl
[10] and , The co-printing problem: A packing problem with a color constraint. Oper. Res. 52 (2004) 623-638. | MR | Zbl
[11] and , On two class-constrained versions of the multiple knapsack problem. Algorithmica 29 (2001) 442-467. | MR | Zbl
[12] and , Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling 4 (2001) 313-338. | MR | Zbl
[13] and , Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica 32 (2002) 651-678. | MR | Zbl
[14] and , Approximation schemes for generalized 2-dimensional vector packing with application to data placement, in Proceedings of 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX. Lect. Notes Comput. Sci. 2764 (2003) 165-177. | MR
[15] and , Tight bounds for online class-constrained packing. Theoret. Comput. Sci. 321 (2004) 103-123. | MR | Zbl
[16] , When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)? INFORMS J. Comput. 12 (2000) 57-74. | MR | Zbl
[17] , and , Disk load balancing for video-on-demand-systems. Multimedia Syst. 5 (1997) 358-370.
[18] and , Approximation schemes for knapsack problems with shelf divisions. Theoret. Comput. Sci. 352 (2006) 71-84. | MR | Zbl
[19] and , The class constrained bin packing problem with applications to video-on-demand. Theoret. Comput. Sci. 393 (2008) 240-259. | MR | Zbl
[20] and , A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math. 156 (2008) 1083-1096. | MR | Zbl
Cité par Sources :
