Google Research· Research

Scheduling in a changing world: Maximizing throughput with time-varying capacity

Manish Purohit, Research Scientist, Google Research We introduce new, provably effective algorithms for scheduling jobs without interruptions on cloud infrastructure when machine availability constantly fluctuates. Quick links Paper Share Copy link × In the world of algorithmic job scheduling, computing resources are often viewed as static: a server has a fixed number of CPUs, or a cluster has a constant number of available machines. However, the reality of modern large-scale cloud computing is far more dynamic. Resources fluctuate constantly due to hardware failure, maintenance cycles, or power limitations. More significantly, in tiered scheduling systems , high-priority tasks often claim resources on demand, leaving a time-varying amount of “leftover” capacity for lower-priority batch jobs. Imagine a restaurant where tables are reserved for VIPs at different times; scheduling regular customers on the remaining tables can become a complex puzzle. When these low-priority jobs are non-preemptive — meaning they cannot be paused and resumed later — the stakes are high. …

Announced

11 Feb 2026 10:34 UTC