La qualité d'un plan d'exécution engendré par un optimiseur de requêtes est fortement dépendante de la qualité des estimations produites par le modèle de coûts. Malheureusement, ces estimations sont souvent imprécises. De nombreux travaux ont été menés pour améliorer la précision des estimations. Cependant, obtenir des estimations précises reste très difficile car ceci nécessite une connaissance préalable et détaillée des propriétés des données et des caractéristiques de l'environnement d'exécution. Motivé par ce problème, deux approches principales de méthodes d'optimisation ont été proposées. Une première approche s'appuie sur des valeurs singulières d'estimations pour choisir un plan d'exécution optimal. A l'exécution, des statistiques sont collectées et comparées à celles estimées. En cas d'erreur d'estimation, une ré-optimisation est déclenchée pour le reste du plan. A chaque invocation, l'optimiseur associe des valeurs spécifiques aux paramètres nécessaires aux calculs des coûts. Cette approche peut ainsi induire plusieurs ré-optimisations d'un plan, engendrant ainsi de mauvaises performances. Dans l'objectif d'éviter cela, une approche alternative considère la possibilité d'erreurs d'estimation dès la phase d'optimisation. Ceci est modélisé par l'utilisation d'un ensemble de points d'estimations pour chaque paramètre présumé incertain. L'objectif est d'anticiper la réaction à une sous-optimalité éventuelle d'un plan d'exécution. Les méthodes dans cette approche cherchent à générer des plans robustes dans le sens où ils sont capables de fournir des performances acceptables et stables pour plusieurs conditions d'exécution. Ces méthodes supposent souvent qu'il est possible de trouver un plan robuste pour l'ensemble de points d'estimations considéré. Cette hypothèse reste injustifiée, notamment lorsque cet ensemble est important. De plus, la majorité de ces méthodes maintiennent sans modification un plan d'exécution jusqu'à la terminaison. Cela peut conduire à de mauvaises performances en cas de violation de la robustesse à l'exécution. Compte tenu de ces constatations, nous proposons dans le cadre de cette thèse une méthode d'optimisation hybride qui vise deux objectifs : la production de plans d'exécution robustes, notamment lorsque l'incertitude des estimations utilisées est importante, et la correction d'une violation de la robustesse pendant l'exécution. Notre méthode s'appuie sur des intervalles d'estimations calculés autour des paramètres incertains, pour produire des plans d'exécution robustes. Ces plans sont ensuite enrichis par des opérateurs dits de contrôle et de décision. Ces opérateurs collectent des statistiques à l'exécution et vérifient la robustesse du plan en cours. Si la robustesse est violée, ces opérateurs sont capables de prendre des décisions de corrections du reste du plan sans avoir besoin de rappeler l'optimiseur. Les résultats de l'évaluation des performances de notre méthode indiquent qu'elle fournit des améliorations significatives dans la robustesse d'évaluation de requêtes. / The quality of an execution plan generated by a query optimizer is highly dependent on the quality of the estimates produced by the cost model. Unfortunately, these estimates are often imprecise. A body of work has been done to improve estimate accuracy. However, obtaining accurate estimates remains very challenging since it requires a prior and detailed knowledge of the data properties and run-time characteristics. Motivated by this issue, two main optimization approaches have been proposed. A first approach relies on single-point estimates to choose an optimal execution plan. At run-time, statistics are collected and compared with estimates. If an estimation error is detected, a re-optimization is triggered for the rest of the plan. At each invocation, the optimizer uses specific values for parameters required for cost calculations. Thus, this approach can induce several plan re-optimizations, resulting in poor performance. In order to avoid this, a second approach considers the possibility of estimation errors at the optimization time. This is modelled by the use of multi-point estimates for each error-prone parameter. The aim is to anticipate the reaction to a possible plan sub-optimality. Methods in this approach seek to generate robust plans, which are able to provide good performance for several run-time conditions. These methods often assume that it is possible to find a robust plan for all expected run-time conditions. This assumption remains unjustified. Moreover, the majority of these methods maintain without modifications an execution plan until the termination. This can lead to poor performance in case of robustness violation at run-time. Based on these findings, we propose in this thesis a hybrid optimization method that aims at two objectives : the production of robust execution plans, particularly when the uncertainty in the used estimates is high, and the correction of a robustness violation during execution. This method makes use of intervals of estimates around error-prone parameters. It produces execution plans that are likely to perform reasonably well over different run-time conditions, so called robust plans. Robust plans are then augmented with what we call check-decide operators. These operators collect statistics at run-time and check the robustness of the current plan. If the robustness is violated, check-decide operators are able to make decisions for plan modifications to correct the robustness violation without a need to recall the optimizer. The results of performance studies of our method indicate that it provides significant improvements in the robustness of query processing.

