Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins tridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode

Le modèle d'acteurs est un modèle de calcul concurrent qui semble bien adapté au modèle d'exécution des architectures massivement parallèles. Nous étudions son adéquation à une machine massivement parallèle à grain fin étudiée dans notre groupe ; nous dégageons les mécanismes de base à intégrer au niveau de l'unité de routage de cette machine. Pour des modèles de programmation dynamiques de ce type, il est nécessaire d'établir une stratégie d'allocation dynamique de processus. Nous proposons et évaluons une idée originale pour l'allocation dynamique de processus dans une architecture massivement parallèle. Dans le cas d'une machine à grain fin comme la nôtre, il est primordial qu'une telle fonction n'induise qu'un minimum de charge supplémentaire en termes de communications. Nous présentons une fonction intégrée de recherche de processeurs libres pour l'exécution des processus dynamiques. L'évaluation des principaux choix architecturaux a pu être menée grâce à un simulateur développé dans le cadre de ce travail. Les résultats obtenus, qui démontrent l'intérêt de l'approche, sont présentés dans cette thèse.

Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins quadridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode développée.