We formulate the problem of video on demand (VOD) from a resource allocation perspective. We introduce the decision element into a movie vending environment, which complements the current approaches. In contrast with the traditional resource allocation problems (e.g., machine scheduling), the problem possesses the distinctive batching property, which stands for the feasibility of several requests being served by one resource. First, we investigate the problem in an on-line fashion, namely, having to accept or reject a request for a movie without any knowledge about future requests. We show upper and lower bounds on the competitive ratio of on-line movie scheduling algorithms for a variety of scenarios depending on the notification time. In particular, when the length of the movie and the notification time on requests are linearly related, we present a simple competitive algorithm. Second, we propose a new approach - Shared VOD - which gives a more balanced functionality/price tradeoff than the two popular approaches full VOD and near VOD. In this approach, several users may share the same channels, but the movies are selected by the users themselves. In this framework, we evaluate a variety of on-line channel allocation algorithms under "typical" conditions. We compare these strategies to the off-line strategy, and show that the algorithm we introduce substantially outperforms the rest. 2002 Elsevier Science B.V. All rights reserved.
