Indexed by:Conference Paper

Date of Publication:2012-05-14

Included Journals:Scopus、EI

Volume:7285 LNCS

Page Number:161-171

Abstract:In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results, which improve on work from FOCS 2008: i) for m identical machines, we give a 1.5-competitive online algorithm with a buffer of size 1.5m, which is better than the previous best result: 1.5-competitive algorithm with a buffer of size 1.6197m; ii) for three identical machines, to give an optimal online algorithm we reduce the size of the buffer from nine to six; 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. ? 2012 Springer-Verlag.