La présente étude porte sur le développement et l’optimisation d’un modèle de générateur thermoélectrique placé sur la surface d’une source de chaleur. La particularité de ce modèle est que la source de chaleur est sujette à un flux de chaleur et à une température de surface fixes. L’objectif principal est de développer un modèle de générateur thermoélectrique d’intérêt dans ce contexte particulier qui pourra s’adapter à différentes sources de chaleur et qui pourra inclure différents systèmes de refroidissement. Le modèle a été créé intégralement à l’aide du logiciel Matlab. Un algorithme génétique multi objectif est ensuite utilisé comme outil d’optimisation afin de maximiser les performances tout en minimisant les coûts du générateur thermoélectrique. Les objectifs d’optimisation proposés sont donc de maximiser la puissance électrique et de minimiser le nombre de modules. Lorsqu’un collecteur thermique est inclus au système, il est aussi nécessaire de minimiser la puissance de pompage et l’aire totale d’échange du collecteur. Une première étude considère uniquement la puissance comme objectif d’optimisation afin d’observer l’impact des contraintes de température et de flux de chaleur de la source sur les designs optimaux. Des cas multiobjectifs seront ensuite étudiés avec les différents objectifs énoncés. Finalement, les performances de différents algorithmes d’optimisation heuristiques seront comparées entre eux en utilisant le modèle thermoélectrique développé comme banc d'essai. Les forces et faiblesses de chaque algorithme seront analysées selon divers critères de performance, lorsqu’appliqués à un cas d’optimisation complexe. / This study presents a model of a thermoelectric generator placed directly on the surface of a heat source. One unique feature of this model is that the heat source is subject to fixed heat flux and surface temperature that the system must respect. The main objective is to develop this model in this particular context with the possibility to be adapted to any heat source and the option to add a cooling system. The model has been developed entirely on the software Matlab. Then, a genetic algorithm is used to perform an optimisation in order to find the design with the maximal power output and minimal number of thermoelectric modules. With the cooling system included, the total surface of exchange and pumping power is also considered. A preliminary analysis is conducted to analyse the impact of the heat flux and surface temperature constraint on such system. Thereafter, a multi-objective optimisation is performed to find the optimal design considering multiple optimisation objectives. Finally, different heuristic algorithms are compared for solving the thermoelectric model proposed. The performance is discussed using different performance criteria to show the pros and cons of each heuristic algorithm when solving a complex optimisation design problem.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019. / Les activités de distribution et d’entreposage sont des piliers importants de la chaîne d’approvisionnement. Ils assurent la stabilité du flux de matières et la synchronisation de toutes les parties prenantes du réseau. Un centre de distribution (CD) agit comme un point de découplage entre l’approvisionnement, la production et les ventes. La distribution comprend un large éventail d’activités visant à assurer la satisfaction de la demande. Ces activités passent de la réception au stockage des produits finis ou semi-finis, à la préparation des commandes et à la livraison. Les opérations d’un CD sont maintenant perçues comme des facteurs critiques d’amélioration. Elles sont responsables de la satisfaction d’un marché en évolution, exigeant des délais de livraison toujours plus rapides et plus fiables, des commandes exactes et des produits hautement personnalisés. C’est pourquoi la recherche en gestion des opérations met beaucoup d’efforts sur le problème de gestion des CDs. Depuis plusieurs années, nous avons connu de fortes avancées en matière d’entreposage et de préparation de commandes. L’activité de préparation de commandes est le processus consistant à récupérer les articles à leur emplacement de stockage afin d’assembler des commandes. Ce problème a souvent été résolu comme une variante du problème du voyageur de commerce, où l’opérateur se déplace à travers les allées de l’entrepôt. Cependant, les entrepôts modernes comportent de plus en plus de familles de produits ayant des caractéristiques très particulières rendant les méthodes conventionnelles moins adéquates. Le premier volet de cette thèse par articles présente deux importants et complexes problèmes de manutention des produits lors de la préparation des commandes. Le problème de préparation des commandes a été largement étudié dans la littérature au cours des dernières décennies. Notre recherche élargit le spectre de ce problème en incluant un ensemble de caractéristiques associées aux installations physiques de la zone de prélèvement, comme les allées étroites, et aux caractéristiques des produits (poids, volume, catégorie, fragilité, etc.). Une perspective plus appliquée à la réalité des opérations est utilisée dans notre développement d’algorithmes. Les déplacements liés à la préparation des commandes sont fortement influencés par le positionnement des produits. La position des produits dans la zone de prélèvement est déterminée par une stratégie d’affectation de stockage (storage assignment strategy). Beaucoup de ces stratégies utilisent de l’information sur les ventes des produits afin de faciliter l’accès aux plus populaires. Dans l’environnement concurrentiel d’aujourd’hui, la durée de vie rentable d’un produit peut être relativement courte. Des promotions peuvent également être faites pour pousser différents produits sur le marché. Le positionnement fourni par la stratégie d’hier ne sera probablement plus optimal aujourd’hui. Il existe plusieurs études mesurant l’impact d’une bonne réaffectation de produits sur les opérations de prélèvement. Cependant, ils étudient la différence des performances avec les positionnements passés et actuels. La littérature démontre clairement que cela apporte des avantages en termes d’efficacité. Toutefois, les déplacements nécessaires pour passer d’une position à une autre peuvent constituer une activité très exigeante. Ceci constitue le second volet de cette thèse qui présente des avancées intéressantes sur le problème de repositionnement des produits dans la zone de prélèvement. Nous présentons le problème de repositionnement des produits sous une forme encore peu étudiée aux meilleurs de nos connaissances : le problème de repositionnement. Plus précisément, nous étudions la charge de travail requise pour passer d’une configuration à l’autre. Cette thèse est structuré comme suit. L’introduction présente les caractéristiques et les missions d’un système de distribution. Le chapitre 1 fournit un survol de la littérature sur les principales fonctions d’un centre de distribution et met l’accent sur la préparation des commandes et les décisions qui affectent cette opération. Le chapitre 2 est consacré à l’étude d’un problème de préparation de commandes en allées étroites avec des équipements de manutention contraignants. Dans le chapitre 3, nous étudions un problème de préparation des commandes où les caractéristiques des produits limitent fortement les routes de prélèvement. Le chapitre 4 présente une variante du problème de repositionnement (reassignment) avec une formulation originale pour le résoudre. La conclusion suit et résume les principales contributions de cette thèse. Mots clés : Préparation des commandes, entreposage, problèmes de routage, algorithmes exacts et heuristiques, réaffectation des produits, manutention. / Distribution and warehousing activities are important pillars to an effective supply chain. They ensure the regulation of the operational flow and the synchronization of all actors in the network. Hence, distribution centers (DCs) act as crossover points between the supply, the production and the demand. The distribution includes a wide range of activities to ensure the integrity of the demand satisfaction. These activities range from the reception and storage of finished or semi-finished products to the preparation of orders and delivery. Distribution has been long seen as an operation with no or low added value; this has changed, and nowadays it is perceived as one of the critical areas for improvement. These activities are responsible for the satisfaction of an evolving market, requiring ever faster and more reliable delivery times, exact orders and highly customized products. This leads to an increased research interest on operations management focused on warehousing. For several years, we have witnessed strong advances in warehousing and order picking operations. The order picking activity is the process of retrieving items within the storage locations for the purpose of fulfilling orders. This problem has long been solved as a variant of the travelling salesman problem, where the order picker moves through aisles. However, modern warehouses with more and more product families may have special characteristics that make conventional methods irrelevant or inefficient. The first part of this thesis presents two practical and challenging material handling problems for the order picking within DCs. Since there are many research axes in the field of warehousing operations, we concentrated our efforts on the order picking problem and the repositioning of the products within the picking area. The order picking problem has been intensively studied in the literature. Our research widens the spectrum of this problem by including a set of characteristics associated with the physical facilities of the picking area and characteristics of the product, such as its weight, volume, category, fragility, etc. This means that a more applied perspective on the reality of operations is used in our algorithms development. The order picking workload is strongly influenced by the positioning of the products. The position of products within the picking area is determined by a storage assignment strategy. Many of these strategies use product sales information in order to facilitate access to the most popular items. In today’s competitive environment, the profitable lifetime of a product can be relatively short. The positioning provided by yesterday’s assignment is likely not the optimal one in the near future. There are several studies measuring the impact of a good reassignment of products on the picking operations. However, they study the difference between the two states of systems on the picking time. It is clear that this brings benefits. However, moving from one position to another is a very workload demanding activity. This constitutes the second part of this thesis which presents interesting advances on the repositioning of products within the picking area. We introduce the repositioning problem as an innovative way of improving performance, in what we call the reassignment problem. More specifically, we study the workload required to move from one setup to the next. This thesis is structured as follows. The introduction presents the characteristics and missions of a distribution system. Chapter 1 presents an overview of the literature on the main functions of a DC and emphasizes on order picking and decisions affecting this operation. Chapter 2 is devoted to the study of a picking problem with narrow aisles facilities and binding material handling equipment. In Chapter 3, we study the picking problem with a set of product features that strongly constrain the picking sequence. Chapter 4 presents a variant of the reassignment problem with a strong and new formulation to solve it. The conclusion follows and summarizes the main contributions of this thesis. Key words: Order-picking, warehousing, routing problems, exact and heuristic algorithms, products reassignment, material handling.

