Extended Matching Problem for a Coupled-Tasks Scheduling Problem

Gilles Simonin 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
Abstract : This paper introduces a scheduling problem with coupled-tasks in presence of a compatibility graph on a single processor. We investigate a specific configuration, in which the coupled-tasks possess an idle time equal to 2. The complexity of these problems will be studied according to the presence or absence of triangles in the compatibility graph. As an extended matching, we propose a polynomial-time algorithm which consists in minimizing the number of non-covered vertices, by covering vertices with edges or paths of length two in the compatibility graph. This type of covering will be denoted by 2-cover technique. According on the compatibility graph type, the 2-cover technique provides a polynomial-time rho-approximation algorithm with rho=13/12 (resp. rho=10/9) in absence (resp. presence) of triangles.
Type de document :
Communication dans un congrès
TMFCS'09: International Conference on Theoretical and Mathematical Foundations of Computer Science, Jul 2009, Orlando, Florida, United States. pp.082-089, 2009
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00375000
Contributeur : Gilles Simonin <>
Soumis le : vendredi 10 avril 2009 - 17:35:34
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : jeudi 10 juin 2010 - 20:20:54

Fichier

2-recouvrementRR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00375000, version 1

Collections

Citation

Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König. Extended Matching Problem for a Coupled-Tasks Scheduling Problem. TMFCS'09: International Conference on Theoretical and Mathematical Foundations of Computer Science, Jul 2009, Orlando, Florida, United States. pp.082-089, 2009. 〈lirmm-00375000〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

65