Google Research has introduced provably effective algorithms for scheduling non-preemptive jobs on cloud infrastructure with time-varying capacity. The research, presented at SPAA 2025, addresses the challenge of maximizing throughput when machine availability constantly fluctuates due to hardware failures, maintenance cycles, or power limitations.

Traditional scheduling models assume static resources, but modern cloud computing requires handling dynamic capacity changes. In tiered scheduling systems, high-priority tasks often claim resources on demand, leaving unpredictable capacity for lower-priority batch jobs. The stakes are particularly high for non-preemptive jobs that cannot be paused and resumed, as interruptions result in complete loss of progress.

The research provides the first constant-factor approximation algorithms for several problem variants. For the offline setting, a simple Greedy strategy achieves a 1/2-approximation guarantee, while more complex primal-dual frameworks handle jobs with varying profits. The online setting proves more challenging, with standard algorithms failing completely due to the inability to handle long jobs that block future opportunities.

To address online scheduling, the team developed algorithms that allow job interruptions with restarts, achieving a 1/2-competitive ratio. For the stricter interruption-without-restarts model, they devised novel algorithms for common-deadline scenarios, achieving a competitive ratio of 1/11. These theoretical foundations enable building more robust schedulers for volatile cloud environments.