|
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 speci c 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 Preprint submitted to Elsevier Science assignment problem " provides a simple and e cient 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 e cient on-line algorithm for the dynamic single-resource scheduling problem., |
