Les réseaux ad hoc véhiculaires (VANETs) sont constitués par un ensemble de véhicules qui échangent des données de sécurité et de confort même s’ils ne sont pas toujours directement à portée radio.Les problèmes liés aux réseaux VANETs ne sont pas encore tous résolus. Dans ce contexte, et dans le but de maximiser la stabilité dans ce type de réseaux, nous proposons différentes contributions pour assurer le routage en combinant les métaheuristiques et la technique de clustérisation.Tout d’abord, nous présentons un modèle de routage utilisant l’algorithme de clustérisation le plus efficace k-medoids. Ensuite, nous proposons plusieurs améliorations en utilisant les métaheuristiques, plus précisément les algorithmes génétiques, la recherche tabou et la recherche par dispersion. Enfin, nous proposons une application réelle de communication entre trois robots mobiles dans les zones non couvertes par le réseau VANET.A l’aide de diverses métriques, des simulations extensives montrent que nos contributions donnent de bons résultats par rapport à d’autres modèles conçus dans le même but. / Vehicular ad hoc networks (VANETs) consist of a set of vehicles trying to exchange security and comfort data even if they are not directly within radio range of each other. The problems related to VANET networks are not yet solved. In this context, and in order to maximize the stability in the VANETs networks, we propose different contributions combining the metaheuristics and the clustering technique. First, we propose a routing model using the most efficient clustering algorithm K-medoids. Then, we propose several improvements using metaheuristics, more precisely the AGs, the RT and the Scatter Search. Finally, we propose a real application that uses the Arduino Uno platform to allow communication between three mobile robots in an areas not covered by the VANET network.Using various metrics, extensive simulations prove that our contributions show good results compared to other models designed for the same purpose.

La modélisation et la représentation des architectures logicielles sont devenues une des phases principales du processus de développement des systèmes complexes. En effet, la représentation de l'architecture fournit de nombreux avantages pendant tout le cycle de vie du logiciel. Cependant, pour beaucoup de systèmes existants, aucune représentation fiable de leurs architectures n'est disponible. Afin de pallier cette absence, source de nombreuses difficultés principalement lors des phases de maintenance et d'évolution, nous proposons dans cette thèse une approche, appelée ROMANTIC, visant à extraire une architecture à base de composants à partir d'un système orienté objet existant. L'idée première de cette approche est de proposer un processus quasi-automatique d'identification d'architectures en formulant le problème comme un problème d'optimisation et en le résolvant au moyen de méta-heuristiques. Ces dernières explorent l'espace composé des architectures pouvant être abstraites du système en utilisant la sémantique et la qualité architecturale pour sélectionner les meilleures solutions. Le processus s'appuie également sur l'architecture intentionnelle du système, à travers l'utilisation de la documentation et des recommandations de l'architecte.

Nous étudions des stratégies d'ordonnancement et d'équilibrage de charge pour des plates-formes hétérogènes distribuées. Notre problème est d'ordonnancer un ensemble de tâches indépendantes afin d'en réduire le temps total d'exécution. Ces tâches utilisent des données d'entrée qui peuvent être partagées : chaque tâche peut utiliser plusieurs données, et chaque donnée peut être utilisée par plusieurs tâches. Les tâches ont des durées d'exécution différentes, et les données ont des tailles différentes. Toute la difficulté est de réussir à placer sur un même processeur des tâches partageant des données, tout en conservant un bon équilibrage de la charge des différents processeurs. Notre étude comporte trois parties généralisant progressivement le problème. Nous nous limitons dans un premier temps au cas simple où il n'y a pas de partage de données, où les tailles des tâches et des données sont homogènes, et où la plate-forme est de type maître-esclave. Le partage des données est introduit dans la deuxième partie, ainsi que l'hétérogénéité pour les tailles des tâches et des données. Dans la dernière partie nous généralisons le modèle de plate-forme à un ensemble décentralisé de serveurs reliés entre eux par un réseau d'interconnexion quelconque. La complexité théorique du problème est étudiée. Pour les cas simples, des algorithmes calculant une solution optimale sont proposés, puis validés par des résultats expérimentaux avec une application scientifique réelle. Pour les cas plus complexes, nous proposons de nouvelles heuristiques pour résoudre le problème d'ordonnancement. Ces nouvelles heuristiques, ainsi que des heuristiques classiques comme min-min et sufferage, sont comparées entre elles à l'aide de nombreuses simulations. Nous montrons ainsi que nos nouvelles heuristiques réussissent à obtenir des performances aussi bonnes que les heuristiques classiques, tout en ayant une complexité algorithmique d'un ordre de grandeur plus faible.

Les travaux de cette thèse concernent la conception et l'optimisation de lignes de transfert reconfigurables. L'objectif principal est de concevoir une ligne d'usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d'optimisation correspondant est un problème d'équilibrage de lignes d'usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d'installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d'inclusion et d'exclusion, nous avons dû considérer des contraintes d'accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d'usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l'utilisation d'une tête d'usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d'outils qui dépendent de la séquence d'opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l'aide d'un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu'une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d'équilibrage plus difficile que dans le cas des lignes dédiées, et l'approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d'optimisation combinatoire.

