在线A形装箱问题

On-line A-shaped Bin Packing

研究了一类有实际背景的新的装箱问题—— A形装箱问题 (ASBP)的在线情形 .在 ASBP中物品均为圆柱形 ,并且在每个箱子中物品均摆放成 A字形 ,即后到达的物品放在先到达的物品之上且上层物品的截面半径不超过下层物品的截面半径 ,优化目标是最小化装下所有物品所用的箱子数 .当所有物品半径都相同时 ASBP退化成经典一维装箱问题 (BP) ,故 BP为 ASBP的特殊情形 .BP的大多数启发式算法可以推广到 ASBP中 ,我们从最坏情形分析的角度讨论了两类 ASBP启发式算法 .证明了直接推广的启发式算法性能较差 ,其中一些算法的渐近最坏比甚至可以任意大 ;如果半径的种类有限 ,按半径分类的启发式算法的性能较好 ,并且一些算法的渐近最坏比和它们所基于的

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 can not 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