A-shaped bin packing: Worst case analysis via simulation

An A-shaped bin packing problem, where the items are cylinders and they must be packed into an A-shaped tower in each bin is considered in this paper. It is a variant of the classical one dimensional bin packing problem. For the off-line version of the problem, it is the same to the classical bin packing problem. For the on-line version of the problem, directly extended and radius-classified heuristics from the classical bin packing are analyzed and compared with the worst case analysis and simulation methods. The worst case analysis shows that the asymptotic competitive ratios of heuristics extended from the next fit, the worst fit, the best fit, the almost worst fit, the harmonics are all infinity except of the first fit with asymptotic competitive ratio 2. The radius-classified heuristics perform as well as in classical bin packing in view of the worst case analysis. Simulation results show that the best fit is the best among the directly extended heuristics and give the equilibrium point of choosing directly extended or radius-classified heuristics for an instance.