Le procédé de fabrication de mélanges (PM) consiste à déterminer les proportions optimales à mélanger d'un ensemble de composants de façon que le produit obtenu satisfasse un ensemble de spécifications sur leurs propriétés. Deux caractéristiques importantes du problème de mélange sont les bornes dures sur les propriétés du mélange et l'incertitude répandue dans le procédé. Dans ce travail, on propose une méthode pour la production de mélanges robustes en temps réel qui minimise le coût de la recette et la sur-qualité du mélange. La méthode est basée sur les techniques de l'Optimisation Robuste et sur l'hypothèse que les lois des mélange sont linéaires. On exploite les polytopes sous-jacents pour mesurer, visualiser et caractériser l'infaisabilité du PM et on analyse la modification des bornes sur les composants pour guider le procédé vers le ``meilleur`` mélange robuste. On propose un ensemble d'indicateurs et de visualisations en vue d'offrir une aide à la décision. / The oil blending process (BP) consists in determining the optimal proportions to blend from a set of available components such that the final product fulfills a set of specifications on their properties. Two important characteristics of the blending problem are the hard bounds on the blend's properties and the uncertainty pervading the process. In this work, a real-time optimization method is proposed for producing robust blends while minimizing the blend quality giveaway and the recipe's cost. The method is based on the Robust Optimization techniques and under the assumption that the components properties blend linearly. The blending intrinsic polytopes are exploited in order to measure, visualize and characterize the infeasibility of the BP. A fine analysis of the components bounds modifications is conducted to guide the process towards the ``best`` robust blend. A set of indices and visualizations provide a helpful support for the decision maker.

Dans un marché électrique concurrentiel, EDF a adapté ses outils de gestion de production pour permettre une gestion optimale de son portefeuille, particulièrement sur les horizons journaliers et infra-journaliers, derniers leviers pour une gestion optimisée de la production. Et plus l'horizon d'optimisation s'approche du temps réel, plus les décisions prises aux instants précédents deviennent structurantes voire limitantes en terme d'actions. Ces décisions sont aujourd'hui prises sans tenir compte du caractère aléatoire de certaines entrées du modèle. En effet, pour les décisions à court-terme, la finesse et la complexité des modèles déjà dans le cas déterministe ont souvent été un frein à des travaux sur des modèles tenant compte de l'incertitude. Pour se prémunir face à ces aléas, des techniques d'optimisation en contexte incertain ont fait l'objet des travaux de cette thèse. Nous avons ainsi proposé un modèle robuste de placement de la production tenant compte des incertitudes sur la demande en puissance. Nous avons construit pour cette fin un ensemble d'incertitude permettant une description fine de l'aléa sur les prévisions de demande en puissance. Le choix d'indicateurs fonctionnels et statistiques a permis d'écrire cet ensemble comme un polyèdre d'incertitude. L'approche robuste prend en compte la notion de coût d'ajustement face à l'aléa. Le modèle a pour objectif de minimiser les coûts de production et les pires coûts induits par l'incertitude. Ces coûts d'ajustement peuvent décrire différents contextes opérationnels. Une application du modèle robuste à deux contextes métier est menée avec un calcul du coût d'ajustement approprié à chaque contexte. Enfin, le présent travail de recherche se situe, à notre connaissance, comme l'un des premiers dans le domaine de la gestion optimisée de la production électrique à court terme avec prise en compte de l'incertitude. Les résultats sont par ailleurs susceptibles d'ouvrir la voie vers de nouvelles approches du problème. / Robust Optimization is an approach typically offered as a counterpoint to Stochastic Programming to deal with uncertainty, especially because it doesn't require any precise information on stochastic distributions of data. In the present work, we deal with challenging unit-commitment problem for the French daily electricity production under demand uncertainty. Our contributions concern both uncertainty modelling and original robust formulation of unit-commitment problem. We worked on a polyhedral set to describe demand uncertainty, using statistical tools and operational indicators. In terms of modelling, we proposed robust solutions that minimize production and worst adjustment costs due to uncertainty observation. We study robust solutions under two different operational contexts. Encouraging results to the convex unit-commitment problems under uncertainty are thus obtained, with intersting research topics for future work.

Plusieurs problèmes d'ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d'incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d'ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d'ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d'incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d'incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d'ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d'optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d'optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d'ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d'évaluer l'efficacité de notre méthode nous l'avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d'une manière uniforme et dont l'objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l'arbre de recherche consiste à calculer le volume d'un polytope. Enfin, pour montrer l'efficacité de chacune de ses méthodes, des résultats numériques sont présentés. / Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.

