Fair on-line scheduling of a dynamic set of tasks on a single resource

✍ Scribed by Sanjoy K. Baruah; Johannes E. Gehrk; C.Greg Plaxton; Ion Stoica; Hussein Abdel-Wahab; Kevin Jeffay

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 841 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00149-x

✦ Synopsis

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. @