点击次数：

论文类型：会议论文

发表时间：2012-05-14

收录刊物：EI、Scopus

卷号：7285 LNCS

页面范围：161-171

摘要：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.