Dans cette thèse, nous nous intéressons à la problématique de transport usager dans un contexte multimodal, multi-objectif et dépendant du temps. Notre première contribution porte sur la définition du graphe de transfert, un modèle de représentation des réseaux multimodaux. Sur base de ce modèle, cette thèse propose plusieurs algorithmes de calculs d’itinéraires multimodaux et dépendants du temps mais simplement mono-objectifs. Toujours dans le souci de faire face aux exigences des usagers, nous nous intéressons dans une deuxième partie de cette au problème multi-objectif. Nous avons expérimenté dans un premier temps, la version dépendante du temps de l’algorithme exact de Martins, ensuite proposé une solution basée sur les algorithmes génétiques. Ces deux approches restent limitées faute de temps ou d’espace. L’algorithme hybride combinant la rapidité des méta-heuristiques et la complétude des méthodes exactes a donné de meilleurs résultats / The focus of this thesis is about multi-modal, multi-objective and time-dependent in passengers transport networks. We propose itineraries processing solutions that satisfy the user needs, as much as possible. The first part of our contributions begins with the definition of the transfer-graph model that is consistent with the distributed nature of multi-modal transport networks. Based on this model, we propose several itineraries processing algorithms. We have been interested, in a second part of this thesis, in developing multi-objective solutions to satisfy more constraints at the same time. We first experimented the time-dependent version of an exact algorithm based on Martins. We then proposed a solution based on a genetic algorithm. Both of these approaches are limited because of either excessive time response or memory space limit. The hybrid algorithm which combines the speed of meta-heuristics and completeness of exact methods, provide better results

Les problèmes d'ordonnancement peuvent être rencontrés dans plusieurs situations de la vie courante. Organiser des activités quotidiennes, planifier un itinéraire de voyage sont autant d'exemples de petits problèmes d'optimisation que nous tentons de résoudre tous les jours sans nous en rendre compte. Mais quand ces problèmes prennent des proportions plus grandes, il devient difficile au cerveau humain de gérer tous ces paramètres et le recours à une solution informatique s'impose. Les problèmes d'ordonnancement en contexte industriel sont nombreux et celui qui retient particulièrement notre attention dans le cadre de ce mémoire est le problème d'ordonnancement de commandes sur machine unique avec temps de réglages dépendant de la séquence. Ce problème fait partie de la classe de problèmes NP-Difficiles. Etant donnée sa complexité, ce problème ne peut être résolu par une méthode exacte. Les métaheuristiques représentent ainsi une bonne alternative pour obtenir des solutions de bonne qualité dans des délais très courts. Les algorithmes génétiques, qui font partie des algorithmes évolutionnaires, sont utilisés dans ce travail pour résoudre ce problème d'ordonnancement. La prolifération des architectures parallèles a ouvert la voie à un nouvel éventail d'approches pour optimiser les algorithmes et plus spécialement les métaheuristiques. Ce mémoire propose une stratégie de parallélisation de l'algorithme génétique pour en étudier les bénéfices. Le premier algorithme génétique proposé est implémenté sur le modèle d'un algorithme de la littérature. Cet algorithme ne s'est pas avéré performant pour toute la série de problèmes test et, pour cette raison, des modifications de paramètres ont été rendues nécessaires. Ces modifications ont donné naissance à une deuxième version séquentielle dont les résultats se sont avérés satisfaisants. Une troisième version a ensuite été implémentée avec une optique d'exécution parallèle selon un modèle en îlot et une topologie en anneau unidirectionnel. Un plan d'expérience a ensuite été mis au point selon plusieurs variables et vise à identifier les meilleures configurations de l'algorithme tant sur le plan de la qualité des résultats que sur le plan de l'accélération. Les résultats obtenus dans ce mémoire montrent que l'introduction de la parallélisation dans un algorithme génétique est bénéfique à ce dernier tant sur le plan qualité des résultats que sur le plan accélération. Dans un premier temps, la version sans communications n'a pas amélioré une grande partie des problèmes mais a pu atteindre des accélérations linéaires. Par la suite, l'introduction des échanges a nettement influé sur la qualité des résultats. En effet, en adoptant une stratégie de division de la taille de la population par le nombre de processeurs, l'algorithme génétique parallèle parvient à donner des résultats équivalents voire meilleurs que la version séquentielle, et ceci pour plusieurs fréquences d'échanges entre les populations.

