Capacity scheduling for data services over digital networks

In this paper we present the problem of scheduling the playout of data serv ices over a digital video network. First, we develop a mathematical model o f it and analyse its computational complexity. Next, we propose to tackle i t by means of local search. To this end, we develop a linear programming ap proach using column generation to solve the sub-problem of determining abso lute times and bit rates, given a relative time ordering and resource assig nment. Elaboration of the co-ordinating local search approach, in which we are going to alter relative time orderings and resource assignments, is sub ject of further research. Copyright (C) 2001 John Wiley & Sons, Ltd.