Complexity and approximation for scheduling problem for a torpedo - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2009

Complexity and approximation for scheduling problem for a torpedo

Gilles Simonin
Rodolphe Giroudeau
Jean-Claude König

Résumé

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.
Fichier principal
Vignette du fichier
cie39_rapport.pdf (95.38 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00355052 , version 1 (21-01-2009)

Identifiants

  • HAL Id : lirmm-00355052 , version 1

Citer

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. pp.352-356. ⟨lirmm-00355052⟩
192 Consultations
323 Téléchargements

Partager

More