Windows Scheduling
Richard Ladner, University of Washington
october 8, 2004

Abstract

The windows scheduling is a periodic scheduling problem defined by a sequence of positive integers (w_1, w_2, ... , w_n), where w_i represents an upper bound on how often job i should be scheduled on a set of processors. Jobs are of unit size, two jobs cannot be scheduled on the same processor at the same time and once a job has started it cannot be preempted. The optimization goal is to find the minimum number of processors needed for a window scheduling instance. Applications of windows scheduling include scheduling media in media-on-demand systems and media push systems that periodically display stock prices, sports scores, and advertisements on cable channels. We discuss the complexity of windows scheduling, approximation algorithms, restrictions, and extensions.

This is joint work with Amotz Bar-Noy and Tami Tamir.