【摘要】 讨论如下定义的带启动重量的脆度装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数(脆度和重量),若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小.该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配.本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果.更多还原

【Abstract】 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 combinatorial optimization problem which comes from the channel allocation in CDMA cellular communication 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 ratio of 2 and the corresponding experimental results are given.更多还原