Voir la notice de l'article provenant de la source Numdam
In this paper we consider the problem of scheduling precedence task graphs in parallel processing where there can be disturbances in computation and communication times. Such a phenomenon often occurs in practice, due to our inability to exactly predict the time because of system intrusion like cache miss and packet transmission time in mediums like ethernet etc. We propose a method based on the addition of some extra edges to protect the initial scheduling from performing badly due to such changes and provide an upper bound on the performance guarantee for the scheduling algorithms. Moreover, this construction guarantees a result at least as good as the result obtained for the initial static scheduling. We also show that this construction is a minimal set in context of partially on-line scheduling.
@article{RO_2003__37_3_145_0,
author = {Gupta, Apurv and Parmentier, Gilles and Trystram, Denis},
title = {Scheduling precedence task graphs with disturbances},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {145--156},
publisher = {EDP-Sciences},
volume = {37},
number = {3},
year = {2003},
doi = {10.1051/ro:2003018},
mrnumber = {2034536},
zbl = {1090.68530},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2003018/}
}
TY - JOUR AU - Gupta, Apurv AU - Parmentier, Gilles AU - Trystram, Denis TI - Scheduling precedence task graphs with disturbances JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2003 SP - 145 EP - 156 VL - 37 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2003018/ DO - 10.1051/ro:2003018 LA - en ID - RO_2003__37_3_145_0 ER -
%0 Journal Article %A Gupta, Apurv %A Parmentier, Gilles %A Trystram, Denis %T Scheduling precedence task graphs with disturbances %J RAIRO - Operations Research - Recherche Opérationnelle %D 2003 %P 145-156 %V 37 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2003018/ %R 10.1051/ro:2003018 %G en %F RO_2003__37_3_145_0
Gupta, Apurv; Parmentier, Gilles; Trystram, Denis. Scheduling precedence task graphs with disturbances. RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 3, pp. 145-156. doi: 10.1051/ro:2003018
Cité par Sources :