底为正方形的三维装箱问题

A Three Dimensional Packing Method for Square Bottom Instances.

本文讨论如何将一堆底部为正方形，长、宽、高均不超过１的盒子装入一底为１×１，高为正无穷的柱形箱子，使装箱高度Ｚ为最小的问题．该问题已知为ＮＰ难的问题．Ｌｉ和Ｃｈｅｎｇ在１９９０年提出了多项式近似算法Ｃ１，其渐近性能比ｒ（Ｃ１）＝２．６８７５（见参考文献［１］）．本文根据算法Ｃ１的思想，进一步利用盒子底部为正方形的特点，尽可能不浪费高度空间，提出了所谓“单元装箱法”Ｄ，使新算法的渐近性能比得到改进：ｒ（Ｄ）≤２２５１７８４＝２．３２０１５．

This paper discusses how to pack a set of boxes with square bottoms into a box B with a fixed size square bottom and unbounded height such that the height of the packing is minimized. It is required that all boxes be packed into B orthogonally and oriented in all three dimensions.The problem is known to be NP hard.Li and Cheng developed an approximation algorithm C 1 in 1990,of which the worstcase performance ratio is r(C 1)=2.6875 ( reference 1 ). Based on the idea of algorithm C 1 and the characteristics of squares, a new packing method D is developed, of which the worst case performance ratio is r(D)≤2251784=2.32015.