Les ports maritimes se confrontent à des exigences rigoureuses imposées par l'évolution de la taille de la flotte mondiale des porte-conteneurs et des zones de stockage qui arrivent à des niveaux de saturation élevés. Pour répondre à ces défis, plusieurs ports ont décidé de créer des terminaux multimodaux qui jouent le rôle de méga-hubs pour les terminaux maritimes, en vue de libérer les zones de stockage de ces terminaux, de développer la part du transport massifié de conteneurs et de réduire les émissions des gaz à effet de serre en utilisant des modes alternatifs à la route. Néanmoins, la gestion de ces nouveaux schémas logistiques est laborieuse. Cela s’explique par plusieurs facteurs, entre autres, la nature dynamique et distribuée de ces systèmes, la diversité des opérations et le manque des informations nécessaires au contrôle de flux. La finalité de cette thèse est de développer des approches capables de répondre aux besoins des opérateurs portuaires dans un terminal multimodal, avec prise en compte des différentes sources d’incertitudes. Deux problèmes d'optimisation sont principalement considérés dans cette thèse, à savoir : l'optimisation de tournées de navettes ferroviaires (The Rail Shuttle Routing Problem) et l'ordonnancement de grues de quai (The Quay Crane Scheduling Problem). En vue d'aborder la complexité et l’aspect incertain de ces problèmes, nous proposerons des modélisations mathématiques, ainsi que des approches de résolution basées sur l’optimisation par colonies de fourmis, l’optimisation robuste et le couplage Simulation-Optimisation. Les différents tests numériques effectués ont prouvé l’efficacité des algorithmes proposés et leur robustesse. / Today, seaports face increasingly stringent requirements imposed by the considerable growth of goods transited by sea. Indeed, the organization of the port sector has evolved rapidly and has caused several negative impacts, including pollution and congestion of terminals, which constitute today the major concerns of port operators. To address those challenges, several ports have decided to build multimodal terminals that act as mega-hubs for maritime terminals, in order to free the storage areas on the maritime terminals, to promote the use of consolidated container modes of transfer and to reduce greenhouse gas emissions by using alternative modes to the road. Nevertheless, the management of these new logistic systems is laborious. This is due to several factors, including the dynamic and distributed nature of these systems, the variety of operations, and the lack of information needed to control flow. The aim of this thesis is to develop approaches capable of meeting the needs of port operators in a multimodal terminal, taking into account the different sources of uncertainty. Two optimization problems are mainly considered in this thesis, namely : the Rail Shuttle Routing Problem(RSRP) and the Quay Crane Scheduling Problem(QCSP). To address the complexity and uncertainties of these problems, we propose new mathematical models, as well as some heuristics approaches based on ant colony optimization, robust optimization and Simulation-Optimization. The various numerical tests carried out proved the effectiveness and the robustness of the proposed algorithms.

Dans cette thèse, nous nous intéressons à des chaînes logistiques dont les acteurs de la chaîne sont des entités décisionnelles indépendantes. Plus précisément, notre cadre d'étude sera un "maillon" d'une chaîne logistique (relation client fournisseur) dont les acteurs (le client et le fournisseur) sont des entités décisionnelles indépendantes qui souhaitent mettre en place des processus de planification coopératifs en présence d'incertitude, sachant que le client fabriques des produits à la commande et le fournisseur sur stock. Dans ce contexte, la contribution majeure visée par nos travaux est l'intégration des connaissances imparfaites sur les données (date du besoin en composants, quantité nécessaire...etc.) afin de calculer le plan d'approvisionnement plus robuste (plan minimisant l'impact de l'incertitude). L'intégration des imperfections repose sur l'utilisation de la théorie des possibilités. Une fois le modèle de représentation des données imparfaites réalisé, nous proposons des méthodes de calcul de plan d'approvisionnement utilisant les informations supplémentaires grâce à la représentation des imperfections.

Nous étudions dans cette thèse le problème de gestion du risque physique en production électrique à l'horizon hebdomadaire. Dans un premier temps, nous nous intéressons à l'intégration de l'aléa d'apport hydraulique dans la gestion locale d'une vallée hydraulique. Cette approche est menée à l'aide de l'optimisation robuste et de règles de décision linéaires. Les résultats de multiples modes de simulation montrent que ces approches permettent de réduire notoirement les déversés en comparaison des modèles déterministes appliqués en exploitation, moyennant une faible augmentation du coût. La deuxième problématique traitée est la gestion active de la marge de production, définie comme l'écart entre l'offre totale et la demande totale, compte tenu des aléas affectant le système électrique. Il s'agit de déterminer quelles décisions optimales prendre, selon un certain critère économique, pour se couvrir contre un risque trop élevé de non-satisfaction de la demande dans au moins 99% des situations. Pour cela, une formulation inédite en boucle ouverte, basée sur le processus stochastique de marge de production et des contraintes en probabilité est proposée. Pour les besoins de cette formulation, nous générons des scénarios à l'aide de techniques plus réalistes qu'en exploitation. Enfin, une résolution moins anticipative est étudiée en appliquant l'heuristique «Programmation Stochastique avec Règles de Décision Constantes par Morceaux» introduite par Thénié et Vial. Les premiers résultats sont très encourageants en comparaison avec les modèles en boucle ouverte.

