 |
 |
|
|
| HAL : lirmm-00355052, version 1 |
| Fiche détaillée |  Récupérer au format |
|
|
| CIE'39 : The 39th International Conference on Computers & Industrial Engineering, Troyes - France : (2009) |
|
|
|
|
| Complexity and approximation for scheduling problem for a torpedo |
|
|
| Gilles Simonin 1Rodolphe Giroudeau 1 |
|
|
| (21/01/2009) |
|
|
|
| This paper considers a special case of the coupled-tasks scheduling problem on one processor. The general problems were analyzed in depth by Orman and Potts. In this paper, we consider that all processing times are equal to 1, the gap has exact length L, we have precedence constraints, compatibility constraints are introduced and the criterion is to minimize the scheduling length. We use this problem to study the problem of data acquisition and data treatment of a torpedo under the water. We show that this problem is NP-complete and we propose an rho-approximation algorithm where rho<=(L+6)/6. |
|
|
|
|
|
|
|
|
|
|
|
| 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 |
|
|
| scheduling – coupled-tasks – compatibility constraints – complexity – approximation |
|
|
|
| Liste des fichiers attachés à ce document : | |||||
|
|||||
|
|
|
| lirmm-00355052, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00355052 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00355052 | |
| Contributeur : Gilles Simonin | |
| Soumis le : Mercredi 21 Janvier 2009, 17:43:38 | |
| Dernière modification le : Vendredi 11 Septembre 2009, 15:17:22 | |
