Computational Grids are large infrastructures composed of several components such as clusters, or massively parallel machines, generally spread across a country or the world, linked together through some network such as Internet, and allowing a transparent access to any resource. Grids have become unavoidable for a large part of the scientific community requiring computational power such as high-energy physics, bioinformatics or earth observation. Large projects are emerging, often at an international level, but even if Grids are on the way of being efficient and user-friendly systems, computer scientists and engineers still have a huge amount of work to do in order to improve their efficiency. Amongst a large number of problems to solve or to improve upon, the problem of scheduling the work and balancing the load is of first importance.<p><p><p>This work concentrates on the way the work is dispatched on such systems, and mainly on how the first level of scheduling – generally name brokering, or meta-sheduling – is performed. We deeply analyze the behavior of popular strategies, compare their efficiency, and propose a new very efficient brokering policy providing notable performances, attested by the large number of simulations we performed and provided in the document.<p><p><p>The work is mainly split in two parts. After introducing the mathematical framework on which the following of the manuscript is based, we study systems where the grid brokering is done without any feed-back information, i.e. without knowing the current state of the clusters when the resource broker – the grid component receiving jobs from clients and performing the brokering – makes its decision. We show here how a computational grid behaves if the brokering is done is such a way that each cluster receives a quantity of work proportional to its computational capacity.<p><p><p>The second part of this work is rather independent from the first one, and consists in the presentation of a brokering strategy, based on Whittle's indices, trying to minimize as much as possible the average sojourn time of jobs. We show how efficient the proposed strategy is for computational grids, compared to the ones popular in production systems. We also show its robustness to several parameter changes, and provide several very efficient algorithms allowing to make the required computations for this index policy. We finally extend our model in several directions.<p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

Pourquoi à l’ère du digital, les particuliers préfèrent-ils encore opérer des transactions immobilières avec un intermédiaire ? Quelles sont les perspectives qu’offre Internet aux acteurs de l’intermédiation ? Et quelles sont les limites de cette transformation digitale ? Les travaux développés dans la présente thèse visent à apporter des éléments de réponses à ces questions aux professionnels de l’immobilier résidentiel souhaitant mieux appréhender le comportement de leurs clients et du marché aujourd’hui. L’objectif de cette thèse est de contribuer à améliorer la compréhension des systèmes d’intermédiation, et en particulier de ce qui amène les acheteurs et les vendeurs à utiliser ces services, sur le marché immobilier résidentiel français. / Why, during the digital era, individuals still prefer transaction operations through an estate agent? What do the Internet perspectives offer to the intermediation actors? And what are the Limits of this digital transformation?The work developed in this dissertation aim to provide answers elements to those questions to estate professionals wishing to understand better the behavior of their customers and the market today. The objective of this dissertation is to contribute to the comprehension of improving the intermediation systems, and particularly what brings buyers and sellers to use these services on the real estate French market.

