On-line A-shaped bin packing

This paper presents a new variant of the classical bin packing problem (BP) named A-shaped bin packing (ASBP). In ASBP, the items are cylindrical and they must be packed into an A-shape in each bin, i.e. an item's radius cannot be less than that of the item above it. ASBP includes BP as a special case. Most heuristics of BP can be extended to ASBP, and we evaluate the performance of two kinds of extended heuristics on the criterion of asymptotic worst case analysis. The results show that the directly-extended heuristics perform badly and the asymptotic worst case ratios of some can even be arbitrarily large. But if the number of different radii is finite, some radius-classified heuristics can behave as well as those BP heuristics from which they are derived.