hide
Free keywords:
-
Abstract:
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 fixed
buffer size, and it requires a buffer of size $\Omega(m/\log 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 a competitive ratio of $m$, which is best possible
for any fixed sized buffer.
We show similar results (but with different constructions) for
the restricted assignment model. We give tight bounds for two machines in all
the three models.
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 a competitive
ratio of $m$ already for identical machines, and it is impossible
to obtain an algorithm of finite competitive 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 a greedy algorithm on (a specific set of)
related machines, whereas our algorithm for related machines
completely ignores the speeds until all jobs have arrived, and then only uses
the relative order of the speeds.
