Article ID: | iaor200728 |
Country: | Netherlands |
Volume: | 5 |
Issue: | 3 |
Start Page Number: | 353 |
End Page Number: | 370 |
Publication Date: | Sep 2006 |
Journal: | Journal of Mathematical Modelling and Algorithms |
Authors: | Finke G., Brauner N., Lemaire P. |
Keywords: | heuristics |
This paper extends the previous work on multibin packing problems and gives a deeper insight into these models and their complexity, so as to provide a strong framework for future application-oriented studies. In a multibin problem, an object requires several bins to be packed. New models are represented, including the maximum cardinality multibin packing. Their complexity is studied and several pseudo-polynomial time algorithms are described, together with a fully polynomial time approximation scheme for a fixed number of bins.