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

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.