互联网信息组织和规划中的带拒绝装箱问题

摘要

讨论如下定义的带拒绝装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和罚值.物品可以放入箱子也可被拒绝放入箱子.如果将物品放入箱子,则使该箱剩余长度减少.一旦需将某一物品放入某一箱中,而该箱的剩余长度不够时,则需启用新箱子.如果物品被拒绝放入任何箱中,则产生惩罚.问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,来源于内部互联网的信息组织和规划.该文首先给出一个最优解值的下界估计,它可用于分枝定界法求最优解.由于该问题是强NP-难的,该文进一步研究它的离线和在线近似算法的设计与分析.文中给出一个离线算法,其绝对性能比为2;同时给出一个在线算法,其绝对性能比不超过3,渐近性能比为2,还对算法性能比的下界进行了讨论.