Approximation algorithms for partitioning small items in unequal bins to minimize the total size

AbstractA set of items has to be assigned to a set of bins with different sizes. If necessary the size of each bin can be extended. The objective is to minimize the total size, i.e. the sum of the sizes of the bins. In this paper we study both the off-line case and the on-line variant of this problem under the assumption that each item is smaller than any bin. For the former case, when all times are known in advance, we analyze the worst-case performance of the longest processing time heuristic and prove a bound of 2(2 − √2). For the on-line case, where each incoming item has to be assigned immediately to a bin and the assignment cannot be changed later, we give a lower bound of 76 on the worst-case relative error of any on-line algorithm with respect to the off-line problem and we show that a list scheduling algorithm, which assigns the incoming item to the bin with biggest idle space, has a worst-case performance ratio equal to 54. This bound is shown to be tight