点击次数：

论文类型：期刊论文

发表时间：2014-08-01

发表刊物：INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

收录刊物：SCIE

卷号：25

期号：5

页面范围：525-536

ISSN号：0129-0541

关键字：Online scheduling; competitive ratio; buffer

摘要：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 inverted right perpendicular1.5minverted left perpendicular; (ii) for three identical machines, we give an optimal online algorithm with a buffer size six, better than the previous nine; (iii) for rn uniform machines, using a buffer of size m, we improve the competitive ratio from 2 + epsilon to 2 - 1/m + epsilon, where epsilon > 0 is sufficiently small and en is a constant.