Voir la notice de l'article provenant de la source Numdam
In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay be tween two tasks and depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless 𝒫 = 𝒩𝒫) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.
@article{RO_2012__46_1_1_0,
author = {Boudet, Vincent and Cohen, Johanne and Giroudeau, Rodolphe and K\"onig, Jean-Claude},
title = {Scheduling in the presence of processor networks : complexity and approximation},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1--22},
publisher = {EDP-Sciences},
volume = {46},
number = {1},
year = {2012},
doi = {10.1051/ro/2012005},
mrnumber = {2934890},
zbl = {1242.90075},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2012005/}
}
TY - JOUR AU - Boudet, Vincent AU - Cohen, Johanne AU - Giroudeau, Rodolphe AU - König, Jean-Claude TI - Scheduling in the presence of processor networks : complexity and approximation JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2012 SP - 1 EP - 22 VL - 46 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2012005/ DO - 10.1051/ro/2012005 LA - en ID - RO_2012__46_1_1_0 ER -
%0 Journal Article %A Boudet, Vincent %A Cohen, Johanne %A Giroudeau, Rodolphe %A König, Jean-Claude %T Scheduling in the presence of processor networks : complexity and approximation %J RAIRO - Operations Research - Recherche Opérationnelle %D 2012 %P 1-22 %V 46 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2012005/ %R 10.1051/ro/2012005 %G en %F RO_2012__46_1_1_0
Boudet, Vincent; Cohen, Johanne; Giroudeau, Rodolphe; König, Jean-Claude. Scheduling in the presence of processor networks : complexity and approximation. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 1-22. doi: 10.1051/ro/2012005
Cité par Sources :