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.