论文部分内容阅读
讨论了如下定义的带核元带拒绝装箱问题：设有许多等长的箱子，给定一个带核元的物品集，每个非核元有2个参数：大小和罚值．非核元物品可以放入箱子也可被拒绝放入箱子．如果某物品被拒绝放入箱中，则产生惩罚值，同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1，问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题，在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景．提出了一个求解该问题的局外近似算法，分析其最坏情况渐进性能比为2，并给出了相应的实验结果．