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.