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

Actuellement on assiste à une émergence des applications des systèmes embarqués destinées à un large public d'utilisateurs. Ces applications sont de plus en plus complexes et diversifiées. Elles nécessitent une capacité de calcul accrue et doivent satisfaire, dans leurs exécutions, la prise en compte du temps réel. De plus, ces systèmes sur puce fonctionnent dans des conditions souvent difficiles et perturbantes. Ainsi, certaines contraintes temporelles, contraintes de ressources, contraintes de précédence ainsi que d'autres caractéristiques des systèmes généraux peuvent changer au cours d'exécution. Pour respecter leurs contraintes, ces systèmes doivent être capables de supporter la nature dynamique du monde réel depuis la modélisation de l'application jusqu'à son implémentation sur la plateforme d'exécution. Dans cette thèse une nouvelle approche combinant la modélisation haut niveau et l'ordonnancement sur une architecture reconfigurable dynamiquement de nouveau type, a été proposée. Cette approche est originale depuis ça conception en ciblant des applications fortement dynamiques et flexibles. De plus, l'ordonnanceur ainsi développé intègre un nouveau service qui est responsable de la prédiction des variables dynamiques afin d'aboutir à une meilleure exploitation de l'architecture et meilleure performance d'exécution. Des expérimentations ont été présentées sur des applications temps réel. / Embedded systems have important requirements such as reducing complexity and saving development effort. They have also to take account of applications constraints related to timing, resources, tasks precedence relations and other characteristics of general systems that may change during execution. To meet their constraints, these systems must be capable of supporting the dynamic nature of the real world at an early phase of their design. Dynamically reconfigurable architecture (DRA) is presented as the ideal solution to satisfy the highly dynamic and non-deterministic behaviour of current applications since it provides both high performance and run-time flexibility. In this thesis a new approach combining the high level modeling and scheduling on a dynamically reconfigurable architecture of a new type, has been proposed. Based on an original task graph model, the scheduling is performed by a predictive approach. The proposed method aims to better manage the reconfiguration process and minimize its latency. Experimental results based on the original DRA named OLLAF demonstrate the benefits and efficiency of our scheduling technique.

