##
Fair On-Line Scheduling of a Dynamic Set of Tasks on a Single Resource

- S.K. Baruah,
J.E. Gehrke,
C.G. Plaxton,
I. Stoica,
H. Abdel-Wahab, and
K. Jeffay
- Information Processing Letters
- Volume 64, Number 1 (October 1997)
- pages 43-51.

*ABSTRACT:*
Consider a set of "tasks" competing for the use of a single "resource,"
where: (i) only one task is allowed to use the resource at a time, (ii)
the resource is scheduled in unit-time intervals, (iii) each task requires
a specific fraction of the resource capacity over an extended period, and
(iv) tasks arrive and depart at any time. We refer to such a task system
as an instance of the single-resource scheduling problem. The problem of
designing a "fair" scheduling algorithm for such task systems has recently
received a great deal of attention in the literature. This paper makes
two main contributions. First, we point out that Tijdeman's work on the
so-called "chairman assignment problem" provides a simple and efficient
on-line algorithm for the static version of the single-resource scheduling
problem (i.e., where the set of tasks competing to use the resource does
not change over time). We then extend Tijdeman's algorithm to obtain a
simple and efficient on-line algorithm for the dynamic single-resource
scheduling problem.

Get a
PostScript - or -
PDF
copy of this paper.

Back to *
Real-Time Systems Research at UNC page.
*