Geodesic
Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks
Discrete mathematics & theoretical computer science, Tome 3 (1998-1999) no. 4.

Voir la notice de l'article provenant de la source Episciences

In this paper, we consider the problem of scheduling independent parallel tasks in parallel systems with identical processors. The problem is NP-hard, since it includes the bin packing problem as a special case when all tasks have unit execution time. We propose and analyze a simple approximation algorithm called H_m, where m is a positive integer. Algorithm H_m has a moderate asymptotic worst-case performance ratio in the range [4/3 ... 31/18] for all m≥ 6; but the algorithm has a small asymptotic worst-case performance ratio in the range [1+1/(r+1)..1+1/r], when task sizes do not exceed 1/r of the total available processors, where r>1 is an integer. Furthermore, we show that if the task sizes are independent, identically distributed (i.i.d.) uniform random variables, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio of algorithm H_m is no larger than 1.2898680..., and for an exponential distribution of task sizes, it does not exceed 1.2898305.... As demonstrated by our analytical as well as numerical results, the average-case performance ratio improves significantly when tasks request for smaller numbers of processors. 
@article{DMTCS_1999_3_4_a2,
     author = {Li, Keqin},
     title = {Analysis of an {Approximation} {Algorithm} for {Scheduling} {Independent} {Parallel} {Tasks}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {3},
     number = {4},
     year = {1998-1999},
     doi = {10.46298/dmtcs.262},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.262/}
}
TY  - JOUR
AU  - Li, Keqin
TI  - Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks
JO  - Discrete mathematics & theoretical computer science
PY  - 1998-1999
VL  - 3
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.262/
DO  - 10.46298/dmtcs.262
LA  - en
ID  - DMTCS_1999_3_4_a2
ER  - 
%0 Journal Article
%A Li, Keqin
%T Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks
%J Discrete mathematics & theoretical computer science
%D 1998-1999
%V 3
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.262/
%R 10.46298/dmtcs.262
%G en
%F DMTCS_1999_3_4_a2
Li, Keqin. Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks. Discrete mathematics & theoretical computer science, Tome 3 (1998-1999) no. 4. doi : 10.46298/dmtcs.262. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.262/

Cité par Sources :