|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs
点击次数：
论文类型：期刊论文
发表时间：2015-05-04
发表刊物：INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
收录刊物：SCIE、EI
卷号：92
期号：5
页面范围：873-881
ISSN号：0020-7160
关键字：90B35; 68M20; 68R05; scheduling problem; hierarchical constraint; competitive ratio; semi-online
摘要：In this paper, we consider three versions of semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the makespan. In the first version, we assume that the total size of jobs with lower hierarchy is given and we get the tight bound . In the second one, assume that the total size of jobs in each hierarchy is given and we get the tight bound . In the third one, we assume that the total size of jobs with lower hierarchy is known in advance and a buffer of size K is given to store at most K jobs temporarily. We propose an optimal algorithm with competitive ratio using K=1 and show that a bigger buffer size is not helpful.