Les Problèmes d’Optimisation Combinatoire (COP) sont largement utilisés pour modéliser et résoudre un grand nombre de problèmes industriels. La résolution de ces problèmes pose un véritable défi en raison de leur inhérente difficulté, la plupart étant NP-difficiles. En effet, les COP sont difficiles à résoudre par des méthodes exactes car la taille de l’espace de recherche à explorer croît de manière exponentielle par rapport à la taille du problème. Les méta-heuristiques sont souvent les méthodes les plus efficaces pour résoudre les problèmes les plus difficiles. Malheureusement, bien des problèmes réels restent hors de portée des meilleures méta-heuristiques. Le parallélisme permet d’améliorer les performances des méta-heuristiques. L’idée de base est d’avoir plusieurs instances d’une méta-heuristique explorant de manière simultanée l’espace de recherche pour accélérer la recherche de solution. Les meilleures techniques font communiquer ces instances pour augmenter la probabilité de trouver une solution. Cependant, la conception d’une méthode parallèle coopérative n’est pas une tâche aisée, et beaucoup de choix cruciaux concernant la communication doivent être résolus. Malheureusement, nous savons qu’il n’existe pas d’unique configuration permettant de résoudre efficacement tous les problèmes. Ceci explique que l’on trouve aujourd’hui des systèmes coopératifs efficaces mais conçus pour un problème spécifique ou bien des systèmes plus génériques mais dont les performances sont en général limitées. Dans cette thèse nous proposons un cadre général pour les méta-heuristiques parallèles coopératives (CPMH). Ce cadre prévoit plusieurs paramètres permettant de contrôler la coopération. CPMH organise les instances de méta-heuristiques en équipes ; chaque équipe vise à intensifier la recherche dans une région particulière de l’espace de recherche. Cela se fait grâce à des communications intra-équipes. Des communications inter-équipes permettent quant a` elles d’assurer la diversification de la recherche. CPMH offre à l’utilisateur la possibilité d’ajuster le compromis entre intensification et diversification. De plus, ce cadre supporte différentes méta-heuristiques et permet aussi l’hybridation de méta-heuristiques. Nous proposons également X10CPMH, une implémentation de CPMH, écrite en langage parallèle X10. Pour valider notre approche, nous abordons deux COP du monde industriel : des variantes difficiles du Problème de Stable Matching (SMP) et le Problème d’Affectation Quadratique (QAP). Nous proposons plusieurs méta-heuristiques originales en version séquentielle et parallèle, y compris un nouvelle méthode basée sur l’optimisation extrémale ainsi qu’un nouvel algorithme hybride en parallèle coopératif pour QAP. Ces algorithmes sont implémentés grâce à X10CPMH. L’évaluation expérimentale montre que les versions avec parallélisme coopératif offrent un très bon passage à l’échelle tout en fournissant des solutions de haute qualité. Sur les variantes difficiles de SMP, notre méthode coopérative offre des facteurs d’accélération super-linéaires. En ce qui concerne QAP, notre méthode hybride en parallèle coopératif fonctionne très bien sur les cas les plus difficiles et permet d’améliorer les meilleures solutions connues de plusieurs instances. / Combinatorial Optimization Problems (COP) are widely used to model and solve real-life problems in many different application domains. These problems represent a real challenge for the research community due to their inherent difficulty, as many of them are NP-hard. COPs are difficult to solve with exact methods due to the exponential growth of the problem’s search space with respect to the size of the problem. Metaheuristics are often the most efficient methods to make the hardest problems tractable. However, some hard and large real-life problems are still out of the scope of even the best metaheuristic algorithms. Parallelism is a straightforward way to improve metaheuristics performance. The basic idea is to perform concurrent explorations of the search space in order to speed up the search process. Currently, the most advanced techniques implement some communication mechanism to exchange information between metaheuristic instances in order to try and increase the probability to find a solution. However, designing an efficient cooperative parallel method is a very complex task, and many issues about communication must be solved. Furthermore, it is known that no unique cooperative configuration may efficiently tackle all problems. This is why there are currently efficient cooperative solutions dedicated to some specific problems or more general cooperative methods but with limited performances in practice. In this thesis we propose a general framework for Cooperative Parallel Metaheuristics (CPMH). This framework includes several parameters to control the cooperation. CPMH organizes the explorers into teams; each team aims at intensifying the search in a particular region of the search space and uses intra-team communication. In addition, inter-team communication is used to ensure search diversification. CPMH allows the user to tune the trade-off between intensification and diversification. However, our framework supports different metaheuristics and metaheuristics hybridization. We also provide X10CPMH, an implementation of our CPMH framework developed in the X10 parallel language. To assess the soundness of our approach we tackle two hard real-life COP: hard variants of the Stable Matching Problem (SMP) and the Quadratic Assignment Problem (QAP). For all problems we propose new sequential and parallel metaheuristics, including a new Extremal Optimization-based method and a new hybrid cooperative parallel algorithm for QAP. All algorithms are implemented thanks to X10CPMH. A complete experimental evaluation shows that the cooperative parallel versions of our methods scale very well, providing high-quality solutions within a limited timeout. On hard and large variants of SMP, our cooperative parallel method reaches super-linear speedups. Regarding QAP, the cooperative parallel hybrid algorithm performs very well on the hardest instances, and improves the best known solutions of several instances.

Les progrès dans l'architecture de réseau informatique ajoutent continuellement de nouvelles fonctionnalités aux problèmes de routage des véhicules. Dans cette thèse, le problème de tournée des véhicules avec la collecte de donnée sans fil (WT-VRP) est étudié. Il recherche un itinéraire pour le véhicule chargé de collecter des informations auprès des stations ainsi qu'un planning efficace de collecte d'informations. La nouvelle fonctionnalité ajoutée ici est la possibilité de récupérer des informations via une transmission sans fil, sans visiter physiquement les stations du réseau. Le WT-VRP a des applications dans la surveillance sous-marine et la surveillance environnementale. Nous discutons les critères pour mesurer l'efficacité d'une solution et proposons des formulations de programmation linéaire en nombre entier mixte pour résoudre le problème. Des expériences computationnelles ont été réalisées pour accéder à la complexité numérique du problème et pour comparer les solutions selon les critères proposés. Ensuite, nous avons renforcé certains modèles ainsi que considéré différentes suppositions pour le réseaux sans fils. Finalement, pour être capable de résoudre le problème dans des réseaux de grande échelle, nous avons développés des méthodes heuristiques pour le WT-VRP. / The vehicle routing problem is one of the most studied problems in Operations Research.Different variants have been treated in the past 50 years and with technologicaladvances, new challenges appear. In this thesis, we introduce a new variation of theVRP appearing in wireless networks. The new characteristic added to this well-knowproblem is the possibility of pick-up information via wireless transmissions. In the contextconsidered here, a unique base station is connected with the outside and a vehicleis responsible for collecting information via wireless connection to the vehicle when it islocated in another sufficiently close station. Simultaneous transmissions are permitted.Time of transmission depends on the distance between stations, the amount of informationtransmitted, and other physical factors (e.g obstacles along the way, installedequipment). Information to be sent outside of the network is continuously generatedin each station at a constant rate. The first contribution of this thesis is the introductionof a mixed ILP formulation for a variation in which it is only possible to send all theinformation or nothing during a wireless transmission. For this model three differentstrategies are investigated: maximizing total amount of information extracted an theend of the time horizon; maximizing the average of the information in the vehicle ateach time point; and maximizing the satisfaction of each station at the end of the timehorizon. Each strategy is translated as a different objective function for the mixed ILPformulation. The problem is then reformulated by accepting the option of sending onlypart of the information during a wireless transmission and considering only the firststrategy,(i.e. maximizing the amount of information extracted at the end of the horizontime). For this new version, we present three mixed ILP formulations, each one withadvantages and disadvantages. These mixed ILP models are compared according to theCPU time, amount of information collected, gap of unresolved instances, etc. Becausein real life we need to solve problems with a large number of stations, in this thesis,we also propose heuristics methods for the second version of the problem introduced.We build some heuristics that do not depend on the mixed ILP model (as for exampleGreedy heuristics) and also matheuristcs. In our matheuristics our best model (a vehicleevent model) is used as a base for the development of construction of Heuristics aswell as local search heuristics.

Cette thèse aborde un problème de transport appelé le Problème de m-Tournées Sélectives (PmTS) ou ”Team Orienteering Problem” en anglais. Le PmTS consiste à construire m tournées pour une flotte de véhicules afin de desservir un sous-ensemble sélectionné de clients. Dans le PmTS un service est fourni à chaque client visité en contrepartie de quoi, un gain est récolté. La tournée de chaque véhicule part d'un dépôt, passe par un sous-ensemble de clients et revient en un autre sans dépasser la longueur maximale autorisée. Chaque client peut être desservi au plus une fois par un unique véhicule. L'objectif est de maximiser le gain total récolté. Le PmTS étant un problème NP-difficile, notre objectif de recherche a consisté à proposer des heuristiques basées sur le principe général de ”Cluster first - Route second”. Ces algorithmes sont prévus pour être intégrés dans un logiciel de planification des tournées de techniciens de maintenance.

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

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshop<br /><br />Plus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.<br /> <br />Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.<br /><br />Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques. <br /><br />Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.

Partant d'un effort de délimitation de l'entrepreneuriat et d'une de ses figures les plus typiques - les enterprises nouvellement créées- sont mis au jour leurs difficultés stratégiques lors des premières années. L'auteur propose une revue de literature des comportements stratégiques utilisées par les firmes de moins de 8 ans et une description des facteurs cognitifs agissant à chaque phase de la decision stratégique. 9 cas sont étudiés dont deux en longitudinal Une modélisation des biais et heuristiques cognitifs est proposée ainsi que des solutions en matières d'accompagnement spécifique.

Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly.