On-line load balancing of temporary tasks

被引:41
作者
Azar, Y
Kalyanasundaram, B
Plotkin, S
Pruhs, KR
Waarts, O
机构
[1] UNIV PITTSBURGH,DEPT COMP SCI,PITTSBURGH,PA 15260
[2] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305
[3] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720
基金
美国国家科学基金会; 以色列科学基金会;
关键词
D O I
10.1006/jagm.1995.0799
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
This paper considers the nonpreemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines, increasing the load on this machine for the duration of the task by an amount that depends on both the machine and the task. The goal is to minimize the maximum load. Azar, Broder, and Karlin studied the unknown duration case where the duration of a task is not known upon its arrival (On-line load balancing, in ''Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science, 1992,'' pp. 218-225). They focused on the special case in which for each task there is a subset of machines capable of executing it, and the increase in load due to assigning the task to one of these machines depends only on the task and not on the machine. For this case, they showed an O(n(2/3))competitive algorithm, and an Omega(root n) lower bound on the competitive ratio, where n is the number of the machines. This paper closes the gap by giving an O(root n)-competitive algorithm. In addition, trying to overcome the Omega(root n) lower bound for the case of unknown task duration, this paper initiates a study of the load balancing problem for tasks with known duration (i.e., the duration of a task becomes known upon its arrival). For this case we show an O(log nT)-competitive algorithm, where T is the ratio of the maximum possible duration of a task to the minimum possible duration of a task. The paper explores an alternative way to overcome the Omega(root n) bound; it considers the related machines case with unknown task duration. In the related machines case, a task can be executed by any machine and the increase in load depends on the speed of the machine and the weight of the task. For this case the paper gives a 20-competitive algorithm and shows a lower bound of 3 - o(1) on the competitive ratio. (C) 1997 Academic Press.
引用
收藏
页码:93 / 110
页数:18
相关论文
共 17 条
[1]  
ASPNES J, 1993, 25 ACM S THEOR COMP, P623
[2]  
AWERBUCH B, 1993, AN S FDN CO, P32
[3]  
AWERBUCH B, 1994, 5TH P ACM SIAM S DIS, P321
[4]  
Azar Y., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P218, DOI 10.1109/SFCS.1992.267770
[5]  
AZAR Y, 1992, 3RD P ANN ACM SIAM S, P203
[6]  
Bartal Yair, 1992, P 24 ANN ACM S THEOR
[7]   AN OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEM [J].
BORODIN, A ;
LINIAL, N ;
SAKS, ME .
JOURNAL OF THE ACM, 1992, 39 (04) :745-763
[8]  
Graham R. L., 1979, Discrete Optimisation, P287
[9]   BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].
GRAHAM, RL .
BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+
[10]  
KARGER D, 1993, UNPUB BETTER ALGORIT