L’intérêt des différents langages de la famille des diagrammes de décisionvalués (VDD) est qu’ils admettent des algorithmes en temps polynomialpour des traitements (comme l’optimisation, la cohérence inverse globale,l’inférence) qui ne sont pas polynomiaux (sous l’hypothèse P 6= NP), si ilssont effectués sur le problème dans sa forme originale tel que les réseaux decontraintes ou les réseaux bayésiens.Dans cette thèse, nous nous intéressons au problème de configuration deproduit, et plus spécifiquement, la configuration en ligne avec fonction de valuationassociée (typiquement, un prix). Ici, la présence d’un utilisateur enligne nous impose une réponse rapide à ses requêtes, rapidité rendant impossiblel’utilisation de langages n’admettant pas d’algorithmes en temps polynomialpour ces requêtes. La solution proposée est de compiler hors-ligneces problèmes vers des langages satisfaisant ces requêtes, afin de diminuer letemps de réponse pour l’utilisateur.Une première partie de cette thèse est consacrée à l’étude théorique desVDD, et plus particulièrement les trois langages Algebraic Decision Diagrams,Semi ring Labelled Decision Diagrams et Affine Algebraic Decision Diagrams(ADD, SLDD et AADD). Nous y remanions le cadre de définition des SLDD,proposons des procédures de traductions entre ces langages, et étudions la compacitéthéorique de ces langages. Nous établissons dans une deuxième partie lacarte de compilation de ces langages, dans laquelle nous déterminons la complexitéalgorithmique d’un ensemble de requêtes et transformations correspondantà nos besoins. Nous proposons également un algorithme de compilationà approche ascendante, ainsi que plusieurs heuristiques d’ordonnancement devariables et contraintes visant à minimiser la taille de la représentation aprèscompilation ainsi que le temps de compilation. Enfin la dernière partie estconsacrée à l’étude expérimentale de la compilation et de l’utilisation de formescompilées pour la configuration de produit. Ces expérimentations confirmentl’intérêt de notre approche pour la configuration en ligne de produit.Nous avons implémenté au cours de cette thèse un compilateur (le compilateurSALADD) pleinement fonctionnel, réalisant la compilation de réseauxde contraintes et de réseaux bayésiens, et avons développés un ensemble defonctions adaptées à la configuration de produit. Le bon fonctionnement etles bonnes performances de ce compilateur ont été validés via un protocole devalidation commun à plusieurs solveurs. / The different languages from the valued decision diagrams (VDD) family benefitfrom polynomial-time algorithms for some tasks of interest (such as optimization,global inverse consistency, inference) for which no polynomial-timealgorithm exists (unless P = NP) when the input is a constraint network ora Bayesian network considered at start.In this thesis, we focus on configuration product problems, and more specificallyon-line configuration with an associated valuation function (typically, aprice). In this case, the existence of an on-line user forces us to quickly answerto his requests, making impossible the use of languages that does not admitpolynomial-time algorithm for this requests. Therefore, our solution consistsin an off-line compilation of these problems into languages that admit suchpolynomial-time algorithms, and thus decreasing the latency for the user.The first part of this thesis is dedicated to the theoretical study of VDDs,an more specifically Algebraic Decision Diagrams (ADDs), Semi ring LabelledDecision Diagrams (SLDDs) and Affine Algebraic Decision Diagrams(AADDs). We revisit the SLDD framework, propose translation proceduresbetween these languages and study the succinctness of these languages. In asecond part, we establish a knowledge compilation map of these languages,in which we determine the complexity of requests and transformations correspondingto our needs. We also propose a bottom-up compilation algorithmand several variables and constraints ordering heuristics whose aim is to reducethe size of the compiled form, and the compilation time. The last partis an experimental study of the compilation and the use of the compiled formin product configuration. These experimentations confirm the interest of ourapproach for on-line product configuration.We also implemented a fully functional bottom-up compiler (the SALADDcompiler), which is capable of compiling constraints network and Bayesian networkinto SLDDs. We also developed a set of functions dedicated to productconfiguration. The proper functioning and good performances of this programwas validated by a validation protocol common to several solvers.

Cette thèse propose la méthodologie de dimensionnement optimal pour optimiser la configuration de système d'énergie hybride. Pour cela, nous utilisons une approche pour la génération de base de règles floues et une optimisation automatiques au moyen d'algorithme génétique et d'un PSO adaptés avec le floue. Ces algorithmes nous permet d'obtenir le nombre optimal de panneaux photovoltaïques, d'éoliennes et des batteries, minimisant le coût total du système et garantissant la disponibilité permanente de l'électricité pour couvrir les besoins énergétiques. L'historique horaire de vitesse du vent, d’ensoleillement, sont utilisés pour modéliser la production des éoliennes, la production photovoltaïque et de charge. Le coût total est la fonction objective et la taille technique est une contrainte. / This thesis proposes the optimum sizing methodology to optimize the configuration of hybrid energy system. For this, we use an approach for automatic fuzzy rule base generation and optimization by means of Fuzzy-Adaptive Genetic Algorithm and fuzzy adaptive PSO. This Algorithms allows us to obtain the optimal number of photovoltaic panels, wind turbines and storages units, ensuring the minimal global high efficiency system total cost and guaranteeing the permanent availability of energy to cover the load energy requirements. Historical hourly wind speed, solar irradiance and load data are used to stochastically model the wind turbines, photovoltaic generation and load. The total cost is the objective function and the technical size is a constraint.

