Capacity scheduling for data services over digital networks

In this paper we present the problem of scheduling the playout of data services over a digital video network. First, we develop a mathematical model of it and analyse its computational complexity. Next, we propose to tackle it by means of local search. To this end, we develop a linear programming approach using column generation to solve the sub-problem of determining absolute times and bit rates, given a relative time ordering and resource assignment. Elaboration of the co-ordinating local search approach, in which we are going to alter relative time orderings and resource assignments, is subject of further research.