Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2012-08-31

Journal: INFORMATION PROCESSING LETTERS

Included Journals: Scopus、EI、SCIE

Volume: 112

Issue: 16

Page Number: 641-645

ISSN: 0020-0190

Key Words: Scheduling problems; Competitive ratio; Online algorithms

Abstract: 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.