Thèse Sciences économiques, Groningue, 1969.

Reproduction de : Thèse de doctorat : Systèmes industriels. Automatique : Toulouse, INPT : 2004. / Titre provenant de l'écran-titre. Bibliogr. 97 réf.

Thèse de doctorat : Génie électrique : INPL : 2006. / Titre provenant de l'écran-titre. Bibliogr.

Résumé de thèse--Bucarest. / In SpringerLink. Titre de l'écran-titre (visionné le 12 mars 2010). Bibliogr. : p. 39-50. Publié aussi en version papier.

Thèse--University of Zurich, 2007. / In SpringerLink. Titre de l'écran-titre (visionné le 24 septembre 2009). Bibliogr. Publié aussi en version papier.

Thèse de doctorat : Informatique : Tours : 2008. / Titre provenant de l'écran-titre.

Thèse de doctorat : Mathématiques appliquées : Bordeaux 1 : 2008. / Titre provenant de l'écran-titre.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3514. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. [149]-160.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.

Les travaux présentés dans cette thèse portent sur l'étude de la complexité et de l'approximation des problèmes d'ordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation d'un problème de robotique portant sur une torpille sous-marine d'exploration. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches. La première partie de nos travaux s'intéresse à la modélisation du problème, aux différentes tâches utilisées et aux contraintes qui leur sont appliquées. Nous mettons en avant l'impact de la contrainte de compatibilité, nous forçant à utiliser la théorie des graphes pour analyser nos problèmes. Enfin, nous finissons cette partie avec un état de l'art sur les différents résultats portant sur l'ordonnancement de tâches-couplées sur mono-processeur, et sur des problèmes de recouvrement de sommets dans des graphes. Dans une seconde partie, nous donnons la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Nous donnons des preuves de complexité pour certains problèmes se trouvant à la limite entre la polynomialité et la NP-complétude selon les valeurs des paramètres. Pour chaque problème NP-complet, nous proposons des algorithmes d'approximation en temps polynomial et analysons les bornes obtenues selon les paramètres ou les topologies du graphe de compatibilité. L'ensemble des résultats est décomposé en trois chapitres prenant chacun en compte l'introduction d'une contrainte (d'incompatibilité et/ou de précédence). Tout au long de cette partie nous cherchons à montrer l'impact de l'introduction de la contrainte d'incompatibilité sur la complexité des problèmes d'ordonnancement avec tâches-couplées, à travers les preuves de NP-complétude et les techniques employées pour résoudre ou approximer un problème.