Un ordonnancement est défini comme étant une allocation, dans le temps, des ressources (machines) disponibles aux différents travaux (tâches, jobs) à réaliser, dans le but d'optimiser un ou plusieurs objectifs. La richesse de la problématique de l'ordonnancement est due aux différentes interprétations que peuvent prendre les ressources et tâches. Ainsi, les ressources peuvent être des machines dans un atelier, des pistes de décollage et d'atterrissage dans un aéroport, des équipes dans un terrain de construction, des processeurs dans les ordinateurs, etc. Les tâches, quant à elles, peuvent être des opérations dans un processus de production, le décollage et l'atterrissage dans un aéroport, les étapes d'un projet de construction, l'exécution d'un programme informatique, etc. Les différentes tâches sont caractérisées par un degré de priorité et un temps d'exécution. Les ressources, quant à elles, sont caractérisées entre autres par une capacité, des temps de réglage, etc. Les problèmes d'ordonnancement sont généralement classés en deux modèles dépendamment du nombre d'opérations que requièrent les jobs: les modèles à une opération (modèle à machine unique et modèle à machines parallèles) et les modèles à plusieurs opérations dits modèles en ateliers (flow-shop, open-shop et job-shop). Bien entendu, il est également possible de trouver d'autres modèles, hybrides, qui sont des mélanges de ces deux modèles. Cette classification a permis, un tant soit peu, de mieux comprendre et cerner les problèmes d'ordonnancement réels. Toutefois, l'expérience a montré qu'il existe toujours un gouffre entre la théorie et ce qui se passe réellement dans les centres de production ou les prestations de services. Parmi les contraintes que la théorie d'ordonnancement n'a pas considérées jusqu'à un passé récent, nous pouvons citer les temps de latence des travaux, correspondant aux différents temps nécessaires devant s'écouler entre la fin d'une opération et le début de la prochaine opération d'un même job. Les temps de latence peuvent correspondre par exemple aux temps de transport des jobs à travers les ressources ou encore aux temps de refroidissement des jobs, avant leurs prochaines manipulations. Ces temps peuvent dans certains cas prendre des proportions importantes qu'une entreprise ne doit en aucun cas ignorer. Elle devrait même revoir sa politique d'ordonnancement pour pouvoir améliorer sa productivité. Dans ce mémoire, nous étudions le modèle de flow-shop à deux machines avec des temps de latence dans le but de minimiser le temps total d'accomplissement des jobs, appelé makespan. Pour ce faire, nous avons, tout d'abord, introduit la théorie de l'ordonnancement et survolé quelques concepts de la théorie de la NP-complétude ainsi que les différentes méthodes de résolution d'un problème d'ordonnancement en général, et du flow-shop à deux machines en particulier. Pour résoudre ce problème de flow-shop à deux machines, nous avons utilisé, dans un premier temps la méthode de branch and bound. Nous avons commencé par appliquer cet algorithme sur le cas particulier des temps d'exécution unitaires. Outre les bornes inférieures et supérieures, nous y avons également présenté des règles de dominance. Limité à 900 secondes, pour l'exécution d'une instance, cet algorithme a pu résoudre efficacement des instances n'excédant pas 30 jobs. Ensuite, nous sommes passés au cas où les temps d'exécution des jobs sont quelconques. Nous y avons présentés plusieurs bornes inférieures. Pour les bornes supérieures, nous avons conçu des heuristiques basées sur NEH, la règle de Johnson, la règle de Palmer et CDS. Au-delà de 10 jobs, l'algorithme de branch and bound, que nous avons implémenté, n'a pu résoudre efficacement les instances générées, même en posant 1h d'exécution pour chaque instance. Notons que les temps d'exécution des algorithmes, implémentant ces bornes inférieures et supérieures ainsi que ceux des règles de dominance, pour le cas unitaire, sont tous majorés par une complexité enO(n log n); n étant le nombre de jobs à ordonnancer. Dans un second temps, nous sommes passés à l'autre approche de résolution qu'est la méthode métaheuristique. Nous avons commencé notre étude par le développement d'un algorithme de recherche avec tabous. Des ajouts itératifs tels des procédures d'intensification et de diversification ont nettement amélioré les résultats générés par cet algorithme. Ensuite, nous avons conçu un algorithme génétique. Nous y avons incorporé une recherche locale pour améliorer les résultats. Cependant, l'algorithme de recherche avec tabous a produit de meilleurs résultats sur l'ensemble des instances testées. En guise de conclusion, nous avons discuté de nouvelles pistes de recherche à explorer.

