Bin Packing with Restricted Item Fragmentation

• Autorzy: Robert Pieńkosz
• 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. (original abstract)

Słowa kluczowe

EN

Packaging; Operations research

PL

Opakowania; Badania operacyjne

• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: 43
• Numer: nr 4
• Strony: 547--556

Twórcy

autor

Robert Pieńkosz

• Warsaw University of Technology

Bibliografia

• Epstein L.; van Stee R. (2008) Approximation schemes for packing splittable items with cardinality constraints. Lecture Notes in Computer Science, 4927, 232-245.
• Fleszar K.; Charalambous C. (2011) Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. European Journal of Operational Research, 210, 176 184.
• Garey M.R; Johnson D.S. (1979) Computers and Intractability: A Guide to the Theory of NP Completeness. W.H. Freeman, San Francisco.
• 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.
• 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.
• Menakerman N.; Rom R. (2001) Bin packing with item fragmentation. Lecture Notes in Computer Science, 2125, 313-324.
• Namman N.; Rom R. (2001) Analysis of transmission scheduling with packet fragmentation. Discrete Mathematics and Theoretical Computer Science, 4, 139-156.
• 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.
• Shachnai H.; Yehezkely O. (2007) Fast asymptotic FPTAS for packing fragmentable items with costs. Lecture Notes in Computer Science, 4639, 482-493.
• Shachnai H., Tamir T., Yehezkely O. (2008) Approximation schemes for packing with item fragmentation. Theory of Computing Systems, 43, 81-98. 547-556.