SimPFair: tight fairness at low cost

The fair allocation of resources is a central problem in scheduling. In its minimal formulation, given a number of tasks (demands in manufacturing, flows in networking, etc.) modeled by a utilization, the goal of the scheduler is to allocate resources as close as possible to an ideal fluid allocation. The lag measures the distance from the ideal schedule. A scheduler is normally called fair if it guarantees a bounded lag. Motivated by the observation that a lower lag implies a greater proximity to the ideal resource allocation, in this paper, we propose a scheduling algorithm that produces schedules with lower lag bounds. We accompany our algorithm with some tightness results, showing that below a certain bound, no feasible schedule exists.