Proportional fairness matches single machine scheduling in complex environments
Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling
Data Structures and Algorithms
Summary
Scheduling jobs fairly and efficiently on multiple machines with unknown job lengths is a tough problem. The authors study a method called Proportional Fairness (PF), which was previously known to work well on a single machine. They show that PF keeps its strong performance guarantees even in more complex scenarios like unrelated machines, disproving earlier doubts. They also improve the best-known performance bounds for general job scheduling problems and introduce new mathematical insights to explain why PF works well in these settings.
What this means in practice
- •For cloud resource schedulers: Optimize job allocations across heterogeneous servers without needing prior job length estimates using the improved bounds for proportional fairness.
- •For data center operators: Better guarantee on scheduling efficiency when distributing workloads over unrelated machines, reducing delays and improving throughput under unknown job sizes.
Authors
Alexander Lindermayr, Sven Jäger, Bart Zondervan
Abstract
The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is $2$-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and $(2+\varepsilon)$-speed $O(1/\varepsilon)$-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not $O(1)$-speed $O(1)$-competitive for weighted flow time. Our main technical contribution is an equivalent characterization: a polytope is support submodular if and only if, for all job weights, the optimal weighted completion time is concave in the processing requirements. This structural insight underlies both guarantees. For general PSP, the picture changes: we give the first lower bound above $2$, showing that every randomized nonclairvoyant algorithm has a competitive ratio of at least $2+10^{-5}$ for weighted completion time, even with uniform release dates. On the positive side, we substantially improve the best known guarantee for weighted completion time from $27$ (SICOMP'26) to $4$ via a new dual-fitting analysis of PF. For weighted flow time, we show that PF achieves the first $O(1)$-speed $O(1)$-competitive nonclairvoyant guarantee for graph scheduling.