L'intérêt porté au désassemblage est lié aux notions de recyclage et de récupération des composants et de la matière des produits manufacturés en fin de vie. La plupart des recherches dans le domaine du désassemblage sont concentrées sur la planification du processus et sur la représentation des gammes de désassemblage. Face au manque de travaux en commande en temps réel des systèmes de désassemblage nous avons proposé une solution visant l'optimisation du processus de désassemblage par une nouvelle approche de conduite des systèmes de désassemblage. La définition des équations de l'ordonnancement du désassemblage en temps réel garantie le réalisme du problème et nous assure l'originalité de l'approche. Une architecture de système de commande est proposée. Les interfaces de commande sont conçues sous l'environnement Visual C++ 6.0. Elles intègrent une analyse de l'équilibrage de la ligne et un module d'aide à la décision.

Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d’optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d’un espace représenté sous la forme d’un arbre qui a pour spécificité d’être hautement irrégulier. Pour accélérer l’exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l’irrégularité des calculs inhérents à l’arbre B&B et (ii) l’hétérogénéité inhérente aux environnements de calcul large échelle. Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d’algorithmes distribués pour l’équilibrage de charge afin de garantir qu’aucune entité de calcul n’est surchargée ou sous-utilisée. Nous montrons comment résoudre l’irrégularité des calculs sur différents type d’environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocoles spécifiques à des contextes homogènes, hétérogène en terme de puissance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses. / Branch and Bound (B&B) algorithms are exact methods used to solve combinatorial optimization problems (COPs). The computation process of B&B is extremely time-intensive when solving large problem instances since the algorithm must explore a very large space which can be viewed as a highly irregular tree. Consequently, B&B algorithms are usually parallelized on large scale distributed computing environments in order to speedup their execution time. Large scale distributed computing environments, such as Grids and Clouds, can provide a huge amount of computing resources so that very large B&B instances can be tackled. However achieving high performance is very challenging mainly because of (i) the irregular characteristics of B&B workload and (ii) the heterogeneity exposed by large scale computing environments. This thesis addresses and deals with the above issues in order to design high performance parallel B&B on large scale heterogeneous computing environments. We focus on dynamic load balancing techniques which are to guarantee that no computing resources are underloaded or overloaded during execution time. We also show how to tackle the irregularity of B&B while running on different computing environments, and consider to compare our proposed solutions with the state-of-the-art algorithms. In particular, we propose several dynamic load balancing algorithms for homogeneous, node-heterogeneous and link-heterogeneous computing platforms. In each context, our approach is shown to perform much better than the state-of-the-art approaches.

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

Cette thèse présente une nouvelle approche qui permet la compensation dynamique de mécanismes à quatre barres, c'est-à-dire l'annulation de la somme des forces et moments qu'un mécanisme exerce sur son environnement. Depuis plus de trois décennies des chercheurs se penchent sur le problème de la compensation. Les premières recherches n'ont abordé que le problème de la compensation statique. Par la suite, les chercheurs ont commencé à attaquer le problème de la compensation dynamique tout en le simplifiant en imposant une vitesse constante. Suivant une évolution naturelle, le problème abordé est devenu de plus en plus général mais les mécanismes qui répondaient aux attentes sont devenus eux aussi de plus en plus complexe car on leurs greffait des contrepoids, des contre-rotations, des pantographes. De plus, les conditions trouvées permettant la compensation dynamique étaient souvent suffisantes mais pas toujours nécessaires. L'objectif de cette thèse est de trouver des contraintes de compensations dynamiques (CCD) exprimées en fonctions des paramètres physiques, qui soient nécessaires et suffisantes, sans rien ajouter au mécanisme. Un mécanisme simple sera donc utilisé pour faire la démonstration qu'il est possible de trouver des CCD nécessaires et suffisantes. L'analyse démontrera qu'il existe trois ensembles de CCD permettant la compensation dynamique des mécanismes à quatre barres. Une vérification de ces CCD faite d'une façon analytique à l'aide des équations de Lagrange et d'une façon numérique à l'aide de la méthode de Newton prouverons la validité des CCD. Par la suite, des mécanismes à cinq barres seront étudiés, par contre cette analyse sera moins fructueuse puisque les résultats démontreront que les mécanismes à cinq barres doivent avoir trois contre-rotations pour être compensés dynamiquement. Finalement, les mécanismes à quatre barres compensés dynamiquement serviront de modules pour construire des mécanismes complexes compensés dynamiquement. Des mécanismes sériels plans ainsi que des mécanismes parallèles plans à trois degrés de liberté seront présentés. Cette thèse a donc démontré qu'il était possible d'établir des contraintes de compensation dynamique nécessaires et suffisantes pour des mécanismes à quatre barres. De plus, la démonstrations a été faites que des mécanismes plan à trois degrés de liberté peuvent eux aussi être compensés dynamiquement lors qu'ils sont construits à partir de mécanismes à quatre barres. Cela met donc la première pierre à la voie qui pourrait conduire au développement de mécanismes spatiaux.

