Indexed by:Journal Article

Date of Publication:2011-10-21

Journal:THEORETICAL COMPUTER SCIENCE

Included Journals:EI、SCIE、Scopus

Volume:412

Issue:45

Page Number:6269-6278

ISSN:0304-3975

Key Words:Online scheduling; Bounded rearrangement

Abstract:In this paper, we consider an online non-preemptive scheduling problem on two related machines, where at most K jobs are allowed to be rearranged, but only after all jobs have been revealed and (temporarily) scheduled. We minimize the makespan, and we call the problem as Online scheduling with bounded rearrangement at the end (BRE), which is a semi-online problem. Jobs arrive one by one over list. After all the jobs have been arrived and scheduled, we are informed that the input sequence is over; then at most K already scheduled jobs can be reassigned. With respect to the worst case ratio, we close the gap between the lower bound and upper bound, improving the previous result as well.
   Especially, for the lower bound, (i) for s >= 2 an improved lower bound s+2/s+1 is obtained, which is better than (s+1)(2)/s(2)+s+1 (Liu et al. (2009) [9]); (ii) for 1+root 5/2 <= s < 2, an improved lower bound s(2)/s(2)-s+1 is obtained, which is better than (s+1)(2)/s(2)+s+1 (Liu et al. (2009) [9]). For the upper bound, (i) for s >= 2 and K = 1, a new upper bound s+2/s+1 is obtained, which is optimal and better than the one s+1/s in Liu et al. (2009) [9]; (ii) for 1+root 5/2 <= s < 2 and K = 2, an upper bound s(2)/s(2)-s+1 is proposed, which is optimal and better than the previous one s-1/s in Liu et al. (2009) [9]; (iii) for s < 1+root 5/2 and K = 2, an upper bound (s+1)(2)/s(2)+s+1 is obtained, which is also optimal and better than the previous one min{s+1/s, (s+1)(2)/s+2} in Liu et al. (2009) [9]. (C) 2011 Elsevier B.V. All rights reserved.