Actuellement, les équipements employés dans les milieux industriels sont de plus en plus complexes. Ils exigent une maintenance accrue afin de garantir un niveau de service optimal en termes de fiabilité et de disponibilité. Par ailleurs, souvent cette garantie d'optimalité a un coût très élevé, ce qui est contraignant. Face à ces exigences la gestion de la maintenance des équipements est désormais un enjeu de taille : rechercher une politique de maintenance réalisant un compromis acceptable entre la disponibilité et les coûts associés à l'entretien du système. Les travaux de cette thèse partent par ailleurs du constat que dans plusieurs applications de l'industrie, le besoin de stratégies de maintenance assurant à la fois une sécurité optimale et une rentabilité maximale demeure de plus en plus croissant conduisant à se référer non seulement à l'expérience des experts, mais aussi aux résultats numériques obtenus via la résolution des problèmes d'optimisation. La résolution de cette problématique nécessite au préalable la modélisation de l'évolution des comportements des états des composants constituant le système, i.e, connaître les mécanismes de dégradation des composants. Disposant d'un tel modèle, une stratégie de maintenance est appliquée au système. Néanmoins, l'élaboration d'une telle stratégie réalisant un compromis entre toutes ces exigences représente un verrou scientifique et technique majeur. Dans ce contexte, l'optimisation de la maintenance s'impose pour atteindre les objectifs prescrits avec des coûts optimaux. Dans les applications industrielles réelles, les problèmes d'optimisation sont souvent de grande dimension faisant intervenir plusieurs paramètres. Par conséquent, les métaheuristiques s’avèrent une approche intéressante dans la mesure où d'une part, elles sacrifient la complétude de la résolution au profit de l'efficacité et du temps de calcul et d'autre part elles s'appliquent à un très large panel de problèmes.Dans son objectif de proposer une démarche de résolution d'un problème d'optimisation de la maintenance préventive, cette thèse fournit une méthodologie de résolution du problème d'optimisation des politiques de maintenance préventive systématique appliquée dans le domaine ferroviaire à la prévention des ruptures de rails. Le raisonnement de cette méthodologie s'organise autour de trois étapes principales : 1. Modélisation de l'évolution des comportements des états des composants constituant le système, i.e, connaître les mécanismes de dégradation des composants et formalisation des opérations de maintenance. 2. Formalisation d'un modèle d'évaluation de politiques de maintenance tenant compte aussi bien du facteur sûreté de fonctionnement du système que du facteur économique conséquent aux procédures de gestion de la maintenance (coûts de réparation, de diagnostic, d'indisponibilité). 3. Optimisation des paramètres de configuration des politiques de maintenance préventive systématique afin d'optimiser un ou plusieurs critères. Ces critères sont définis sur la base du modèle d'évaluation des politiques de maintenance proposé dans l'étape précédente / At present, equipments used on the industrial circles are more and more complex. They require a maintenance increased to guarantee a level of optimal service in terms of reliability and availability. Besides, often this guarantee of optimalité has a very high cost, what is binding. In the face of these requirements the management of the maintenance of equipments is from now on a stake in size: look for a politics of maintenance realizing an acceptable compromise between the availability and the costs associated to the maintenance of the system. The works of this thesis leave besides the report that in several applications of the industry, the need for strategies of maintenance assuring(insuring) at the same time an optimal safety and a maximal profitability lives furthermore there

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