L'objectif de cette thèse est la gestion et le dimensionnement optimaux d'un Système de Stockage d'Énergie (SSE) couplé à une production d'électricité issue d'Énergies Renouvelables Intermittentes (EnRI). Dans un premier temps, un modèle technico-économique du système SSE-EnRI est développé, associé à trois scénarios types d'injection de puissance au réseau électrique : lissage horaire basé sur la prévision J-1 (S1), puissance garantie (S2) et combiné (S3). Ce modèle est traduit sous la forme d'un programme d'optimisation non linéaire de grande taille. Dans un deuxième temps, les stratégies heuristiques élaborées conduisent à une gestion optimisée - selon les critères de fiabilité, de productivité, d'efficacité et de profitabilité du système - de la production d'énergie avec stockage, appelée “charge adaptative” (CA). Comparée à un modèle linéaire mixte en nombres entiers (MILP), cette gestion optimisée, applicable en conditions opérationnelles, conduit rapidement à des résultats proches de l'optimum. Enfin, la charge adaptative est utilisée dans le dimensionnement optimisé du SSE - pour chacune des trois sources : éolien, houle, solaire (PV). La capacité minimale permettant de respecter le scénario avec un taux de défaillance et des tarifs de revente de l'énergie viables ainsi que les énergies conformes, perdues, manquantes correspondantes sont déterminées. Une analyse de sensibilité est menée montrant l'importance des rendements, de la qualité de prévision ainsi que la forte influence de l'hybridation des sources sur le dimensionnement technico-économique du SSE. / This thesis aims at presenting an optimal management and sizing of an Energy Storage System (ESS) paired up with Intermittent Renewable Energy Sources (IReN). Firstly, wedeveloped a technico-economic model of the system which is associated with three typical scenarios of utility grid power supply: hourly smoothing based on a one-day-ahead forecast (S1), guaranteed power supply (S2) and combined scenarios (S3). This model takes the form of a large-scale non-linear optimization program. Secondly, four heuristic strategies are assessed and lead to an optimized management of the power output with storage according to the reliability, productivity, efficiency and profitability criteria. This ESS optimized management is called “Adaptive Storage Operation” (ASO). When compared to a mixed integer linear program (MILP), this optimized operation that is practicable under operational conditions gives rapidly near-optimal results. Finally, we use the ASO in ESS optimal sizing for each renewable energy: wind, wave and solar (PV). We determine the minimal sizing that complies with each scenario, by inferring the failure rate, the viable feed-in tariff of the energy, and the corresponding compliant, lost or missing energies. We also perform sensitivity analysis which highlights the importance of the ESS efficiency and of the forecasting accuracy and the strong influence of the hybridization of renewables on ESS technico-economic sizing.

