【作者】 陈锋； 邢文训；

【Author】 CHEN Feng XING Wenxun Department of Mathematical Sciences, Tsinghua University, Beijing 100084

【机构】 清华大学数学科学系；

【摘要】 本文探讨了一类新的装箱问题——塔状装箱问题(Tower-shaped bin packing),在该问题中物品均为圆柱形,且为保证稳定性每只箱子中的物品都要摆放成塔状,即上层物品的半径不能大于下层物品的半径,多数经典装箱问题的启发式算法都可以推广应用于该问题,在第三和第四节中分别讨论了两类塔状装箱问题的启发式算法,结果表明直接推广的启发式算法(Directly-extended heuristics)的性能较坏,有些算法的渐近最坏比甚至可以任意大。如果物品的半径有有限多种,某些按半径分类的启发式算法(Radius-classified heuristics)的性能较好。更多还原

【Abstract】 A new variant of the classical bin packing problem(BP) which arises in practical problems is presented in this paper. It is tower-shaped bin packing problem(TSBP), where the items are cylinders and they must be packed into the shape of a tower in each bin, i.e. the radius of any item can not be less than that of the item above it. TSBP includes BP as a special case. Most heuristics of BP can be extended to TSBP, and we evaluate the performance of two kinds of extended heuristics. The results show that the directly-extended heuristics perform badly, and the asymptotic worst case ratios of some of them 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 which they are based on.更多还原