Résumé: Cette thèse développe une méthodologie pour résoudre les problèmes d'ordonnancement de programmes conditionnels où savoir si une tâche doit être exécutée n'est pas connue à l'avance mais dynamiquement. Le modèle utilisé est à base d'automates temporisés représentant l'espace d'états à explorer. Le problème est donc formulé comme le calcul d'une stratégie gagnante (pire cas optimale) dans un jeu contre l'environnement. Dans un premier temps nous étudions le problème d'ordonnancement sur graphes de tâches déterministe puis nous étendons l'étude au problème d'ordonnancement avec incertitude conditionnelle. Pour les deux problèmes nous étudions différentes classes d'ordonnancements et de stratégies pour réduire l'espace d'états, des décompositions en chaînes pour réduire sa taille, puis nous investiguons plusieurs classes d'algorithmes exactes pour en évaluer l'efficacité et à partir desquels nous dérivons de bonnes heuristiques. Des résultats expérimentaux sur plusieurs exemples de benchmarks sont présentés afin de montrer l'efficacité de chaque algorithme et la précision des heuristiques proposées, puis des bornes théoriques sont déduites pour prouver la garantie de performance pire cas de chaque heuristique.

Grenoble:
Langue: Français
Collation: 133 p. ill. ;30 cm.
Diplôme: Doctorat
Etablissement de soutenance: Grenoble, Université Joseph Fourier
Spécialité: Informatique
Index décimal 003 .Systèmes (analyse, conception, optimisation, théorie des systèmes ; commande, contrôle, étude, généralités ; modèles, simulations appliqués à des situations réelles ; ouvrages interdisciplinaires ; recherche opérationnelle, systémique)
Thème Informatique

Mots clés:
Graphes acyclique
Schur, Fonctions de
Automates temporisés
Ordonnancement (informatique)

Note: Bibliogr. pp.129-133