|
个人信息Personal Information
副教授
硕士生导师
性别：男
毕业院校：大连理工大学
学位：博士
所在单位：计算机科学与技术学院
办公地点：创新园大厦A0827
联系方式：18640987378
电子邮箱：wyx@dlut.edu.cn
Online scheduling with one rearrangement at the end: Revisited
点击次数：
论文类型：期刊论文
发表时间：2012-08-31
发表刊物：INFORMATION PROCESSING LETTERS
收录刊物：SCIE、EI、Scopus
卷号：112
期号：16
页面范围：641-645
ISSN号：0020-0190
关键字：Scheduling problems; Competitive ratio; Online algorithms
摘要：In this paper, we consider an online non-preemptive scheduling problem on two related machines, with only one rearrangement at the end, called Online scheduling with one rearrangement at the end (OSORE). We proposed an improved algorithm for 1 <= s <= 2, where s is the speed ratio between the fast machine and slow machine. The upper bounds are 2(s+1)/s+2 for 1 <= s <= root 2 and s+2/s+1 for root 2 < s <= 2, which are better than previous results. i.e. (s+1)(2)/s+2 for 1 <= s <= root 2 and s+1/s for root 2 < s <= 2 (Liu et al.. 2009 [7]). (C) 2012 Elsevier B.V. All rights reserved.