带核元的带拒绝装箱问题  

Bin packing problem with rejection and kernels

作　　者：杨鼎强[1] 蒋加伏[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,湖南长沙410076

出　　处：《长沙理工大学学报（自然科学版）》2007年第2期59-62,共4页Journal of Changsha University of Science and Technology:Natural Science

基　　金：湖南省教育厅科研资助项目(06C126)

摘　　要：讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.We consider the bin packing problem with list of items,some of them are kernels,each with a c rejection and kernels as follows：given a apacit with equal capacity. An item can be either rejected when it y and penalty,and unlimited bins isn＇t kernel, in which case we pay its penalty,or put in one of the bins. An item can＇t be rejected when it is kernel. A bin can pack only one kernel. The objective is to minimize the sum of the number of the used bins and the penalties of all rejected items. This is a new combinational optimization problem which has many applications such as multi-processor scheduling and management information on web servers,etc. An offline approximation algorithm is presented to solve this problem. It is proved that the algorithm has an asymptotic worst-case performance ratio of 2, finally the experimental results are given.

关 键 词：装箱问题 核元 组合优化 近似算法 最坏情况渐近性能比 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]