Models and Complexity of Multibin Packing Problems

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 (FPTAS) for a fixed number of bins.