Les travaux présentés dans cette thèse portent sur la conception de systèmes de fabrication en contexte incertain. La conception d'un tel système peut être vue comme un problème d'optimisation qui consiste à trouver une configuration qui permet d'optimiser certains objectifs tout en respectant des contraintes technologiques et économiques connues. Les systèmes de fabrication étudiés dans ce mémoire sont des lignes d'assemblage et d'usinage. La première est une ligne qui se présente comme une chaîne de postes de travail où, dans chaque poste, les opérations d'assemblage s'exécutent de manière séquentielle. La deuxième, quant à elle, est une ligne particulière qui se compose de machines de transfert comportant plusieurs boîtiers multibroches où les opérations s'exécutent simultanément. Dans un premier temps, nous décrivons de différentes approches permettant de modéliser l'incertitude des données en optimisation. Une attention particulière est portée sur les deux approches suivantes : l'approche robuste et l'analyse de sensibilité. Puis, nous présentons trois applications : la conception d'une ligne d'assemblage et d'une ligne d'usinage soumises aux variations de temps opératoires et la conception d'une ligne d'assemblage avec les temps opératoires connus sous la forme d'intervalles des valeurs possibles. Pour chaque application, nous identifions les performances attendues ainsi que la complexité de la prise en compte de l'incertitude. Ensuite, nous proposons de nouveaux critères d'optimisation en adéquation avec la problématique introduite. Enfin des méthodes de résolution sont développées pour appréhender les différents problèmes mis en évidence par ces critères.

Le travail présenté dans ce mémoire de thèse concerne la gestion de la consommation et de la production d'énergie électrique dans les bâtiments. Le problème de gestion d'énergie est modélisé sous forme de programme linéaire mixte. Le travail présenté dans ce mémoire propose des outils qui permettent de prendre en compte les incertitudes dans l'optimisation des flux d'énergie dans l'habitat. Dans un premier temps les incertitudes à prendre en compte sont étudiées. Nous distinguons 2 types d'incertitudes : les incertitudes paramétriques qui concernent le caractère imprécis des coefficients du modèle (prévisions météorologiques, paramètres des modèles, demande prévisionnelle d'énergie...) et les incertitudes d'occurrence qui sont liées aux actions directes de l'usager sur sa consommation d'énergie. Une approche d'optimisation robuste s'appuyant sur une formulation présentée par Bertsimas et Sim pour la programmation linéaire robuste est proposée pour prendre en compte les incertitudes paramétriques. Une procédure d'optimisation en deux étapes, basée sur la programmation stochastique, est proposée pour anticiper les possibilités de démarrage des services pilotés par l'usager. Cette procédure apporte une réponse aux incertitudes d'occurrence en permettant de prendre en compte les consommations d'énergie qui ne sont pas pilotées par le système d'optimisation. Différents exemples d'appartements sont utilisés pour illustrer la validité des méthodes proposées. Différents scénarios de tarification de l'énergie sont également étudiés.

Dans cette thèse, nous nous intéressons à des chaînes logistiques dont les acteurs de la chaîne sont des entités décisionnelles indépendantes. Plus précisément, notre cadre d’étude sera un "maillon" d’une chaîne logistique (relation client fournisseur) dont les acteurs (le client et le fournisseur) sont des entités décisionnelles indépendantes qui souhaitent mettre en place des processus de planification coopératifs en présence d’incertitude, sachant que le client fabriques des produits à la commande et le fournisseur sur stock. Dans ce contexte, la contribution majeure visée par nos travaux est l’intégration des connaissances imparfaites sur les données (date du besoin en composants, quantité nécessaire…etc.) afin de calculer le plan d’approvisionnement plus robuste (plan minimisant l’impact de l’incertitude). L’intégration des imperfections repose sur l’utilisation de la théorie des possibilités. Une fois le modèle de représentation des données imparfaites réalisé, nous proposons des méthodes de calcul de plan d’approvisionnement utilisant les informations supplémentaires grâce à la représentation des imperfections. / In this thesis, we focus on supply chain where the actors are independent entities. More precisely, ours interests are on point-to-point (customer/supplier) relationships where the actors (the customer and the supplier) are independent entities which want to set up collaborative planning process under uncertainty, such that the customer produces to orders and the supplier produces to stock. In this context, the major contribution of the thesis is the integration of ill-known data (date of requirement, required quantities ...etc.) to calculate a robust procurement plan (plan which minimize the impact of uncertainty). We used the possibility theory to model those uncertainties. After the model of ill-known data proposed, we present a set of methods to compute a procurement plan using the additional information (information on the uncertainty).