点击次数：

论文类型：期刊论文

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