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 : vendredi 9 juin 2017 - 10:42:52

Identifiants

Collections

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

161