We introduce a new scheduling problem that is motivated by
applications in the area of access and flow-control in high-speed
and wireless networks. An instance of the problem consists of
a set of persistent tasks that have to be scheduled repeatedly.
Each task has a demand to be scheduled ``as often as possible''.
There is no explicit limit on the number of tasks that can be
scheduled concurrently. However, such limits are imposed implicitly
because some tasks may be in conflict and cannot be scheduled
simultaneously. These conflicts are presented in the form of
a conflict graph. We define parameters which quantify the fairness
and regularity of a given schedule. We then proceed to show
lower bounds on these parameters, and present fair and efficient
scheduling algorithms for the case where the conflict graph
is an interval graph. Some of the results presented here extend
to the case of perfect graphs and circular-arc graphs as well.
Joint work with:
Alain Mayer (columbia University)
Baruch Schieber (IBM T. J. Watson Research Center)
Madhu Sudan (IBM T. J. Watson Research Center)