Les travaux présentés dans cette thèse portent sur la conception de systèmes de fabrication en contexte incertain. La conception d'un tel système peut être vue comme un problème d'optimisation qui consiste à trouver une configuration qui permet d'optimiser certains objectifs tout en respectant des contraintes technologiques et économiques connues. Les systèmes de fabrication étudiés dans ce mémoire sont des lignes d'assemblage et d'usinage. La première est une ligne qui se présente comme une chaîne de postes de travail où, dans chaque poste, les opérations d'assemblage s'exécutent de manière séquentielle. La deuxième, quant à elle, est une ligne particulière qui se compose de machines de transfert comportant plusieurs boîtiers multibroches où les opérations s'exécutent simultanément. Dans un premier temps, nous décrivons de différentes approches permettant de modéliser l'incertitude des données en optimisation. Une attention particulière est portée sur les deux approches suivantes : l'approche robuste et l'analyse de sensibilité. Puis, nous présentons trois applications : la conception d'une ligne d'assemblage et d'une ligne d'usinage soumises aux variations de temps opératoires et la conception d'une ligne d'assemblage avec les temps opératoires connus sous la forme d'intervalles des valeurs possibles. Pour chaque application, nous identifions les performances attendues ainsi que la complexité de la prise en compte de l'incertitude. Ensuite, nous proposons de nouveaux critères d'optimisation en adéquation avec la problématique introduite. Enfin des méthodes de résolution sont développées pour appréhender les différents problèmes mis en évidence par ces critères.

Les travaux de recherche effectués dans le cadre de cette thèse concernent essentiellement la conception en avant-projet de systèmes d'usinage dédiés à la production en grande série. Lors de cette phase de conception, l'objectif principal est de trouver, pour une pièce donnée, une configuration du système d'usinage qui satisfaisait, à coût minimal, les contraintes technologiques, techniques et économiques existantes. Plusieurs problèmes combinatoires posés par cet objectif sont étudiés dans la thèse. Plus concrètement, nous nous sommes intéressés aux problèmes d'optimisation de la configuration des trois types de systèmes d'usinage suivants : machines de transfert, machines à table mobile et machines à table circulaire pivotante. Pour chacun de ces systèmes, nous avons proposé, dans un premier temps, différents modèles mathématiques. Dans un deuxième temps, nous avons développé de nombreux outils d'optimisation dédiés à leur résolution, tels que des algorithmes de calcul des bornes inférieures, des procédures de pré-traitement, des algorithmes de résolution exacte et approchée, et des approches mixtes utilisant plusieurs de ces algorithmes. Ces travaux ont permis de concevoir un prototype de logiciel destiné à supporter les différentes étapes de conception en avant projet d'un système d'usinage. Ce logiciel a été testé avec succès sur plusieurs cas industriels.

De nos jours, le transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de collecte et de distribution avec fenêtres de temps à un seul véhicule est un des problèmes les plus rencontrés. Ayant un ensemble de demandes à satisfaire, le véhicule doit transporter des biens de fournisseurs à leurs clients respectifs en respectant les fenêtres de temps et sa capacité. Dans ce travail, nous présentons un état de l'art du 1-PDPTW et nous proposons plusieurs approches évolutionnistes pour traiter ses deux cas : statique et dynamique. Nos approches utilisent principalement des algorithmes évolutionnistes basés sur l'utilisation d'opérateurs génétiques spéciaux conçus dans le but d'améliorer la qualité des solutions et de diminuer le temps de calcul. Elles sont aussi basées sur la Pareto optimalité pour fournir un ensemble de solutions viables. Quelques unes de nos approches utilisent des bornes inférieures de distance et de retard dans le but d'évaluer les résultats obtenus. Une recherche Tabou, constituant un étage d'hybridation, peut être appliquée pour l'amélioration des solutions obtenues par les algorithmes évolutionnistes. Enfin nous présentons quelques simulations et résultats élaborés à partir de benchmarks spécialement conçus pour le 1-PDPTW ainsi que d'autres provenant de la littérature.

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.

Le but de cette thèse est l'exploration du domaine de l'optimisation de la topologie radiale d'un réseau de distribution en temps réel pour différents régimes d'exploitation. Nous avons ainsi développé différents outils de calcul performants, en particulier une approche unifiée qui se prête d'une part pour l'optimisation pour le régime normal d'exploitation, d'autre part pour établir un plan de reprise de service pour les zones îlotées suite à la défaillance d'un élément du réseau. Afin de satisfaire la contrainte temps réel, nous nous sommes basés sur des méthodes heuristiques permettant de s'approcher au plus de l'optimum global en un temps de calcul très court. La vérification de la qualité des solutions obtenues par des méthodes heuristiques est effectuée à l'aide d'autres méthodes d'optimisation plus dédiées à la recherche de l'optimum global. En validant la méthodologie proposée sur des réseaux de distribution réels à grande taille, nous avons montré l'efficacité de notre approche tant au niveau de la qualité des résultats qu'au niveau du temps de calcul.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal