【带核的Bin-packing问题】.pdf

浙江大学硕士学位论文带核的Bin-packing问题

浙江大学硕士学位论文摘要装箱问题是组合优化中最著名的问题之一,也是长期以来被广泛研究的一个问题．它在生产实际中有广泛的应用背景,如在存储、集装箱等实际运用中起重要作用．本文对一类特殊的装箱问题一带核装箱问题进行了分析和探讨,提出了一个近似算法一FFD算法,给出了其渐近性能比一的证明

浙江大学硕士学位论文第一章简介本章简介了装箱问题已有的几种算法及相应的渐近性能比.S1.经典装箱问题 Bin-packing问题即装箱问题作为一个较为实际的问题已被提出许久,目前也已获得了对它的较为美满的方案。所谓装箱问题,即给定有穷的“物品”集合 U分成k个不相交的子集U,U2,U,使得每一个U中的物品的体积之和不超过1且k尽可能的小．我们可把每一个子集U.看作要装人一只单位容量的箱子中的一组物品,其目标是把U中的物品装人尽可能少的箱子中,已经证明装箱问题是强NP完全的(它包含三元划分作为子情况),所以很少有希望找到一个哪怕是关于它的伪多项式时间的最优化算法,但提出了