点击次数：

论文类型：期刊论文

发表时间：2011-10-21

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：Scopus、SCIE、EI

卷号：412

期号：45

页面范围：6269-6278

ISSN号：0304-3975

关键字：Online scheduling; Bounded rearrangement

摘要：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.