Windows Scheduling for Broadcasting Data

by
Jacob Christensen

The windows scheduling problem has many practical applications including the problems of minimizing bandwidth in push systems and minimizing startup delay in media-on-demand systems. The windows scheduling problem is defined by the positive integers n, h, and w1, . , wn. There are n jobs where the window wi is associated with job i and h is the number of slotted channels available for broadcasting the jobs. A schedule that solves the problem assigns jobs to slots such that the gap between any two consecutive appearances of job i is at most wi slots. We explore two methods of finding solutions to the windows scheduling problem namely a greedy algorithm and a general buffer scheme. Each method is analyzed with different input sets, some that are strategically designed to expose the effectiveness of one method over another. My work was primarily focused on implementing both the greedy algorithm and the general buffer scheme and performing the experiments.

Advised by Richard Ladner and Tami Tamir

MGH 251
Wednesday
February 11, 2004
3:30 - 4:20 pm