Nous abordons dans cette thèse le problème de l'insensibilité dans les réseaux de files d'attente et quelques applications au partage de ressources informatiques. Tout d'abord, nous montrons que les réseaux de files d'attente symétriques avec le routage de Jackson ou de Kelly sont tous insensibles à la distribution des demandes de service même si à l'arrivée, au départ ou au changement de files d'un client quelconque, les autres clients dans chaque file sont permutés au hasard selon certaine loi dépendante de l'état du réseau. Nous identifions également certaines disciplines de service non symétriques pour lesquellesla propriété d'insensibilité est satisfaite. Ensuite, nous proposons deux nouvelles métriques de débit pour les réseaux de données. Nous montrons quelques propriétés génériques satisfaites par ces deux métriques et nous illustrons leur différence à travers quelques exemples. Enfin, nous montrons que l'équilibrage de sources de trafic élastique détériore la performance en termes de débit, et en présence de contrôle d'admission, de probabilité de blocage.

L'utilisation de systèmes de stockage de l'énergie électrique tels que les batteries nécessite l'assemblage de plusieurs cellules. Comme chacune de ces dernières peut avoir des caractéristiques légèrement différentes ainsi que des conditions d'environnement thermique ou de vieillissement distinctes, l'utilisation d'un système d'équilibrage permettant une bonne gestion de la répartition de l'énergie au sein des éléments qui composent le pack est nécessaire. Les travaux de recherche présentés se rapportent à l'étude et à la conception d'un tel circuit d'équilibrage à base de convertisseurs d'énergie intégrables ainsi qu'aux sollicitations électriques engendrées dans les cellules lors de son utilisation.

Cette thèse est une contribution à une démarche globale de conception rationnelle des systèmes d'assemblage. Elle concerne plus précisément le problème de génération des graphes de précédence, en vue de leur utilisation par les méthodes d'équilibrage des systèmes d'assemblage. Le premier chapitre de ce travail est consacré à la description de la problématique des systèmes d'assemblage. Le deuxième chapitre présente un état de l'art des approches de génération des graphes de précédence pour l'assemblage. Les propriétés de ceux-ci sont listées et comparées à celles des autres modèles des processus d'assemblage. L'objectif du troisième chapitre est l'élaboration d'une méthode systématique d'obtention des graphes de précédence à partir d'un ensemble de gammes d'assemblage. Dans ce but, deux algorithmes sont proposés. Ils sont basés sur la vérification d'une propriété structurelle – la propriété ? – qui est nécessaire et suffisante pour assurer l'équivalence d'un ensemble de gammes à un seul graphe de précédence. Un état de l'art des méthodes de conception des systèmes d'assemblage issues de l'équilibrage des lignes d'assemblage est présenté dans le quatrième chapitre. Le problème d'équilibrage consiste à trouver l'affectation des tâches aux postes, telle qu'elle assure la minimisation du temps de cycle total. Une approche systémique est proposée par la formulation de ce problème comme problème d'optimisation discrète, en vue de la résolution par la programmation dynamique. Le dernier chapitre est dédié à l'analyse des systèmes d'assemblage avec auto-équilibrage, dont la conception évite la résolution d'un problème d'équilibrage classique. Il est suffisant qu'un tel système satisfasse une contrainte technologique simple de placement des opérateurs (humains) sur la ligne – du plus lent au plus rapide – pour qu'il atteigne spontanément un comportement optimal du point de vue de l'équilibrage. Une analyse par simulation de tels systèmes est présentée. Ils peuvent être traités comme systèmes dynamiques hybrides à commutations et sauts autonomes. La condition suffisante de l'autoéquilibrage – le "bon ordre" – est démontrée en utilisant les critères de stabilité des systèmes dynamiques discrets.

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

