Geodesic
Some complexity and approximation results for coupled-tasks scheduling problem according to topology
Darties, Benoit1  ; Giroudeau, Rodolphe2  ; König, Jean-Claude2  ; Simonin, Gilles3 
1 LE2I, UMR CNRS 6306, University of Burgundy, 8 Rue Alain Savary, 21000 Dijon, France.
2 LIRMM, UMR CNRS 5506, Université de Montpellier, 161 rue Ada, 34392 Montpellier cedex 5, France.
3 Insight Centre for Data Analytics, University College Cork, Cork, Ireland.
RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 781-795

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

We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain, ...). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016034
Classification : 90B35, 68W25, 68Rxx, 68R10
Keywords: Coupled-task scheduling model, complexity, polynomial-time approximation algorithm

Darties, Benoit 1 ; Giroudeau, Rodolphe 2 ; König, Jean-Claude 2 ; Simonin, Gilles 3

1 LE2I, UMR CNRS 6306, University of Burgundy, 8 Rue Alain Savary, 21000 Dijon, France.
2 LIRMM, UMR CNRS 5506, Université de Montpellier, 161 rue Ada, 34392 Montpellier cedex 5, France.
3 Insight Centre for Data Analytics, University College Cork, Cork, Ireland. 
@article{RO_2016__50_4-5_781_0,
     author = {Darties, Benoit and Giroudeau, Rodolphe and K\"onig, Jean-Claude and Simonin, Gilles},
     title = {Some complexity and approximation results for coupled-tasks scheduling problem according to topology},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {781--795},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4-5},
     year = {2016},
     doi = {10.1051/ro/2016034},
     zbl = {1353.90058},
     mrnumber = {3570530},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016034/}
}
TY  - JOUR
AU  - Darties, Benoit
AU  - Giroudeau, Rodolphe
AU  - König, Jean-Claude
AU  - Simonin, Gilles
TI  - Some complexity and approximation results for coupled-tasks scheduling problem according to topology
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 781
EP  - 795
VL  - 50
IS  - 4-5
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016034/
DO  - 10.1051/ro/2016034
LA  - en
ID  - RO_2016__50_4-5_781_0
ER  - 
%0 Journal Article
%A Darties, Benoit
%A Giroudeau, Rodolphe
%A König, Jean-Claude
%A Simonin, Gilles
%T Some complexity and approximation results for coupled-tasks scheduling problem according to topology
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 781-795
%V 50
%N 4-5
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016034/
%R 10.1051/ro/2016034
%G en
%F RO_2016__50_4-5_781_0
Darties, Benoit; Giroudeau, Rodolphe; König, Jean-Claude; Simonin, Gilles. Some complexity and approximation results for coupled-tasks scheduling problem according to topology. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 781-795. doi: 10.1051/ro/2016034

Cité par Sources :