Guaranteeing Fair Service to Persistent Dependent Tasks

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.

Also appeared inAnnual ACM-SIAM Symposium on Discrete Algorithms (6th) Proceedings. Philidelphia, PA, Association of Computing Machinery, 1995. p. 243-52