A note on dual approximation algorithms for class constrained bin packing problems

Xavier, Eduardo C.; Miyazawa, Flàvio Keidi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 239-248.

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 $c_e$ and size $s_e$. 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+\epsilon$ for a given $\epsilon >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.

Classification : 68W25
Mots clés : bin packing, approximation algorithms

[1] M. Dawande, J. Kalagnanam and J. Sethuranam, 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] J.S. Ferreira, M.A. Neves and P. Fonseca E Castro, A two-phase roll cutting problem. Eur. J. Oper. Res. 44 (1990) 185-196. | Zbl

[3] S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput. 24 (1998) 91-122. | Zbl

[4] L. Golubchik, S. Khanna, S. Khuller, R. Thurimella and A. Zhu, Approximation algorithms for data placement on parallel disks, in Proceedings of SODA (2000) 223-232. | MR | Zbl

[5] D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for schedulling problems: practical and theoretical results. J. ACM 34 (1987) 144-162. | MR

[6] R. Hoto, M. Arenales and N. Maculan, The one dimensional compartmentalized cutting stock problem: a case study. Eur. J. Oper. Res. 183 (2007) 1183-1195. | MR | Zbl

[7] J.R. Kalagnanam, M.W. Dawande, M. Trumbo and H.S. Lee, The surplus inventory matching problem in the process industry. Oper. Res. 48 (2000) 505-516.

[8] S.R. Kashyap and S. Khuller, Algorithms for non-uniform size data placement on parallel disks. J. Algorithms 60 (2006) 144-167. | MR | Zbl

[9] F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res. 34 (2007) 2109-2129. | MR | Zbl

[10] M. Peeters and Z. Degraeve, The co-printing problem: A packing problem with a color constraint. Oper. Res. 52 (2004) 623-638. | MR | Zbl

[11] H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica 29 (2001) 442-467. | MR | Zbl

[12] H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling 4 (2001) 313-338. | MR | Zbl

[13] H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica 32 (2002) 651-678. | MR | Zbl

[14] H. Shachnai and T. Tamir, 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] H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci. 321 (2004) 103-123. | MR | Zbl

[16] G.J. Woeginger, 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] J.L. Wolf, P.S. Wu and H. Shachnai, Disk load balancing for video-on-demand-systems. Multimedia Syst. 5 (1997) 358-370.

[18] E.C. Xavier and F.K. Miyazawa, Approximation schemes for knapsack problems with shelf divisions. Theoret. Comput. Sci. 352 (2006) 71-84. | MR | Zbl

[19] E.C. Xavier and F.K. Miyazawa, The class constrained bin packing problem with applications to video-on-demand. Theoret. Comput. Sci. 393 (2008) 240-259. | MR | Zbl

[20] E.C. Xavier and F.K. Miyazawa, A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math. 156 (2008) 1083-1096. | MR | Zbl