Isomorphic Coupled-Task Scheduling Problem with Compatibility Constraints on a Single Processor

Gilles Simonin 1 Benoit Darties 2, 1 Rodolphe Giroudeau 1 Jean-Claude König 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 LIG - Laboratoire d'Informatique de Grenoble
Abstract : The problem presented in this paper is a generalization of the usual coupled-tasks scheduling problem in presence of compatibility constraints. The reason behind this study is the data acquisition problem for a submarine torpedo. We investigate a particular configuration for coupled-tasks (any task is divided into two sub-tasks separated by an idle time), in which the idle time of a coupled-task is equal to the sum of its two sub-tasks. We prove NP-completeness of the minimization of the schedule length, and we show that finding a solution to our problem amounts to solving a graph problem, which in itself is close to the minimum-disjoint path cover (min-DCP) problem. We design a (3a+2b)/(2a+2b)- approximation, where a and b (the processing time of the two sub-tasks) are two input data such as a>b>0, and that leads to a ratio between 3/2 and 5/4. Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to (1+\sqrt{3})/2.
Type de document :
Communication dans un congrès
MISTA'2009: 4th Multidisciplinary International Scheduling Conference: Theory and Applications, Aug 2009, Dublin, Ireland. pp.378-388, 2009, 〈http://www.mistaconference.org/2009/〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00355050
Contributeur : Gilles Simonin <>
Soumis le : mercredi 21 janvier 2009 - 17:36:14
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mardi 8 juin 2010 - 18:23:00

Fichier

rapport-SDGK.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00355050, version 1

Collections

LIG | UGA | APR | APR-LIRMM | LIRMM | MIPS | LIG_SRCPR | UNIV-MONTPELLIER

Citation

Gilles Simonin, Benoit Darties, Rodolphe Giroudeau, Jean-Claude König. Isomorphic Coupled-Task Scheduling Problem with Compatibility Constraints on a Single Processor. MISTA'2009: 4th Multidisciplinary International Scheduling Conference: Theory and Applications, Aug 2009, Dublin, Ireland. pp.378-388, 2009, 〈http://www.mistaconference.org/2009/〉. 〈lirmm-00355050〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

714

Téléchargements de fichiers

225

Contact

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