超尺寸物品装箱问题及其算法

本文探讨一类新装箱问题-超尺寸物品装箱问题。针对实际解决该问题的两涉法，我们提出了一个评价效率更高的目标函数，证明了在此目标函数下两步法的渐近最坏比不小于2，并给出了渐近量坏比与拆分次数的关系。最后本文提出了一种不同于两步法的新在线算法MA，证明了在新目标函数下其渐近最坏比不超过7/4。

BIN PACKING PROBLEM WITH OVER SIZED ITEMS AND A NEW ALGORITHM

A new variation of bin packing, the bin packing problem with over sized items, is discussed in this paper. A two-step procedure, which is practically adopted, is analyzed. We use a more effective objective function to evaluate the new problem, then find that the asymptotic worst case performance ratio of the algorithm TOPT(the optimal two-step algorithm) is 2 if there is no Iimit on the size of items, and the relationship between the asymptotic worst case performance ratio and the spilt time. Finally a new on-line algorithm, with the asymptotic worst case performance ratio not larger than under the new objective function, is presented.