Dans cette thèse nous nous sommes intéressés à l'extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l'existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu'un robot ne peut transporter qu'un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu'un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :* Une modélisation linéaire ;* Une modélisation sous forme de graphe disjonctif ;* Plusieurs heuristiques de construction de solutions ;* Plusieurs recherches locales qui améliorent les solutions obtenues ;* Utilisation des algorithmes génétiques / mémétiques comme schéma global d'optimisation ;* De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.

Le problème de la classification non supervisée (clustering) a été largement étudié dans le contexte de l'analyse de données, où la structure naturelle des données est dévoilée en groupant des objets similaires tout en séparant ceux qui ne le sont pas. L'Aide Multicritère à la Décision (AMCD) modélise les préférences de décideurs et les aide à choisir une solution appropriée parmi un ensemble d'alternatives. Dans ce contexte, les problématiques du choix, du tri et du rangement ont été largement étudiés, alors que celle du clustering l'a été bien moins. De plus, la plupart de ces approches de résolution en AMCD utilisent des mesures de similarité et n'exploitent pas l'information préférentielle supplémentaire qui est disponible. Dans cette thèse nous étudions ce problème du clustering en AMCD en faisant d'abord un parallèle entre l'analyse de données et l'AMCD pour ensuite proposer le problème de la classification non supervisée en AMCD. Différents modèles sont alors proposés pour résoudre ce problème, ainsi que des algorithmes de résolution, qui sont validés sur un grand nombre de problèmes générés artificiellement. Pour terminer, nous envisageons différentes applications via l'utilisation de différentes mesures descriptives des classes, ainsi que l'extension des algorithmes à des volumes de données importants. Une application est résolue à la fin de la thèse pour illustrer l'intérêt des outils proposés.

