一种松弛的尺寸可变装箱问题及其在线算法

给定物品系列,不同尺寸的箱子依次到达,要求将所有物品装入到箱子中以实现从第一个箱子到最后一个被使用的箱子为止的所有箱子总尺寸最小化.为此给出了6种在线算法,并对这些算法在两种箱子尺寸约束条件下的最坏情形性能和一般情形性能分别进行了研究.理论分析表明最坏情形下6种算法的渐进竞争比在常规约束不小于2,在松弛的约束条件下为无穷;仿真试验表明一般情形下FFD(FirstFitDecreasing)算法最优.

Online algorithms for a relaxed variable-sized bin packing

Given a list of items, how to pack all the items into a list of variable-sized bins arriving in sequence to minimize the total size of bins ranging from the earliest one to the last used one? Two constraints about the size of the bins were considered and the performances of six adapted online algorithms from both of the worst-case and the average-case viewpoints under the two conditions were studied. Worst-case analyses show that the competitive ratios of the six algorithms are not less than 2 if the size of each bin is not less than that of the largest item or are infinite otherwise. Average-case experiments show that the adapted First Fit Decreasing algorithm outperforms any others.