Campus Event Calendar

Event Entry

What and Who

Max-min online allocations with a reordering buffer

Rob van Stee
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Friday, 21 May 2010
30 Minutes
E1 4


We consider online scheduling so as to maximize the minimum load,

using a reordering buffer which can store some of the jobs before
they are assigned irrevocably to machines.
For m identical machines, we show
an upper bound of H_{m-1}+1 for a buffer of size m-1.
A competitive ratio below H_m is not possible with any finite buffer size, and
it requires a buffer of size \tilde\Omega(m) to get a ratio of O(\log m).
For uniformly related machines, we show that a
buffer of size m+1 is sufficient to get an approximation ratio
of m, which is best possible for any finite sized buffer.
We show similar results (but with different constructions) for
the restricted assignment model.

These results sharply contrast to the (previously known) results
which can be achieved without the usage of a reordering buffer,
where it is not possible to get a ratio below an approximation
ratio of m already for identical machines, and it is impossible
to obtain an algorithm of finite approximation ratio in the other
two models, even for m=2. Our results strengthen the previous
conclusion that a reordering buffer is a powerful tool and it
allows a significant decrease in the competitive ratio of online
algorithms for scheduling problems. Another interesting aspect of
our results is that our algorithm for identical machines imitates
the behavior of the greedy algorithm on (a specific set of)
related machines, whereas our algorithm for related machines
completely ignores the speeds until the end, and then only uses
the relative order of the speeds.


Rob van Stee
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

online algorithms, scheduling, buffer

Rob van Stee, 05/17/2010 13:50 -- Created document.