Le formalisme « Problème de Satisfaction de Contraintes » (ou CSP pour Constraint Satisfaction Problem) peut être considéré comme un langage de représentation formelle qui couvre l'ensemble des problèmes dont la modélisation fait intervenir des contraintes. L'intérêt de ce formalisme réside dans l'exploitation de la généricité d'algorithmes de résolution puissants mais également dans la performance d'algorithmes dédiés à des problèmes particuliers.Dans ce travail de thèse, nous étudions la résolution de CSP par des méthodes de recherche arborescente basées sur la notion de « divergence » (une divergence est relative à la contradiction d’une décision proposée par une heuristique de référence). Dans ce cadre, nous proposons de nouveaux mécanismes d'amélioration des méthodes de recherche générales qui exploitent les échecs rencontrés pendant la résolution, en adoptant des heuristiques de pondération des variables et des valeurs. Nous proposons également d'autres techniques spécifiques aux méthodes à base de divergences qui conditionnent l’exploration de l’arbre de recherche développé, notamment la restriction des divergences, les différents modes de comptage ainsi que le positionnement des divergences. Ces propositions sont validées par des expérimentations numériques menées sur des problèmes de satisfaction de contraintes réels et aléatoires. Des comparaisons sont effectuées entre variantes de méthodes à divergences intégrant différentes combinaisons des améliorations et d’autres méthodes connues pour leur performance.Dans une seconde partie, nous étendons nos propositions à un contexte d'optimisation en considérant la résolution de problèmes d'ordonnancement avec contraintes de délais (time lags). Nous traitons l'adaptation d'une méthode de « recherche par montée de divergences » (Climbing Discrepancy Search) pour la résolution de ces problèmes. Nous validons les performances de certaines variantes de cette méthode intégrant les mécanismes proposés dans ce travail sur des problèmes-test de la littérature / The CSP (Constraint Satisfaction Problem) formalism can be considered as a simple example of a formal representation language covering all problems including constraints. The advantage of this formalism consists in the fact that it allows powerful general-purpose algorithms as much as useful specific algorithms.In this PhD thesis, we study several tree search methods for solving CSPs and focus on ones based on the discrepancy concept (a discrepancy is a deviation from the first choice of the heuristic). In this context, we propose improving mechanisms for general methods. These mechanisms take benefits from conflicts and guide the search by weighting the variables and the values. We propose also special mechanisms for methods based on discrepancies as the discrepancies restriction, the discrepancies counting, and the discrepancies positions. All propositions are validated by experiments done on real and random CSPs. We compare variants of methods based on discrepancies integrating several combinations of improvements and other methods known for their efficiency.In a second part, we extend our propositions to an optimisation context considering scheduling problems with time lags. In this purpose, we adapt a discrepancy-based method, Climbing Discrepancy Search, to solve these problems. Efficiency of some improved variants of this method is tested on known benchmarks

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

