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

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.