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

Gilles Simonin 1 Rodolphe Giroudeau 1 Jean-Claude König 1 Benoit Darties 2, 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
Abstract : This paper presents a generalization of the coupled-task scheduling problem introduced by Shapiro, where considered tasks are subject to incompatibility constraint 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 border between P and 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 to our problem, determine new complexity results, and thus propose a new visualization including incompatibility constraint. In the end, we give a new polynomial-time approximation algorithm result which completes previous works.
Keywords : scheduling Complexity
Type de document :
Communication dans un congrès
ICAPS'11: 21st International Conference on Automated Planning and Scheduling, Jun 2011, Freiburg, Germany. pp.218-225, 2011
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00612821
Contributeur : Benoît Darties <>
Soumis le : lundi 1 août 2011 - 01:42:44
Dernière modification le : vendredi 9 juin 2017 - 10:42:32
Document(s) archivé(s) le : lundi 7 novembre 2011 - 12:22:35

Fichier

2695-11294-1-PB-1.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00612821, version 1

Collections

LE2I | MAORE | LIRMM | MIPS

Citation

Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König, Benoit Darties. Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph. ICAPS'11: 21st International Conference on Automated Planning and Scheduling, Jun 2011, Freiburg, Germany. pp.218-225, 2011. <hal-00612821>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

289

Téléchargements du document

182

Contact

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