 |
 |
|
|
| HAL : lirmm-00355050, version 1 |
| Fiche détaillée |  Récupérer au format |
|
|
| MISTA'04 : 4th Multidisciplinary International Scheduling Conference : Theory and Applications, (2009) |
|
|
|
|
| Isomorphic Coupled-Task Scheduling Problem with Compatibility Constraints on a Single Processor |
|
|
| Gilles Simonin 1Benoit Darties 1, 2 |
|
|
| (21/01/2009) |
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
| 1 : | Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) |
|
|
|
CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc |
|
|
| 2 : | Laboratoire d'Informatique de Grenoble (LIG) |
|
|
|
CNRS : UMR5217 – INRIA – Université Pierre Mendès-France - Grenoble II – Université Joseph Fourier - Grenoble I – Institut Polytechnique de Grenoble - Grenoble Institute of Technology |
|
|
|
|
|
|
|
|
|
| [INFO/APR : Algorithmique et Performances des Réseaux] |
|
|
|
|
| Domaine | : | Informatique/Recherche opérationnelle |
|
|
| Liste des fichiers attachés à ce document : | |||||
|
|||||
|
|
|
| lirmm-00355050, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00355050 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00355050 | |
| Contributeur : Gilles Simonin | |
| Soumis le : Mercredi 21 Janvier 2009, 17:36:14 | |
| Dernière modification le : Vendredi 11 Septembre 2009, 15:25:32 | |
