Max-min online allocations with a reordering buffer

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.