Dynamic Bin Packing

Abstract

Motivated by potential applications to computer storage allocation, we generalize the classical one-dimensional bin packing model to include dynamic arrivals and departures of items over time. Within this setting, we prove close upper and lower bounds on the worst-case performance of the commonly used First Fit packing algorithm, and, using adversary-type arguments, we show that no on-line packing algorithm can satisfy a substantially better performance bound than that for First Fit.