Approximation algorithm for constrained coupled-tasks scheduling problem

Abstract : We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
Type de document :
Communication dans un congrès
CoDIT: Control, Decision and Information Technologies, Nov 2014, Metz, France. pp.110-112, 2014, 〈http://codit2014.event.univ-lorraine.fr〉. 〈10.1109/CoDIT.2014.6996877〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01101208
Contributeur : Rodolphe Giroudeau <>
Soumis le : jeudi 8 janvier 2015 - 10:17:37
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08

Identifiants

Citation

Gilles Simonin, Benoit Darties, Jean-Claude König, Rodolphe Giroudeau. Approximation algorithm for constrained coupled-tasks scheduling problem. CoDIT: Control, Decision and Information Technologies, Nov 2014, Metz, France. pp.110-112, 2014, 〈http://codit2014.event.univ-lorraine.fr〉. 〈10.1109/CoDIT.2014.6996877〉. 〈lirmm-01101208〉

Partager

Métriques

Consultations de la notice

174