Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines

作     者：Dósa, G He, Y 

作者机构：Univ Veszprem Dept Math H-8201 Veszprem Hungary Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Zhejiang Univ State Key Lab CAD & CG Hangzhou 310027 Peoples R China 

出 版 物：《COMPUTING》 (计算)

年 卷 期：2006年第76卷第1-2期

页      面：149-164页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：scheduling rejection on-line algorithms preemption competitive analysis 

摘      要：In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio 1/2 + root 1/4 + 1/s for any s = 1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s = 1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852 = s 1.6180 and has a smaller competitive ratio than that of original version for any 1 = s 1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.