Back to Search
Start Over
ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER.
- Source :
-
International Journal of Foundations of Computer Science . Aug2014, Vol. 25 Issue 5, p525-536. 12p. - Publication Year :
- 2014
-
Abstract
- In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results: (i) for m > 51 identical machines, we give a 1.5-competitive online algorithm with a buffer of size ⌈1.5m⌉; (ii) for three identical machines, we give an optimal online algorithm with a buffer size six, better than the previous nine; (iii) for m uniform machines, using a buffer of size m, we improve the competitive ratio from 2 + ε to 2 − 1/m+ ε, where ε > 0 is sufficiently small and m is a constant. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 25
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 97729130
- Full Text :
- https://doi.org/10.1142/S0129054114500191