Cette thèse traite du problème de la redistribution dynamique parallèle efficace de la charge pour les problèmes numériques de très grande taille. Nous présentons tout d'abord un état de l'art des algorithmes permettant de résoudre les problèmes du partitionnement, du repartitionnement, du placement statique et du re-placement. Notre première contribution vise à étudier, dans un cadre séquentiel, les caractéristiques algorithmiques souhaitables pour les méthodes parallèles de repartitionnement. Nous y présentons notre contribution à la conception d'un schéma multi-niveaux k-aire pour le calcul sequentiel de repartitionnements. La partie la plus exigeante de cette adaptation concerne la phase d'expansion. L'une de nos contributions majeures a été de nous inspirer des méthodes d'influence afin d'adapter un algorithme de raffinement par diffusion au problème du repartitionnement.Notre deuxième contribution porte sur la mise en oeuvre de ces méthodes sur machines parallèles. L'adaptation du schéma multi-niveaux parallèle a nécessité une évolution des algorithmes et des structures de données mises en oeuvre pour le partitionnement. Ce travail est accompagné d'une analyse expérimentale, qui est rendue possible grâce à la mise en oeuvre des algorithmes considérés au sein de la bibliothèque Scotch. / This thesis concerns efficient parallel dynamic load balancing for large scale numerical problems. First, we present a state of the art of the algorithms used to solve the partitioning, repartitioning, mapping and remapping problems. Our first contribution, in the context of sequential processing, is to define the desirable features that parallel repartitioning tools need to possess. We present our contribution to the conception of a k-way multilevel framework for sequential repartitioning. The most challenging part of this work regards the uncoarsening phase. One of our main contributions is the adaptation of influence methods to a global diffusion-based heuristic for the repartitioning problem. Our second contribution is the parallelization of these methods. The adaptation of the aforementioned algorithms required some modification of the algorithms and data structure used by existing parallel partitioning routines. This work is backed by a thorough experimental analysis, which is made possible thanks to the implementation of our algorithms into the Scotch library.