Dans cette thèse, nous nous intéressons à une méthode de détection des ruptures dans une suite d’observations appartenant à un ensemble muni d’un noyau semi-défini positif. Cette procédure est une version « à noyaux » d’une méthode des moindres carrés pénalisés. Notre principale contribution est de montrer que, pour tout noyau satisfaisant des hypothèses raisonnables, cette méthode fournit une segmentation proche de la véritable segmentation avec grande probabilité. Ce résultat est obtenu pour un noyau borné et une pénalité linéaire, ainsi qu’une autre pénalité venant de la sélection de modèles. Les preuves reposent sur un résultat de concentration pour des variables aléatoires bornées à valeurs dans un espace de Hilbert, et nous obtenons une version moins précise de ce résultat lorsque l’on supposeseulement que la variance des observations est finie. Dans un cadre asymptotique, nous retrouvons les taux minimax usuels en détection de ruptures lorsqu’aucune hypothèse n’est faite sur la taille des segments. Ces résultats théoriques sont confirmés par des simulations. Nous étudions également de manière détaillée les liens entre différentes notions de distances entre segmentations. En particulier, nous prouvons que toutes ces notions coïncident pour des segmentations suffisamment proches. D’un point de vue pratique, nous montrons que l’heuristique du « saut de dimension » pour choisir la constante de pénalisation est un choix raisonnable lorsque celle-ci est linéaire. Nous montrons également qu’une quantité clé dépendant du noyau et qui apparaît dans nos résultats théoriques influe sur les performances de cette méthode pour la détection d’une unique rupture. Dans un cadre paramétrique, et lorsque le noyau utilisé est invariant partranslation, il est possible de calculer cette quantité explicitement. Grâce à ces calculs, nouveaux pour plusieurs d’entre eux, nous sommes capable d’étudier précisément le comportement de la constante de pénalité maximale. Pour finir, nous traitons de l’heuristique de la médiane, un moyen courant de choisir la largeur de bande des noyaux à base de fonctions radiales. Dans un cadre asymptotique, nous montrons que l’heuristique de la médiane se comporte à la limite comme la médiane d’une distribution que nous décrivons complètement dans le cadre du test à deux échantillons à noyaux et de la détection de ruptures. Plus précisément, nous montrons que l’heuristique de la médiane est approximativement normale centrée en cette valeur. / In this thesis, we focus on a method for detecting abrupt changes in a sequence of independent observations belonging to an arbitrary set on which a positive semidefinite kernel is defined. That method, kernel changepoint detection, is a kernelized version of a penalized least-squares procedure. Our main contribution is to show that, for any kernel satisfying some reasonably mild hypotheses, this procedure outputs a segmentation close to the true segmentation with high probability. This result is obtained under a bounded assumption on the kernel for a linear penalty and for another penalty function, coming from model selection.The proofs rely on a concentration result for bounded random variables in Hilbert spaces and we prove a less powerful result under relaxed hypotheses—a finite variance assumption. In the asymptotic setting, we show that we recover the minimax rate for the change-point locations without additional hypothesis on the segment sizes. We provide empirical evidence supporting these claims. Another contribution of this thesis is the detailed presentation of the different notions of distances between segmentations. Additionally, we prove a result showing these different notions coincide for sufficiently close segmentations.From a practical point of view, we demonstrate how the so-called dimension jump heuristic can be a reasonable choice of penalty constant when using kernel changepoint detection with a linear penalty. We also show how a key quantity depending on the kernelthat appears in our theoretical results influences the performance of kernel change-point detection in the case of a single change-point. When the kernel is translationinvariant and parametric assumptions are made, it is possible to compute this quantity in closed-form. Thanks to these computations, some of them novel, we are able to study precisely the behavior of the maximal penalty constant. Finally, we study the median heuristic, a popular tool to set the bandwidth of radial basis function kernels. Fora large sample size, we show that it behaves approximately as the median of a distribution that we describe completely in the setting of kernel two-sample test and kernel change-point detection. More precisely, we show that the median heuristic is asymptotically normal around this value.

