|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
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.