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 netwo rks and has not been studied previously. We provide an on-line algorithm fo r the problem with a competitive ratio of O(min{log Delta,log tau}), where Delta is the ratio between the longest and shortest duration of a process, and tau is the maximum number of concurrent active processes that have diff erent durations. For the special case where all durations are powers of two , the competitive ratio achieved is O(log log Delta). (C) 2000 Elsevier Sci ence B.V. All rights reserved.