Online bin packing with arbitrary release times
We study a new variant of the online bin-packing problem, in which each item a(i) is associated with a size ai and also a release time r(i) so that it must be placed at least r(i) above the bottom of a bin. Items arrive in turn and must be assigned without any knowledge of subsequent items. The goal is to pack all items into unit-size bins using the minimum number of bins. We study the problem with all items have equal size. First, we show that the ANY FIT algorithm cannot be approximated within any constant. Then we present a best possible online algorithm with asymptotic competitive ratio of two. (C) 2007 Elsevier B.V. All rights reserved.
bin packing online algorithm performance evaluation