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, characterized by multiple item and bin attributes and by the joint presence of both compulsory and non-compulsory items. The contribution of this paper is twofold: we conduct a worst case analysis applied to the much richer Generalized Bin Packing Problem of two outstanding bin packing algorithms (the First Fit Decreasing and the Best Fit Decreasing algorithms) arising in Transportation and Logistics, and we propose two semi-online algorithms also arising in the fields of Transportation and Logistics. We also show how knowing part of the instance or the whole instance is not enough for computing worst case ratio bounds.