论文部分内容阅读
本文给出一类新的装箱问题,超尺寸物品装箱问题.就实际解决该问题所普遍采用的两步法,证明了当采用经典目标函数并且拆分次数不超过2时,第二步采用FFDLR的渐进最坏比为3/2.进而针对超尺寸物品装箱问题的算法提出了一个评价效率更高的目标函数.证明了在此目标函数下,当不限制物品的最大尺寸时,第二步采用最优装法的两步法的渐近最坏比为2.最后,给出了渐近最坏比与拆分次数的关系.