An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

被引：0

作者：

Hans Kellerer

Vladimir Kotov

Michaël Gabay

机构：

[1] Universität Graz,Institut für Statistik und Operations Research

[2] Belarusian State University,Faculty of Applied Mathematics and Computer Science

[3] Grenoble-INP/UJF-Grenoble 1/CNRS,undefined

[4] G-SCOP UMR5272,undefined

来源：

Journal of Scheduling | 2015年 / 18卷

关键词：

Semi-online scheduling; Competitive analysis; Multiprocessor scheduling;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We consider a semi-online multiprocessor scheduling problem with a given a set of identical machines and a sequence of jobs, the sum of whose processing times is known in advance. The jobs are to be assigned online to one of the machines and the objective is to minimize the makespan. The best known algorithm for this problem achieves a competitive ratio 1.6 (Cheng et al. in Theor Comput Sci 337:134–146, 2005). The best known lower bound is approximately 1.585 (Albers and Hellwig in Theor Comput Sci 443:1–9, 2012) if the number of machines tends to infinity. We present an elementary algorithm with competitive ratio equal to this lower bound. Thus, the algorithm is best possible if the number of machines tends to infinity.

引用

页码：623 / 630

页数：7

共 26 条

[1]

Albers S(2012)Semi-online scheduling revisited Theoretical Computer Science 443 1-9

[2]

Hellwig M(2004)The on-line multiprocessor scheduling problem with known sum of the tasks Journal of Scheduling 7 421-428

[3]

Angelelli E(2001)On-line bin-stretching Theoretical Computer Science 268 17-41

[4]

Nagy AB(2005)Semi-on-line multiprocessor scheduling with given total processing time Theoretical Computer Science 337 134-146

[5]

Speranza MG(1989)On the performance of on-line algorithms for partition problems Acta Cybernetica 9 107-119

[6]

Tuza Z(2000)On-line scheduling revisited Journal of Scheduling 3 343-353

[7]

Azar Y(1966)Bounds for certain multiprocessor anomalies Bell System Technical Journal 45 1563-1581

[8]

Regev O(1969)Bounds on multiprocessing timing anomalies SIAM Journal of Applied Mathematics 17 263-269

[9]

Cheng TCE(1987)Using dual approximation algorithms for scheduling problems: theoretical and practical results Journal of the ACM 34 144-162

[10]

Kellerer H(2013)An efficient algorithm for bin stretching Operations Research Letters 41 343-346

← 1 2 3 →