Afin de pouvoir satisfaire la demande sans cesse croissante du trafic aérien, le futur système de gestion du trafic aérien utilisera le concept d'opérations basées sur les trajectoires (Trajectory Based Operations), qui augmentera la capacité du trafic aérien, en réduisant la charge de travail du contrôleur. Pour ce faire, les tâches de détection et de résolution de conflits seront transférées depuis la phase tactique vers la phase stratégique de la planification. Dans le cadre de ce nouveau paradigme pour le système de gestion du trafic aérien, nous introduisons dans cette thèse une méthodologie qui permet d'aborder ce problème de planification stratégique de trajectoires d'avion à l'échelle d'un pays ou d'un continent. Le but de la méthodologie proposée est de minimiser l'interaction globale entre les trajectoires d'avion, en affectant de nouveaux créneaux de décollage, de nouvelles routes et de nouveaux niveaux de vols aux trajectoires impliquées dans l'interaction. De plus, afin d'améliorer la robustesse du plan stratégique de vols obtenu, nous prenons en compte l'incertitude de la position de l'avion et de son heure d'arrivée à un point donné de la trajectoire de l'avion. Nous proposons une formulation mathématique de ce problème de planification stratégique conduisant à un problème d'optimisation discrète et un problème d'optimisation en variables mixtes, dont la fonction objectif est basée sur le nouveau concept d'interaction. Un algorithme efficace en termes de temps de calcul pour évaluer l'interaction entre des trajectoires d'avion pour des applications de grande taille est introduit et mis en œuvre. Des méthodes de résolution basées sur des algorithmes de type métaheuristique et métaheuristique hybride ont été développées pour résoudre ces problèmes d'optimisation de grande taille. Enfin, la méthodologie globale de planification stratégique de trajectoires d'avion est mise en œuvre et testée sur des données de trafic, prenant en compte des incertitudes, pour l'espace aérien français et l'espace aérien européen, impliquant plus de 30000 vols. Des plans de vols 4D sans conflits et robustes ont pu être produits avec des temps de calcul acceptables dans un contexte opérationnel, ce qui démontre la viabilité de l'approche proposée.

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

