Article ID: | iaor20001500 |
Country: | Netherlands |
Volume: | 94 |
Issue: | 1/3 |
Start Page Number: | 181 |
End Page Number: | 191 |
Publication Date: | May 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Speranza Maria Grazia, Dell'Olmo P. |
Keywords: | bin packing |
A 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 −