 |
 |
|
|
| HAL : lirmm-00355048, version 2 |
| Fiche détaillée |  Récupérer au format |
|
|
| N° RR-09003 (2009) |
|
|
| Versions disponibles : | v1 (27-01-2009) | v2 (15-04-2009) |
|
|
|
|
| 2-Cover Definition for a Coupled-Tasks Scheduling Problem |
|
|
| Gilles Simonin 1Rodolphe Giroudeau 1 |
|
|
| (21/01/2009) |
|
|
|
| This paper presents a scheduling problem with coupled-tasks in presence of a compatibility graph on a mono 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 2-cover technique. According on the compatibility graph type, the 2-cover technique provides an 13/12-approximation or 10/9-approximation algorithm. |
|
|
|
|
|
|
|
|
|
|
|
| 1 : | Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) |
|
|
|
CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc |
|
|
|
|
|
|
|
|
|
| [INFO/APR : Algorithmique et Performances des Réseaux] |
|
|
|
|
| Domaine | : | Informatique/Recherche opérationnelle |
|
|
| 2-cover – scheduling – coupled-tasks – compatibility constraints – approximation |
|
|
|
| Liste des fichiers attachés à ce document : | |||||
|
|||||
|
|
|
| lirmm-00355048, version 2 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00355048 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00355048 | |
| Contributeur : Gilles Simonin | |
| Soumis le : Vendredi 10 Avril 2009, 18:08:24 | |
| Dernière modification le : Mercredi 15 Avril 2009, 11:34:25 | |
