Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope SchedulingResearch Paper
Many computing and production systems share resources among jobs whose sizes are unknown when they arrive: a cluster splits processors among tasks, a network splits link capacity among flows, a factory splits machines among orders. A scheduler that never learns a job's size until the job finishes is called nonclairvoyant. On a single machine the right…