Non-Clairvoyant Scheduling: Proportional Fairness and Progress BarsOberseminar Discrete Optimization

by Alexander Lindermayr (University of Bremen)

Monday Jun 16, 2025, 11:15 AM → 12:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Non-clairvoyant scheduling is an online problem, where an algorithm must compute a preemptive schedule over time without any knowledge about processing times and future job releases.
The goal is to minimize the average flow time (response time), a classical and central quality-of-service objective. We study this problem on a single machine, heterogeneous machines, and for arbitrary scheduling polytopes. In this talk, we present the following new directions and results:

 

1)     In the case of simultaneous job arrival, we show small competitive ratios for unrelated machines and polytope scheduling by utilizing the fundamental Proportional Fairness allocation rule from economics and analyzing its properties in the context of preemptive scheduling.

2)     A classical lower bound rules out competitive ratios better than 2 even for simultaneous job arrival. We introduce the concept of progress bars, which give improved adversarial or stochastic estimates of job sizes while we are processing them, and show that we can utilize them for breaking this lower bound.

3)     For the problem with online job arrival, no constant competitive ratio is possible. We apply a minimalistic progress bar and show that a little clairvoyance suffices to achieve constant competitive ratios.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.