Bin packing with restricted item fragmentation

• Autorzy: Pieńkosz K.
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider a generalization of the bin packing problem, in which it is permitted to fragment the items while packing them into bins. There is, however, a restriction that the size of each piece of the fragmented item cannot be smaller than a given parameter β An interesting aspect of such a model is that if β= 0, then the problem can be easily solved optimally. If β is large enough, meaning, in fact, that the fragmentation is not allowed, we get the classical bin packing problem, which is NP-hard in the strong sense. We present approximation algorithms for solving the problem and analyse their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented.

Słowa kluczowe

EN

bin packing; fragmentable items; approximation algorithms

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: Vol. 43, no. 4
• Strony: 547--556
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Pieńkosz K.

• Institute of Control and Computation Engineering, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland

Bibliografia

• 1. Epstein L. and van Stee R. (2008) Approximation schemes for packing splittable items with cardinality constraints. Lecture Notes in Computer Science, 4927, 232-245.
• 2. Fleszar K. and Charalambous C. (2011) Average–weight–controlled bin– oriented heuristics for the one–dimensional bin–packing problem. European Journal of Operational Research, 210, 176 184.
• 3. Garey M.R. and Johnson D.S. (1979) Computers and Intractability: A Guide to the Theory of NP Completeness. W.H. Freeman, San Francisco.
• 4. Johnson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. (1974)Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3, 299-325.
• 5. Mandal C.A., Chakrabarti P.P., Ghose S. (1998) Complexity of fragmentable object bin packing and an application. Computers and Mathematics with Applications, 35, 91-97.
• 6. Menakerman N. and Rom R. (2001) Bin packing with item fragmentation. Lecture Notes in Computer Science, 2125, 313-324.
• 7. Namman N. and Rom R. (2001) Analysis of transmission scheduling with packet fragmentation. Discrete Mathematics and Theoretical Computer Science, 4, 139-156.
• 8. Scholl A., Klein R., Jurgens C. (1997) BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research, 24, 627-645.
• 9. Shachnai H. and Yehezkely O. (2007) Fast asymptotic FPTAS for packing fragmentable items with costs. Lecture Notes in Computer Science, 4639, 482-493.
• 10. Shachnai H., Tamir T., Yehezkely O. (2008) Approximation schemes for packing with item fragmentation. Theory of Computing Systems, 43, 81-98. 547-556.