Dynamic storage allocation with known durations

This paper is concerned with a new version of on-line storage allocation in which the durations of all processes are known at their arrival time. This version of the problem is motivated by applications in communication networks and has not been studied previously. We provide an on-line algorithm for the problem with a competitive ratio of O(min{log 3,log τ}), where 3 is the ratio between the longest and shortest duration of a process, and is the maximum number of concurrent active processes that have different durations. For the special case where all durations are powers of two, the competitive ratio achieved is O(log log 3).