Dans ce travail on s'intéresse à la conception et au développement d'un système d'aide à la confection d'horaires. Le banc d'essai"Benchmark" utilisé est le problème d'horaires de cours dans une université basé sur l'inscription des étudiants aux cours"Post Enrolment based Course Timetabling", proposé en deuxième volet lors de la compétition internationale d'horaires en 2007"International Timetabling Competition". Le système d'aide à la confection d'horaires applique une approche heuristique basée sur la recherche locale stochastique. L'originalité du système consiste à implémenter les algorithmes de recuit simulé, recherche tabou et génétique, qui s'exécutent sur les mêmes énoncés des problèmes proposés par l'ITC et qui se partagent les mêmes structures de données et la majorité des modules de recherche locale. Ensuite une étude qualitative et quantitative de performance à produire des horaires de qualité comparable à ceux réalisés lors de la compétition est effectuée pour chaque algorithme implémenté.

La recherche en optimisation est un secteur crucial pour les constructeurs aéronautiques. La performance des appareils est un élément déterminant dans la compétition commerciale qui oppose les principaux manufacturiers du marché. L'incorporation de plus en plus massive des matériaux composites dans les avions de ligne dans les années 2000 illustre le désir des constructeurs de réduire la masse de leurs appareils pour en diminuer la consommation de kérosène. Parallèlement, la sécurité est devenue au fil des années une préoccupation majeure pour l'ensemble des acteurs. Cependant, l'emploi massif de matériaux composites, dont les propriétés physiques sont très intéressantes pour les constructeurs mais qui sont conçus avec une marge de tolérance pour des raisons de coût, induit des variations indésirables dans la structure, des incertitudes. Outre ces matériaux, d'autres éléments non prévisibles sont susceptibles de perturber la structure de l'appareil. Le modèle d'un avion en avant-projet est toujours amené à évoluer pour répondre aux évolutions des exigences du constructeur, mais des études de faisabilité doivent être menées avant que la structure ne soit totalement définie, afin de s'assurer de la viabilité du modèle. Des éléments non pris en compte dans la structure, comme les câbles, peuvent également avoir une influence non négligeable sur le comportement global de l'appareil. Ces incertitudes ont un impact non négligeable sur la stabilité de la structure en vol. Des études ont commencé à incorporer cet aspect incertain dans les processus d'optimisation, mais généralement en adaptant les algorithmes existants et sans exploiter la nature incertaine des problèmes. Afin de tenir compte de l'aspect incertain, on se propose de représenter ces incertitudes par des variables aléatoires et d'exploiter des outils théoriques développés dans d'autres domaines, notamment les outils des mathématiques financières. / Research in optimization is a fundamental field for aircraft manufacturers. The performance of airplanes is a crucial element in the commercial competition that pit main aircraft manufacturers against each other. Since 2000, composite materials have been more and more used in aircraft design. This shows the manufacturers' desire to reduce the airplane weight to diminish kerosene consumption. At the same time, safety has become a major concern for all the parties involved. But the use of composite materials, which are designed with a margin of tolerance on the physical properties to cut cost, causes unwanted variations in the structure. Other factors in the airplane design could also disrupt the overall structure of the final product. An airplane model is intended to be modified according to the manufacturer's wishes and their evolution, but feasibility studies must be carried out before the structural design is complete, in order to make sure that the model is viable. Elements which are not modeled in the structure, e.g. cables, can affect the overall behavior of the airplane. These uncertainties have a non-negligible influence on the stability of the structure during flights. Some studies have started to take into account these uncertainties in the optimization process, but they usually consist in adapting existing deterministic algorithms, without regard for the inherent uncertainty of the problem. In order to take uncertainty into account, we propose to represent these uncertainties by random variables and to use theoretical tools that are used in other domains, such as financial mathematics.

Le Problème de Transport à la Demande (PTD), consiste à prendre en charge le transport des personnes d'un lieu de départ vers un lieu d'arrivée. Il est caractérisé par un ensemble de demandes de transport et d'un nombre de véhicules disponible. L'ultime objectif dans ce travail de thèse est d'offrir une alternative optimisée au déplacement individuel et collectif. Le PTD est classé parmi les problèmes NP-difficile, la majorité des travaux de recherche ont été concentrés sur l'utilisation des méthodes approchées pour le résoudre.Ce problème est également multicritère, la solution proposée dans ce travail permet à la fois une réduction du temps de voyage et également de la distance parcourue. Dans cette thèse, nous proposons notre contribution à l'étude et à la résolution du problème de transport à la demande multicritère et dynamique en appliquant l'algorithme de recuit simulé multi-objectif. Une grande partie de notre travail concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un PTD. Ces approches utilisent une méthode multicritère qui s'appuie sur l'algorithme de recuit simulé. La modélisation du PTD est représentée par une architecture multi-acteurs. Cette architecture met en évidence l'aspect distribué du système ainsi que les interactions et les relations qui peuvent avoir lieu entre les différents acteurs. Nous présentons dans ce travail un Système Multi-Agents pour la planification des itinéraires des véhicules affectés au transport des voyageurs. Les agents de ce système utilisent le module d'optimisation développé dans la première partie

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous proposons une méthode d'inversion non linéaire des amplitudes des ondes directes P, SV et SH basée sur l'algorithme du recuit simulé, afin de déterminer à partir d'un nombre limité de stations, le mécanisme au foyer de séismes induits en contexte de réservoir. Cette méthode permet de déterminer aussi bien les paramètres du plan de faille (azimut, pendage et angle de glissement) décrivant une source double-couple, que les six composantes du tenseur des moments décrivant une source plus générale. <br />L'inversion double-couple et l'inversion du tenseur des moments sont testées sur quatre séismes induits dans le réservoir géothermique de Soultz-sous-Forêts. Les mécanismes obtenus sont en accord avec ceux déterminés par Charléty et al. 2007.<br />La méthode d'inversion est appliquée à la sismicité de la saline de Vauvert enregistrée par un réseau permanent de deux stations 3-composante. Dans un premier temps, la méthode est testée sur 15 séismes enregistrés durant le déploiement temporaire d'une antenne de quatre capteurs 3-composante. La comparaison entre l'inversion utilisant les deux stations permanentes et l'antenne temporaires et l'inversion utilisant seulement les deux stations permanentes montre des mécanismes au foyer double-couple identiques pour les séismes localisés entre les deux stations permanentes. Dans un deuxième temps, la méthode est appliquée à un essaim de sismicité. Les mécanismes au foyer obtenus pour 532 évènements, indiquent pour la majorité une rupture le long de fractures sub-verticales NE-SW, interprétée comme de probables ruptures sur les plans stratigraphiques des bancs d'insolubles intercalés dans la formation de sel.