Les travaux menés dans cette thèse de doctorat s’inscrivent dans le cadre d’un effort pluslarge d’automatisation des systèmes de simulation industriels. Dans l’industrie aéronautique,et plus particulièrement au sein d’Airbus, l’application historique de la simulation est laformation des pilotes. Il existe aussi des utilisations plus récentes dans la conception desystèmes, ainsi que dans l’intégration de ces systèmes. Ces dernières utilisations exigent untrès haut degré de représentativité, là où historiquement le plus important était le ressenti dupilote. Les systèmes sont aujourd’hui divisés en plusieurs sous-systèmes qui sont conçus, implémentéset validés indépendamment, afin de maintenir leur contrôle malgré l’augmentationde leurs complexités et la réduction des temps de mise sur le marché. Airbus maîtrise déjà lasimulation de ces sous-systèmes, ainsi que leurs intégrations en simulation. Cettemaîtriseest empirique, les spécialistes de la simulation reprennent l’ordonnancement d’intégrationsprécédentes, et l’adaptent à une nouvelle intégration. C’est un processus qui peut parfois êtrechronophage, et qui peut introduire des erreurs. Les tendances actuelles de l’industrie sont à la flexibilité des moyens de production, àl’intégration d’outils logistiques permettant le suivi, à l’utilisation d’outils de simulation enproduction, et à l’optimisation des ressources. Les produits sont de plus en plus souvent desitérations d’anciens produits améliorés, et les tests et simulations intégrés à leurs cycles de vie.Travailler de manière empirique dans une industrie qui nécessite de la flexibilité estune contrainte, et il est aujourd’hui important de facilement modifier des simulations. Laproblématique est donc de mettre en place des méthodes et outils permettant a priori degénérer des ordonnancements de simulations représentatifs.Afin de répondre à ce problème, nous avons mis en place une méthode permettant de décrireles composants d’une simulation, la manière dont cette simulation pourra être exécutée,ainsi que des fonctions permettant de générer des ordonnancements. Par la suite, nous avonsimplémenté un outil afin d’automatiser la recherche d’ordonnancement, en se basant sur desheuristiques. Enfin nous avons testé et vérifié notre méthode et outils sur des cas d’étudesacadémiques et industriels. / The work carried out in this Ph.D. thesis is part of a broader effort to automate industrialsimulation systems. In the aeronautics industry, and more especially within Airbus, thehistorical application of simulation is pilot training. There are also more recent uses in thedesign of systems, as well as in the integration of these systems. These latter applicationsrequire a very high degree of representativeness, where historically the most important factorhas been the pilot’s feeling. Systems are now divided into several subsystems that are designed, implemented andvalidated independently, in order tomaintain their control despite the increase in their complexity,and the reduction in time-to-market. Airbus already has expertise in the simulationof these subsystems, as well as their integration into a simulation. This expertise is empirical;simulation specialists use the previous integrations schedulings and adapt it to a newintegration. This is a process that can sometimes be time-consuming and can introduce errors.The current trends in the industry are towards flexible production methods, integrationof logistics tools for tracking, use of simulation tools in production, as well as resourcesoptimization. Products are increasingly iterations of older, improved products, and tests andsimulations are increasingly integrated into their life cycles. Working empirically in an industry that requires flexibility is a constraint, and nowadays itis essential to facilitate the modification of simulations. The problem is, therefore, to set upmethods and tools allowing a priori to generate representative simulation schedules.In order to solve this problem, we have developed a method to describe the elementsof a simulation, as well as how this simulation can be executed, and functions to generateschedules. Subsequently, we implemented a tool to automate the scheduling search, based onheuristics. Finally, we tested and verified our method and tools in academic and industrialcase studies.

Dans cette thèse nous nous intéressons à l'étude et à la résolution de problèmes d'optimisation dans le domaine du transport. La première problématique concerne le problème d'élaboration de tournées avec gestion des stocks, et nous considérons dans une seconde partie le problème du voyageur de commerce avec tirant d'eau. Nous avons développé des approches basées sur la recherche à voisinage variable pour résoudre ces problèmes NP-Difficiles, en proposant différentes structures de voisinages et schémas de résolution efficaces. L'évaluation globale des approches proposées sur des instances de la littérature montre leur efficacité. En particulier, nos algorithmes ont amélioré les résultats obtenus par les meilleures approches existantes pour ces deux problèmes. / This thesis deals with the study of optimization problems in the transportation domain. We first address the inventory routing problem and we consider the traveling salesman problem with draft limits in a second part. In both cases we have developed methods based on the variable neighborhood search to solve these NP-hard problems. We have proposed several efficient neighborhood structures and solving frameworks. The global evaluation of the proposed approach on sets of benchmarks available in the litterature shows a remarkable efficency and effectiveness. In particular, our algorithms have improved the results obtained by the current best approaches for these two problems.

