带时间效率约束的一维装箱问题

One-Dimensional Packing Problem with Time Efficiency Constraint

摘要: 一维装箱问题是指把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。本文研究了带时间效率约束的一维装箱问题，时间效率约束为不同机器的装箱效率不同，目标是装箱数目近似比与装箱时间近似比的乘积最小。本文给出了一种求解带时间效率约束的一维装箱问题的近似算法，分析了问题的NP-困难性，并证明出目标近似比的乘积为 (其中)。 One dimensional packing problem is to put a certain number of items into some boxes with the same capacity, so that the sum of the sizes of the items in each box does not exceed the box capacity and minimize the number of boxes used. In this paper, we study one-dimensional packing problem with time efficiency constraint. The time efficiency constraint is that different machines have dif-ferent packing efficiency. The aim is to minimize the product of the approximate ratio of the num-ber of packing and the approximate ratio of the time of packing. We present an approximation algo-rithm for the problem and analyze the NP-Hardness. We prove that the algorithm has the approxi-mation ratio is .