PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Bin packing with restricted item fragmentation

Autorzy
Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
547--556
Opis fizyczny
Bibliogr. 10 poz., rys.
Twórcy
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-c0d44c2a-6411-44f7-990d-c09e0550c768
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.