Cette thèse développe des algorithmes pour des problèmes de transport ferroviaire et est réalisée en partenariat avec l'entreprise Eurotunnel qui exploite le tunnel sous la Manche. Ce partenariat s'est établi sous la forme d'une chaire avec l'École des Ponts où cette thèse a été menée. Nous développons trois sujets dans cette thèse: le premier est un problème opérationnel rencontré par Eurotunnel, les deux autres sont plus prospectifs et théoriques, et sont inspirés des problèmes de transport ferroviaire d'Eurotunnel.Le processus de création de grilles horaires pour le transport ferroviaire se découpe en plusieurs phases (estimation de la demande, détermination du réseau, planification des départs, affectation des trains et du personnel). Nous nous intéressons dans une première partie à la phase de planification des départs des trains sur un intervalle temporel, appliquée au cas spécifique d'Eurotunnel. L'objectif est de calculer les horaires des départs des trains depuis chacune des deux stations (Coquelles en France et Folkestone en Angleterre) en respectant des contraintes d'exploitation (sécurité, chargement, ...) et des accords commerciaux signés avec leurs partenaires (Eurostar, ...). De plus, la prise en compte des retards dès la planification des départs est primordiale pour limiter la propagation des perturbations de train en train sur le réseau. Nous avons développé des algorithmes de planification pour Eurotunnel tenant compte des contraintes du réseau et de la probabilité de retard pour chaque train. Ces algorithmes utilisent des outils standard de la Recherche Opérationnelle pour modéliser et résoudre ces problèmes d'optimisation.La tarification des billets est un enjeu majeur pour les entreprises de transport. Pour les compagnies aériennes, de nombreux algorithmes ont été étudiés pour définir le prix optimal des billets pour différentes classes de passagers. Nous appliquons dans une deuxième partie des méthodes standard de tarification (modèles de choix discrets) afin d'optimiser de manière globale les prix et les horaires des départs pour des entreprises de transport ferroviaire. Des outils classiques de l'optimisation stochastique, des modèles de choix discrets et des heuristiques sont utilisés dans nos algorithmes pour donner les meilleures solutions possibles en un temps de calcul limité.Nous nous intéressons dans une dernière partie à une classe de problèmes de transport, inspirés de ceux rencontrés par Eurotunnel, en donnant des algorithmes efficaces de résolution exacte ou approchée. Ces algorithmes permettent de donner une borne supérieure de la complexité temporelle de ces problèmes. La classe de problèmes étudiés consiste en la planification des départs de navettes sur une ligne fixe, pour transporter d'une station A vers une station B des usagers arrivant de manière continue. Les navettes sont éventuellement autorisées à faire de multiples rotations pour transporter plusieurs vagues d'usagers. L'objectif est de limiter le temps d'attente des passagers avant le départ de leur navette. Des combinaisons originales de l'optimisation convexe et de la théorie des graphes (problèmes de plus court chemin) sont utilisées dans nos algorithmes / This thesis develops algorithms for rail transportation problems, conducted in relationship with the company Eurotunnel which operates the tunnel under the Channel. This partnership is a scientific chair with the École des Ponts et Chaussées, where this thesis was realized. We study three topics throughout the thesis: the first one is an operational problem faced by Eurotunnel, whereas the two other ones are prospective and theoretical problems inspired by their process.The planning process for rail transportation can be divided into several phases (demand estimation, line planning, scheduling of the departure times, rolling stock and crew planning). In a first part, we focus on the scheduling phase on a time interval, applied to the specific case of Eurotunnel. The objective is to compute the departure times of the trains for each of the two stations (Calais in France and Folkestone in England), satisfying operation constraints (security, loading, ...) and commercial agreements with their partners (Eurostar, ...). Moreover, taking into account the delays in the scheduling phase is essential to limit the propagation of the disturbances from train to train in the network. We develop scheduling algorithms for Eurotunnel taking into account the operation and commercial constraints, and the random distributions of the delays for each train. These algorithms use standard tools of Operations Research to model and solve these optimization problems.Pricing is a main issue for transportation companies. Many algorithms have been proposed to help airline companies to define optimized prices of the plane tickets for different classes of passengers. In a second part, we apply some standard pricing frameworks (discrete choice models) in order to optimize in a global way the prices and the departure times of the trains for rail transportation companies. Standard tools of stochastic optimization, discrete choice models, and some heuristics are used in our algorithms to compute the best possible solutions in a limited computation time.We focus in a last part on a class of transportation problems, inspired form Eurotunnel. We give efficient algorithms to solve exactly or to approximate the optimal solutions of these problems. These algorithms give an upper bound of the time complexity of this class of problems. The problems studied consist in scheduling the departure times of shuttles on a fixed trip, to transport passengers, arriving continuously at an initial station, to a given destination. The shuttles are potentially allowed to perform several rotations to transport several groups of passengers. The objective is to minimize the waiting time of the passengers before the depart of their shuttle. Original combinations of convex optimization and graph theory (shortest path problems) are used in our algorithms

