带启动重量的脆度装箱问题  

Fragile bin-packing problem with start-up weight

作　　者：杨鼎强[1] 刘林浩[1] 单树民[1] 

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

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

基　　金：湖南省科技厅科研计划资助项目(2011GK3120)

摘　　要：讨论如下定义的带启动重量的脆度装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数(脆度和重量),若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小.该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配.本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果.A fragile bin-packing problem with start-up weight is discussed in this paper. Supposing there are many one-dimensional boxes with the same size and a list of objects which have two attributes-fragility and weight. The bin needs to be put some additional start-up weight if the bin is filled with objects for the first time. Make sure that the total weight of the every bin and the objects within the bins can not exceed the minimum fragility of the objects inside the bin. Using the fewest bins to arrange the objects is a new combina- torial optimization problem which comes from the channel allocation in CDMA cellular com- munication system. A linear off-line approximation algorithm C-NFI is offered to solve the problem. It proves that the C-NFI algorithm has an asymptotic worst case performance rati- o of 2 and the corresponding experimental results are given.

关 键 词：信道分配 装箱问题 脆度 最坏情况渐进性能比 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]