La course à l'augmentation de la puissance de calcul qui se déroule depuis de nombreuses années entre les différents producteurs de matériel a depuis quelques années changé de visage: nous assistons en effet désormais à une véritable démocratisation des machines parallèles avec une complexification sans cesse croissante de la structure des processeurs. À terme, il est tout à fait envisageable de voir apparaître pour le grand public des architecture pleinement hétérogènes composées d'un ensemble de cœurs reliés par un réseau sur puce. La parallélisation et l'exécution parallèle d'applications sur les machines à venir soulèvent ainsi de nombreux problèmes. Parmi ceux-ci, nous nous intéressons ici au problème de l'ordonnancement d'un ensemble de tâches sur un ensemble de cœurs, c'est à dire le choix de l'affectation du travail à réaliser sur les ressources disponibles. Parmi les méthodes existantes, on distingue deux types d'algorithmes: en-ligne et hors-ligne. Les algorithmes en-ligne comme le vol de travail présentent l'avantage de fonctionner en l'absence d'informations sur le matériel ou la durée des tâches mais ne permettent généralement pas une gestion efficace des communications. Dans cette thèse, nous nous intéressons à l'ordonnancement de tâches en-ligne sur des plates-formes complexes pour lesquelles le réseau peut, par des problèmes de congestion, limiter les performances. Plus précisément, nous proposons de nouveaux algorithmes d'ordonnancement en-ligne, basés sur le vol de travail, ciblant deux configurations différentes. D'une part, nous considérons des applications pour lesquelles le graphe de dépendance est connu à priori. L'utilisation de cette information nous permet ainsi de limiter les quantités de données transférées et d'obtenir des performances supérieures aux meilleurs algorithmes hors-ligne connus. D'autre part, nous étudions les optimisations possibles lorsque l'algorithme d'ordonnancement connaît la topologie de la plate-forme. Encore une fois, nous montrons qu'il est possible de tirer parti de cette information pour réaliser un gain non-négligeable en performance. Nos travaux permettent ainsi d'étendre le champ d'application des algorithmes d'ordonnancement vers des architectures plus complexes et permettront peut-être une meilleure utilisation des machines de demain. / The race towards more processing power between all different hardware manufacturers has in recent years faced deep changes. We see nowadays a huge development in the use of parallel machines with more and more cores and increasingly complex architectures. It seems now clear that we will witness in a near future the development of cheap Network On Chip computers. Executing parallel applications on such machines raises several problems. Amongst them we take in this work interest in the problem of scheduling a set of tasks on a set of computing resources. Between all existing methods we can generally distinguish on-line or off-line algorithms. On-line algorithms like work-stealing present the advantage to work without informations on hardware or tasks durations but do not generally achieve an efficient control of communications. In this book we take interest in on-line tasks scheduling on complex platforms where networking can impact (through congestion) performance. More precisely, we propose several new scheduling algorithms based on work-stealing targeting two different configurations. In a first study, we consider applications whose dependency graph is known in advance. By taking advantage of this information we manage to limit the amount of data transfered and thus to achieve high performance and even outperform the best known off-line algorithms. Concurrently to that, we also study possible optimisations in the case where knowledge of platform topology is available. We show again that it is possible to use this information to enhance performance. Our work allows therefore to extend the application field of scheduling algorithms towards more complex architectures and we hope will allow a better use of tomorrow's machine.

Les applications de transport de particules Monte-Carlo consistent à étudier le comportement de particules se déplaçant dans un domaine de simulation. La répartition des particules sur le domaine de simulation n'est pas uniforme et évolue dynamiquement au cours de la simulation. La parallélisation de ce type d'applications sur des architectures massivement parallèles amène à résoudre une problématique complexe de répartition de charges de calculs et de données sur un grand nombre de cœurs de calcul.Nous avons d'abord identifié les difficultés de parallélisation des applications de transport de particules Monte-Carlo à l'aide d'analyses théoriques et expérimentales des méthodes de parallélisation de référence. Une approche semi-dynamique reposant sur des techniques de partitionnement a ensuite été proposée. Enfin, nous avons défini une approche dynamique capable de redistribuer les charges de calcul et les données tout en maintenant un faible volume de communication. L'approche dynamique a obtenu des accélérations en extensibilité forte et une forte réduction de la consommation mémoire par rapport à une méthode de réplication de domaine parfaitement équilibrée. / Monte Carlo particle transport applications consist in studying the behaviour of particles moving about a simulation domain. Particles distribution among simulation domains is not uniform and change dynamically during simulation. The parallelization of this kind of applications on massively parallel architectures leads to solve a complex issue of workloads and data balancing among numerous compute cores.We started by identifying parallelization pitfalls of Monte Carlo particle transport applications using theoretical and experimental analysis of reference parallelization methods. A semi-dynamic based on partitioning techniques has been proposed then. Finally, we defined a dynamic approach able to redistribute workloads and data keeping a low communication volume. The dynamic approach obtains speedups using strong scaling and a memory footprint reduction compared to the perfectly balanced domain replication method.