Asymptotic results for the Generalized Bin Packing Problem

We present a worst case analysis for the Generalized Bin Packing Problem, a novel packing problem arising in many Transportation and Logistics settings and characterized by multiple item and bin attributes and by the joint presence of both compulsory and non-compulsory items. As a preliminary worst case analysis has recently been proposed in the literature, we extend this study by proposing semi-online and offline algorithms, extending the well known First Fit Decreasing and Best Fit Decreasing heuristics for the Bin Packing Problem. In particular, we show that knowing part of the instance or the whole instance is not enough for computing worst case ratio bounds.