Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph

Rodolphe Giroudeau 1 Benoit Darties 2, 1 Jean-Claude König 1 Gilles Simonin 3, 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 Le2i - Laboratoire Electronique, Informatique et Image
3 LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro \cite{Shapiro}, where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between $\mathcal{P}$ and $\mathcal{NP}$-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of the complexity of scheduling problems with coupled-task given by Orman and Potts \cite{op1997} to our model, determine new complexity results, and thus propose a new visualization including incompatibility constraints. In the end, we give a new polynomial-time approximation algorithm result which completes previous works.
Keywords : coupled-tasks scheduling approximation algorithm complexity
Type de document :
Article dans une revue
Algorithmic Operations Research, Preeminent Academic Facets, 2012, 7 (1), pp.1-12
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00715828
Contributeur : Rodolphe Giroudeau <>
Soumis le : lundi 9 juillet 2012 - 12:45:44
Dernière modification le : mercredi 28 février 2018 - 10:22:50

Identifiants

  • HAL Id : lirmm-00715828, version 1

Collections

UNIV-TLSE3 | LE2I | MAORE | LIRMM | INSA-TOULOUSE | MIPS | UNIV-MONTPELLIER

Citation

Rodolphe Giroudeau, Benoit Darties, Jean-Claude König, Gilles Simonin. Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph. Algorithmic Operations Research, Preeminent Academic Facets, 2012, 7 (1), pp.1-12. 〈lirmm-00715828〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

212

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD