Professor
Supervisor of Doctorate Candidates
Supervisor of Master's Candidates
Open time:..
The Last Update Time:..
Indexed by:会议论文
Date of Publication:2012-05-14
Included Journals:EI、Scopus
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.