Complexity and approximation for scheduling problem for a torpedo

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 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.
Type de document :
Communication dans un congrès
CIE'39: 39th International Conference on Computers & Industrial Engineering, Jul 2009, Troyes, France. 62 (2), pp.352-356, 2009, 〈http://www.utt.fr/cie39/〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00355052
Contributeur : Gilles Simonin <>
Soumis le : mercredi 21 janvier 2009 - 17:43:38
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:08:38

Fichier

cie39_rapport.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00355052, version 1

Collections

Citation

Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König. Complexity and approximation for scheduling problem for a torpedo. CIE'39: 39th International Conference on Computers & Industrial Engineering, Jul 2009, Troyes, France. 62 (2), pp.352-356, 2009, 〈http://www.utt.fr/cie39/〉. 〈lirmm-00355052〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

111