Au cours des dernières années, l’utilisation des téléphones portables et tablettes s’est vue croitre de façon significative. De plus, la disponibilité et l’ubiquité de l’accès sans fil a permis de créer un environnement dans lequel les utilisateurs partout où ils sont accèdent en tout temps à des services se trouvant dans le cloud. Cet environnement appelé cloud sans fil consomme une quantité d’énergie significative et est responsable d’émissions considérables en carbone. Cette consommation massive d’énergie et émissions en carbone deviennent un problème majeur dans le secteur des technologies de la communication. Dans ce contexte, nous nous intéressons dans cette thèse à la réduction de la consommation d’énergie et des empreintes en carbone des réseaux d’accès de type mesh et réseaux de campus ainsi que les data centers des infrastructures cloud. Dans la première partie, nous nous intéressons aux réseaux mesh de type TDMA. Nous proposons des solutions pour le problème de routage et ordonnancement des liens qui permettent de réduire la consommation d’énergie dans le réseau. Nous étendons par la suite cette approche pour les réseaux de campus dans un contexte compatible avec le paradigme SDN. Dans la deuxième partie, nous nous intéressons à la réduction de la consommation l’énergie et des empreintes en carbone des infrastructures cloud distribuées, avec des couts variables de l’électricité et d’émission en carbone. Nous proposons des approches d’optimisations dans deux cas de figures : le cas d’un fournisseur cloud souhaitant réduire ses couts et dans le cas où les utilisateurs cloud spécifient des contraintes en carbone sous forme de Green SLA. / Over the last decade, there has been an increasing use of personal wireless devices, such as laptops, smartphones and tablets. The widespread availability of wireless access created an environment in which anywhere at anytime users access data and services hosted in cloud infrastructures. However, such wireless cloud network consumes a non-negligible amount of energy and generates a considerable amount of carbon, which is becoming a major concern in IT industry. In this context, we address the problem of reducing energy consumption and carbon footprint, as well as building green infrastructures in the two different parts of the wireless cloud: (i) wireless access networks including wireless mesh and campus networks, and (ii) data centers in a cloud infrastructure. In the first part of the thesis, we present an energy-efficient framework for joint routing and link scheduling in multihop TDMA-based wireless networks. At a later stage, we extended this framework to cover campus networks using the emerging Software Defined Networking (SDN) paradigm. In the second part of this thesis, we address the problem of reducing energy consumption and carbon footprint of cloud infrastructures. Specifically, we propose optimization approaches for reducing the energy costs and carbon emissions of a cloud provider owning distributed infrastructures of data centers with variable electricity prices and carbon emissions in two different setups: the case of a cloud provider trying to reduce its carbon emissions and operational costs as well as the case where green constraints are specified by the cloud consumers in the form of Green SLAs.

Ce mémoire traite du problème de la planification intégrée de la maintenance préventive et de la production, au niveau tactique, et ce dans le cas d'une entreprise produisant des biens pour satisfaire une demande client périodique. Le plan de production global obtenu s'étale sur un horizon de planification donné. Le système de production considéré est un système multi-états pouvant travailler à des états de fonctionnement intermédiaires entre le fonctionnement de tous les composants et l'arrêt total. Les composants du système sont assujettis à des pannes aléatoires au cours de l'horizon de planification. Dans le but de fournir un plan global de production et de maintenance, nous proposons la résolution de ce problème de planification visant à minimiser le coût global des activités de production et de maintenance, sous différents types de contraintes. Notre apport réside dans le développement et l'implementation de deux méthodes heuristiques utilisant la recherche à voisinage variable et les algorithmes génétiques, dans le but de résoudre ce problème de planification intégrée. Nous procédons ensuite à l'analyse et à la discussion des résultats obtenus afin d'évaluer les performances des heuristiques conçues.