Proportionate progress: A notion of fairness in resource allocation
S. K. Baruah1, N. K. Cohen1, C. G. Plaxton1 and D. A. Varvel1
| (1) | Department of Computer Science, University of Texas, 78712-1188 Austin, TX, USA |
Received: 28 May 1993 Revised: 5 January 1995
Communicated by C. L. Lui.
Abstract Given a set of
n tasks and
m resources, where each task
x has a rational weight
x.w=x.e/x.p,0<1, aperiodic schedule is one that allocates a resource to a taskx for exactlyx.e time units in each interval [x.p·k, x.p·(k+1)) for allk
N. We define a notion of proportionate progress, called P-fairness, and use it to design an efficient algorithm which solves the periodic scheduling problem. Key words Euclid's algorithm - Fairness - Network flow - Periodic scheduling - Resource allocation
This research was supported by NSF Research Initiation Award CCR-9111591, and the Texas Advanced Research Program under Grant No. 91-003658-480.
References secured to subscribers.