About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1995
Conference paper
Guaranteeing fair service to persistent dependent tasks
Abstract
We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control of 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 gets imposed implicitly by the fact that some tasks are in conflict and cannot be scheduled simultaneously. The conflicts are presented in the form of a conflict graph. We define parameters that 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 special 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.