Ma thèse porte sur la configuration dynamique de réseaux de communication radio vérifiant un certain nombre de contraintes (ou objectifs) et l'utilisation, si possible optimale, de l'ensemble des fréquences disponibles à un instant donné. C'est un problème NP-difficile dont l'enjeu économique est important pour l'entreprise TDF. J'ai construit et mis en œuvre des méta-heuristiques hybrides originales pour résoudre ce type de problème et assurer la meilleure qualité de service (QoS) possible. Les fréquences étant une denrée rare et chère, on peut se demander si, pendant un certain temps, une seule fréquence ne suffirait pas pour couvrir les besoins d'un secteur géographique donné. Ceci permettrait d'utiliser les autres fréquences pour d'autres applications. C'est le principe de base des réseaux SFN (Single Frequency Network) qui nécessitent l'optimisation des délais de transmission, le regroupement de certains émetteurs pour construire un tel réseau et le choix de la fréquence à allouer. Du point de vue informatique, il s'agit de réaliser simultanément plusieurs optimisations. La structure d'un réseau SFN doit être ajustable au cours du temps. J'ai développé un logiciel qui réalise ces opérations, à savoir : - sélection des émetteurs pour construire des réseaux (i.e. plaques) SFN, - optimisation des écarts de transmission dans chaque SFN, - choix de la meilleure fréquence possible pour chaque SFN. Les performances de ces algorithmes sont comparées avec la QoS des plans de fréquences utilisés en France et des pays voisins. Les résultats obtenus sont encourageants. / The purpose of my thesis is the dynamic construction of radio communication networks subject to multiple constraints and the optimal (if possible) use of the set of available frequencies at time t. This is an NP-Hard problem with important economical issues. I have designed and used original hybrid meta-heuristics for solving this kind of problems and providing the best possible QoS. Frequencies are rare and expansive therefore we can ask if a single frequency would not be enough, for a while, in order to cover the needs of a given geographical area. This would allow the use of the remaining frequencies for other applications. This is the principle of Single Frequency Networks (SFN) which necessitate the simultaneous optimization of transmission delays, of the allocated frequency and of their design. I have designed an original and e_cient software which performs these operations. We give experimental results for real benchmarks provided by TDF.

Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances / The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]