Cette thèse s'inscrit dans le cadre d'un projet pluridisciplinaire, le projet DRAMA, qui consiste à générer des scènes virtuelles 3D à partir des descriptions contenues dans les textes théâtraux. L'un des objectifs de ce projet consiste à simplifier au maximum la tâche des utilisateurs finaux en leur offrant un outil simple, rapide, et efficace. Ainsi, la technique adoptée dans cette étude est axée sur la modélisation déclarative d'environnements virtuels qui s'appuie sur trois phases (description, génération et prise de connaissances). La phase de description permet au concepteur de décrire l'environnement à partir d'un ensemble de propriétés, interprétées en un ensemble de contraintes destinées à un système de génération qui produit un ou plusieurs environnements virtuels solutions.Dans le cadre de ce projet DRAMA, des nouvelles méthodes de balisage ont été proposées afin de détecter les éléments essentiels pour la création d'une pièce théâtrale, notamment les informations sur les placements d'objets. Par ailleurs, les utilisateurs peuvent, aussi, lancer des requêtes au niveau du texte à partir de ces balises. Les propriétés sur les placements seront traduites en contraintes spatiales grâce aux données initialement stockées dans une base de connaissance qui utilise le langage XML. Une technique adoptant la méthode des métaheuristiques est ensuite utilisée pour la résolution des contraintes de placements obtenues précédemment. La gestion des propriétés physiques des objets (collision, gravité, friction) a été aussi gérée à partir d'un moteur physique. À la fin, les scènes solutions finales seront proposées à l'utilisateur, en utilisant un moteur de rendu 3D. / This thesis is part of a multidisciplinary project, the DRAMA project, which attempts to generate 3D virtual scenes from the descriptions which are obtained from theatrical text. This project aims to simplify, as soon as possible, the tasks of the end-users by providing simple, fast, and effective tools. Thus, the technique used in this study is focused on the declarative modeling of virtual environments that is based on three phases (description, generation and management of knowledge). The description phase allows the designer to describe the environment from a set of properties, interpreted as a set of constraints for a generation system which produces one or several virtual environments solutions. This project, new tagging methods have been proposed to detect essential for the creation of scene, including information on the placement of objects. In addition, users can also run queries in the text from these tags. Placement properties are translated into spatial constraints with the data originally stored in a knowledge base that uses XML. A technique adopting the method of metaheuristics is then used for solving constraints. The object physical properties (collision, gravity, friction) were also managed from a physics engine. At the end, the finals scenes solutions were be proposed to the user, using a 3D rendering engine.

Dans l’industrie, l’automaticien doit concevoir une loi de commande unique qu’il valide sur un prototype unique, ayant un degré de robustesse suffisant pour satisfaire un cahier des charges complexe sur un grand nombre de systèmes. Pour cela, la méthodologie de développement qu’il emploie consiste en un processus itératif expérimental (phase d’essai-erreur), qui fait grandement appel à l’expérience de l’ingénieur. Dans cette thèse, on tente de rendre la méthodologie de synthèse des correcteurs des asservissements plus efficace car plus directe et donc moins couteuse en temps de développement en calculant un correcteur final (structuré) par une attaque directe de la spécification système haut niveau. La complexité des spécifications systèmes haut-niveau nous pousse à l’emploi des métaheuristiques : ces techniques d’optimisation ne nécessitent pas la formulation du gradient, la seule contrainte étant la possibilité d’évaluer la spécification. Ainsi avons-nous proposé dans ce travail de reformuler les problèmes de commande robuste pour l’optimisation stochastique : on montre dans ce travail comment on peut synthétiser des correcteurs structurés à partir de problématiques de type H ou -synthèse et on montre que l’intérêt de l’approche formulée réside dans sa flexibilité et la prise en compte de contraintes « exotiques » complexes ; les algorithmes évolutionnaires s’avérant très performants et compétitifs, nous avons finalement développé sur cette base une méthode originale de synthèse de correcteurs structurés et robustes vis-à-vis de critères d’optimisation de forme quelconque. La validation de ces travaux a été réalisée sur des exemples industriels de viseurs. / In the industrial framework, the control engineer must design a unique control law that valid on a single prototype, with a sufficient degree of robustness to satisfy a complex specification on many systems. For that purpose, his development methodology consists of an experimental iterative process (trial and error phase), which relies heavily on the experience of the engineer. In this thesis, we try to make the methodology for computing controllers more efficient and more direct with a less costly development time by calculating a final structured controller by a direct optimization on the high level specification.The complexity of high-level specifications pushes us to the use of metaheuristics: these optimization techniques do not require the formulation of the gradient, the only constraint being the possibility of evaluating the specification. Thus we proposed in this work to reformulate robust control problems for stochastic optimization: we show in this work how to synthesize structured controllers for control problems such H synthesis or -synthesis and show that the interest of the formulated approach lies in its flexibility and the consideration of exotic complex constraints. Evolutionary algorithms proving very effective and competitive, we finally developed on this basis a new method for synthesizing robust and structured controllers with respect to any form of optimization criteria. The validation of this work was carried out on the industrial example of the line of sight stabilization problem.

No description available.