Proportionate progress: A notion of fairness in resource allocation

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.