Proportionate progress: A notion of fairness in resource allocation |
| |
Authors: | S. K. Baruah N. K. Cohen C. G. Plaxton D. A. Varvel |
| |
Affiliation: | (1) Department of Computer Science, University of Texas, 78712-1188 Austin, TX, USA |
| |
Abstract: | Given a set ofn tasks andm resources, where each taskx has a rational weightx.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 allkN. We define a notion of proportionate progress, called P-fairness, and use it to design an efficient algorithm which solves the periodic scheduling problem.This research was supported by NSF Research Initiation Award CCR-9111591, and the Texas Advanced Research Program under Grant No. 91-003658-480. |
| |
Keywords: | Euclid's algorithm Fairness Network flow Periodic scheduling Resource allocation |
本文献已被 SpringerLink 等数据库收录! |
|