Optimal preemptive semi-online scheduling on two uniform processors

被引：8
|
作者：
Du, DL [1 ]
机构：
[1] Univ New Brunswick, Fac Adm, Fredericton, NB E3B 5V4, Canada
来源：
INFORMATION PROCESSING LETTERS | 2004年 / 92卷 / 05期
基金：
加拿大自然科学与工程研究理事会;
关键词：
on-line algorithms; uniform processor; scheduling; preemption;
D O I：
10.1016/j.ipl.2004.09.003
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r greater than or equal to 1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s greater than or equal to 1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：219 / 223
页数：5
相关论文
共 50 条
12345