点击次数：

论文类型：期刊论文

发表时间：2011-03-04

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI

卷号：412

期号：8-10

页面范围：642-653

ISSN号：0304-3975

关键字：Scheduling problems; Competitive analysis; Online algorithms

摘要：In this paper, we consider an online non-preemptive scheduling problem on two related machines with rearrangement to minimize the completion time, called online scheduling with bounded rearrangement, which is a semi-online problem. Jobs arrive one by one over list. When a new job arrives at most K already scheduled jobs can be removed from the schedule, then all removed jobs and the new job must be assigned to the machines. The problem is a relaxation of the similar problem online scheduling with a buffer [4]. Assume machine M-1 has speed 1 and M-2 has speed s >= 1. With respect to the worst case ratio, we obtain that (i) for s >= root 3 or K >= 2, the model of online scheduling with bounded rearrangement is equivalent to the model of online scheduling with a bounded buffer; (ii) the model of online scheduling with bounded rearrangement is more powerful than the model of online scheduling with a bounded buffer for root 2 <= s < root 3 and K = 1; (iii) except for 1.3247 <= s < root 3 and K = 1 there is an optimal algorithm for the online scheduling with bounded rearrangement; (iv) fors > 1.618 the lower bound is improved. (C) 2010 Elsevier B.V. All rights reserved.