Geodesic
Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 1, pp. 73-87

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

We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into K classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung-Palem-Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone communication delays. It is also proved that the problem is NP-complete for two dedicated processors if communication delays are non monotone. Lastly, we show that list scheduling algorithm cannot provide a solution for identical processors.

DOI : 10.1051/ro/2013028
Classification : 90B35
Keywords: approximation and complexity, combinatorial optimization, scheduling 
@article{RO_2013__47_1_73_0,
     author = {Munier-Kordon, Alix and Kacem, Fadi and Dupont de Dinechin, Beno{\^\i}t and Finta, Lucian},
     title = {Scheduling an interval ordered precedence graph with communication delays and a limited number of processors},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {73--87},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {1},
     year = {2013},
     doi = {10.1051/ro/2013028},
     mrnumber = {3143743},
     zbl = {1282.90072},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2013028/}
}
TY  - JOUR
AU  - Munier-Kordon, Alix
AU  - Kacem, Fadi
AU  - Dupont de Dinechin, Benoît
AU  - Finta, Lucian
TI  - Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2013
SP  - 73
EP  - 87
VL  - 47
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2013028/
DO  - 10.1051/ro/2013028
LA  - en
ID  - RO_2013__47_1_73_0
ER  - 
%0 Journal Article
%A Munier-Kordon, Alix
%A Kacem, Fadi
%A Dupont de Dinechin, Benoît
%A Finta, Lucian
%T Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2013
%P 73-87
%V 47
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2013028/
%R 10.1051/ro/2013028
%G en
%F RO_2013__47_1_73_0
Munier-Kordon, Alix; Kacem, Fadi; Dupont de Dinechin, Benoît; Finta, Lucian. Scheduling an interval ordered precedence graph with communication delays and a limited number of processors. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 1, pp. 73-87. doi: 10.1051/ro/2013028

Cité par Sources :