Windows Scheduling Problems for Broadcast Systems
Amotz Bar-Noy, Richard E. Ladner · SIAM Journal on Computing · 2003
The windows scheduling problem is defined by the positive integers n, h, and w 1 , ...,w n . There are n pages where the windoww i is associated with pagei , and h is the number of slotted channels available for broadcasting the pages. A schedule that solves the problem assigns pages to slots such that the gap between any two consecutive appearances of page i is at most w i slots. We investigate two optimization problems. (i) The optimal windows scheduling problem: given w 1 , ..., w n find a schedule in which h is minimized. (ii) The optimal harmonic windows scheduling problem: given h find a schedule for the windows w i = i in which n is maximized. The former is a formulation of the problem of minimizing the bandwidth in push systems that support guaranteed delay, and the latter is a formulation of the problem of minimizing the startup delay in media-on-demand systems. For the optimal windows scheduling problem we present an algorithm that constructs asymptotically close to optimal schedules, and for the optimal harmonic windows scheduling problem we show how to achieve the largest known n's for all values of h.