Non-Clairvoyant Scheduling with Progress Bars

In non-clairvoyant scheduling, the goal is to minimize thetotal job completion time without prior knowledge of individualjob processing times. This classical online optimization problemhas recently gained attention through the framework oflearning-augmented algorithms.

We introduce a natural setting in which the scheduler receives continuous feedback in the form ofprogress bars—estimates of the fraction of each job completed over time. We design new algorithms for both adversarial and stochastic progress barsand prove strong competitive bounds.

Our results in the adversarial case surprisinglyinduce improved guarantees for learning-augmented scheduling with job size predictions. We also introduce a general method for combining scheduling algorithms, yieldingfurther insights in scheduling with predictions.

Finally, we propose a stochasticmodel of progress bars as a more optimistic alternative to conventional worst-casemodels, and present an asymptotically optimal scheduling algorithm in this setting.