Cette étude présente des algorithmes de génération et d'améliorations de maillages en simplexes pour la methode des éléments finis (triangles en 2d et tetraedres en 3D). Dans une première partie, après avoir montre que tout domaine plan défini par un contour extérieur et un ensemble de points internes représentant sa discrétisation peut être triangule, on expose et on justifie un algorithme simple de maillages en triangles. On prouve ensuite que l'opération de changement de diagonales dans un quadrilatère convexe permet d'atteindre toute les topologies realisables. Dans la seconde partie, on étudie le cas tridimensionnel et on donne quelques propriétés sur l'existence d'une tetraedrisation quand on se fixe le maillage en facettes triangulaires de la surface extérieure du domaine et les points internes pour la discrétisation. On décrit plusieurs heuristiques d'améliorations topologiques de maillages tetraedriques et on compare leur efficacité pratique sur quelques exemples industriels tires de la mécanique des fluides: on examine ainsi un algorithme glouton généralisant la démarche bidimensionnelle, un algorithme base sur la methode statistique du recuit simule et des algorithmes de type Divide and Conquer couples avec des procédures non topologiques simples comme le barycentrage des Nuds d'une discrétisation. Ces derniers algorithmes provoquent des améliorations conséquentes même sur des maillages de topologies très défavorables

Cette thèse se place dans un cadre de reconstruction urbaine et propose un corpus algorithmique pour extraire des formes simples sur les Modèles Numériques d'Elévation. Ce type de données décrit le relief d'une zone urbaine par une grille régulière de points à chacun desquels est associée une information de hauteur. Les modèles utilisés reposent sur l'utilisation de processus ponctuels marqués. Il s'agit de variables aléatoires dont les réalisations sont des configurations d'objets géométriques. Ces modèles permettent d'introduire des contraintes sur la forme des objets recherchés dans une image ainsi qu'un terme de régularisation modélisé par des interactions entre les objets. Une énergie peut être associée aux configurations d'objets et la configuration minimisant cette énergie trouvée au moyen d'un recuit-simulé couplé à un échantillonneur de type Monte Carlo par Chaîne de Markov à sauts réversibles (RJMCMC). Nous proposons quatre modèles pour extraire des caricatures de bâtiments à partir de descriptions altimétriques de zones urbaines denses. Chaque modèle est constitué par une forme d'objet, une énergie d'attache aux données et une énergie de régularisation. Les deux premiers modèles permettent d'extraire des formes simples (rectangles) en utilisant une contrainte d'homogénéité pour l'un et une détection des discontinuités pour l'autre. Le troisième modèle modélise les bâtiments par une forme polyhédrique. Le dernier modèle s'intéresse à l'apport d'une coopération entre des objets simples. Les algorithmes obtenus, automatiques, sont évalués sur des données réelles fournies par l'IGN (MNE Laser et optiques de différentes qualités).

Etude de certains problèmes liés aux ordonnancements et à leur implantation sur micro-ordinateur. Dans une première partie on s'intéresse à des problèmes d'ordonnancement à contraintes potentielles avec des spécificités données. Dans la seconde partie, on étudie diverses représentations géographiques des résultats (variantes de la méthode de Gantt), qui se feront sur un nombre minimun de lignes. Dans la dernière partie on s'intéresse aux problèmes d'ordonnancement à contraintes disjonctives

Dans cette thèse, nous traitons des problèmes d'intégration des décisions prises aux niveaux planification (tactique) et ordonnancement (opérationnel). Que ce soit en théorie ou en pratique, ces deux niveaux sont habituellement traités indépendamment l'un de l'autre. Ainsi, les objectifs de production à réaliser sont souvent incohérents avec la capacité réelle de l'atelier. Cette thèse propose des méthodes de résolution pour des problèmes intégrés de planification et d'ordonnancement. Nous développons un nouveau modèle mathématique qui prend en compte de manière originale les contraintes de séquencement des opérations sur les machines, garantissant ainsi la faisabilité du plan de production. Ce modèle est résolu à l'aide d'une heuristique Lagrangienne pour une séquence des opérations axée. Notre approche est originale à double titre : dans la mise à jour des multiplicateurs Lagrangiens (puisque il existe un nombre exponentiel de contraintes de capacité dans notre modèle), et par la proposition d'une nouvelle procédure de lissage pour la construction d'une solution réalisable. Nous développons ensuite deux approches, basées sur le recuit simulé et la recherche taboue, qui permettent d'améliorer la séquence des opérations sur les ressources et ainsi de chercher un plan de production optimal associé à une séquence réalisable. De nombreux résultats expérimentaux ont été effectués et valident l'efficacité de nos approches.