English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Max-min Online Allocations with a Reordering Buffer

MPS-Authors
/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Epstein, L., Levin, A., & van Stee, R. (2011). Max-min Online Allocations with a Reordering Buffer. SIAM Journal on Discrete Mathematics, 25(3), 1230-1250. doi:10.1137/100794006.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-124C-E
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.