郭禾

105

  • 教授     博士生导师   硕士生导师
  • 性别:男
  • 毕业院校:大连理工大学
  • 学位:硕士
  • 所在单位:软件学院、国际信息与软件学院
  • 联系方式:guohe@dlut.edu.cn
  • 电子邮箱:guohe@dlut.edu.cn

访问量:

开通时间:2025.3.31

最后更新时间:2025.3.31

ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER

点击次数:

论文类型:期刊论文

发表时间: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.