In this thesis, we study three supply chain planning problems. The first two problems fall in the tactical planning level, while the third one falls in the strategic/tactical level. We present a direct application for the first two planning problems in the wind turbines industry. For the third problem, we show how it can be applied to supply chains in the food industry. Many countries and localities have the explicitly stated goal of increasing the fraction of their electrical power that is generated by wind turbines. This has led to a rapid growth in the manufacturing and installation of wind turbines. The globally installed capacity for the manufacturing of different components of the wind turbine is nearly fully utilized. Because of the large penalties for missing delivery deadlines for wind turbines, the effective planning of its supply chain has a significant impact on the profitability of the turbine manufacturers. Motivated by the planning challenges faced by one of the world’s largest manufacturers of wind turbines, we present a comprehensive tactical supply chain planning model for manufacturing of wind turbines in the first part of this thesis. The model is multi-period, multi-echelon, and multi-commodity. Furthermore, the model explicitly incorporates backorder penalties with a general cost structure, i.e., the cost structure does not have to be linear in function of the backorder delay. To the best of our knowledge, modeling-based supply chain planning has not been applied to wind turbines, nor has a model with all the above mentioned features been described in the literature. Based on real-world data, we present numerical results that show the significant impact of the capability to model backorder penalties with general cost structures on the overall cost of supply chains for wind turbines. With today’s rapidly changing global market place, it is essential to model uncertainty in supply chain planning. In the second part of this thesis, we develop a two-stage stochastic programming model for the comprehensive tactical planning of supply chains under supply uncertainty. In the first stage, procurement decisions are made while in the second stage, production, inventory, and delivery decisions are made. The considered supply uncertainty combines supplier random yields and stochastic lead times, and is thus the most general form of such uncertainty to date. We apply our model to the same wind turbines supply chain. We illustrate theoretical and numerical results that show the impact of supplier uncertainty/unreliability on the optimal procurement decisions. We also quantify the value of modeling uncertainty versus deterministic planning. Supplier selection with quantity discounts has been an active research problem in the operations research community. In this the last part of this thesis, we focus on a new quantity discounts scheme offered by suppliers in some industries. Suppliers are selected for a strategic planning period (e.g., 5 years). Fixed costs associated with suppliers’ selection are paid. Orders are placed monthly from any of the chosen suppliers, but the quantity discounts are based on the aggregated annual order quantities. We incorporate all this in a multi-period multi-product multi-echelon supply chain planning problem and develop a mixed integer programming (MIP) model for it. Leading commercial MIP solvers take 40 minutes on average to get any feasible solution for realistic instances of our model. With the aim of getting high-quality feasible solutions quickly, we develop an algorithm that constructs a good initial solution and three other iterative algorithms that improve this initial solution and are capable of getting very fast high quality primal solutions. Two of the latter three algorithms are based on MIP-based local search and the third algorithm incorporates a variable neighborhood Descent (VND) combining the first two. We present numerical results for a set of instances based on a real-world supply chain in the food industry and show the efficiency of our customized algorithms. The leading commercial solver CPLEX finds only a very few feasible solutions that have lower total costs than our initial solution within a three hours run time limit. All our iterative algorithms well outperform CPLEX. The VND algorithm has the best average performance. Its average relative gap to the best known feasible solution is within 1% in less than 40 minutes of computing time.

A presente pesquisa teve por objetivo propor uma estrutura de modelagem matemática para a localização ótima de unidades de tratamento térmico de resíduos com recuperação energética. Para tal, o ferramental utilizado foi o método de programação inteira mista, sendo a modelagem desenvolvida aplicada para a Região Metropolitana da Baixada Santista e Litoral Norte. Foi considerada como premissa básica que o processo de incineração seria operado pelo poder público; todos os municípios geradores de Resíduos Sólidos Domiciliares foram considerados como potenciais localidades para a instalação da unidade de tratamento térmico de resíduos; todos os aterros sanitários que atendiam os Municípios estudados foram considerados para a recepção das escórias e cinzas provenientes do processo de incineração. Foram especificados quatro cenários para tal análise, que abordaram competitividade em relação ao uso de aterros sanitários e a presença de eficiência na coleta seletiva dos Municípios. Os resultados apontaram para que a unidade de tratamento térmico de resíduos se localize no entorno dos Municípios de Santos, Praia Grande e São Vicente. Mesmo com a opção do uso de aterros sanitários, a implantação da unidade de tratamento térmico de resíduos se apresentou como uma alternativa mais favorável, tendo sido levados em conta, na modelagem proposta, aspectos tanto ambientais como econômicos. / This study aimed to propose a mathematical modeling framework for optimal location of units of the thermal treatment of waste with energy recovery. To this end, the tool used was the method of mixed integer programming, and the developed modeling applied to the Santos Metropolitan Region and North Coast. It was considered as the basic premise that the incineration process would be operated by the Government; all municipalities solid waste generators were considered as potential locations for the installation of the unit thermal treatment of waste, all landfills that serve municipalities studied were considered for receipt of slag and ash from the incineration process. Four scenarios were specified for this analysis that addressed competitiveness in relation to the use of landfills and the presence of selective collection efficiency in the municipalities. Results showed that the unit of thermal treatment of waste should be located in the vicinity of the cities of Santos, São Vicente and Praia Grande. Even with the option of using landfill, the deployment of the unit of thermal treatment of waste is presented as an alternative more favorable, having been taken into account in the proposed model, both environmental and economic aspects.

Cette thèse présente une méthodologie d’ordonnancement cyclique robuste appliquée à la gestion des conteneurs dans les ports maritimes de taille moyenne. Ces derniers sont sujet constamment à des variations des conditions des terminaux, la visibilité réduite sur des évènements futurs ne permet pas de proposer une planification précise des tâches à accomplir. L’ordonnancement cyclique robuste peut jouer un rôle primordial. Il permettra non seulement de proposer un ordonnancement prédictif pour le transport des conteneurs, mais aussi, il proposera également une planification robuste permettant d’éliminer les perturbations éventuelles en temps réel. Dans ce travail nous utilisons les Véhicules Intelligents Automatisés (AIV) pour transporter les conteneurs et nous modélisons les procédures de transit de ces derniers par des graphes d’évènements P-temporels fortement connexes (PTSCEG). Avant l’arrivée d’un porte conteneur au port, un plan (planning) de transport des conteneurs est proposé en un temps court par la programmation linéaire mixte (MIP). Des algorithmes polynomiaux de calcul de robustesse permettent de calculer sur les différents nœuds du système les marges de robustesse. Une fois le navire à quai, l’ordonnancement cyclique robuste est appliqué. Lorsqu’une perturbation est observée (localisée) dans le système, une comparaison avec la marge de robustesse connue est effectuée. Si cette perturbation est incluse dans la marge de robustesse, l’algorithme robuste est utilisé pour éliminer ces perturbations en quelques cycles. Dans le cas où la perturbation est trop importante, la méthode MIP est utilisée pour calculer un nouvel ordonnancement cyclique en un temps réduit / This PhD thesis is dedicated to propose a robust cyclic scheduling methodology applied to container management of medium sized seaport which faces ever changing terminal conditions and the limited predictability of future events and their timing. The robust cyclic scheduling can be seen not just a predictable scheduling to compute a container transportation schedule, but also a reactive scheduling to eliminate the disturbances in real time. In this work, the automated intelligent vehicles (AIV) are used to transport the containers, and the P-time strongly connected event graph (PTSCEG) is used as a graphical tool to model the container transit procedures. Before the arrival of the container vessel, a cyclic container transit schedule can be given by the mixed integer programming (MIP) method in short time. The robustness margins on the nodes of the system can be computed by robustness algorithms in polynomial computing time. After the stevedoring begins, this robust cyclic schedule is used. When a disturbance is observed in system, it should be compared with the known robustness margin. If the disturbance belongs to the robustness margin, the robustness algorithm is used to eliminate the disturbance in a few cycle times. If not, the MIP method is used to compute a new cyclic schedule in short time

L’objectif de cette thèse porte sur des recherches théoriques et algorithmiques d’optimisation locale et globale via les techniques de programmation DC & DCA, Séparation et Evaluation (SE) ainsi que les techniques de relaxation DC/SDP, pour résoudre plusieurs types de problèmes d’optimisation non convexe (notamment en Optimisation Combinatoire et Optimisation Polynomiale). La thèse comporte quatre parties :La première partie présente les outils fondamentaux et les techniques essentielles en programmation DC & l’Algorithme DC (DCA), ainsi que les techniques de relaxation SDP, et les méthodes de séparation et évaluation (SE).Dans la deuxième partie, nous nous intéressons à la résolution de problèmes de programmation quadratique et linéaire mixte en variables entières. Nous proposons de nouvelles approches locales et globales basées sur DCA, SE et SDP. L’implémentation de logiciel et des simulations numériques sont aussi étudiées.La troisième partie explore des approches de la programmation DC & DCA en les combinant aux techniques SE et SDP pour la résolution locale et globale de programmes polynomiaux. Le programme polynomial avec des fonctions polynomiales homogènes et son application à la gestion de portefeuille avec moments d’ordre supérieur en optimisation financière ont été discutés de manière approfondie dans cette partie.Enfin, nous étudions dans la dernière partie un programme d’optimisation sous contraintes de type matrices semi-définies via nos approches de la programmation DC. Nous nous consacrons à la résolution du problème de réalisabilité des contraintes BMI et QMI en contrôle optimal.L’ensemble de ces travaux a été implémenté avec MATLAB, C/C++ ... nous permettant de confirmer l’utilisation pratique et d’enrichir nos travaux de recherche. / The main objective of this thesis focuses on theoretical and algorithmic researches of local and global optimization techniques to DC programming & DCA with Branch and Bound (B&B) and the DC/SDP relaxation techniques to solve several types of non-convex optimization problems (including Combinatorial Optimization and Polynomial Optimization). This thesis is divided into four parts :We present in the first part some fondamental theorems and essential techniques in DC programming & DC Algorithm (DCA), the SDP Relaxation techniques, as well as the Branch and Bound methods (B&B).In the second part, we are interested in solving mixed integer quadratic and linear programs. We propose new local and global approaches based on DCA, B&B and SDP. The implementation of software and numerical simulations have also been investigated.The third part explores the DC programming approaches & DCA combined with a B&B technique and SDP for locally and globally solving a class of polynomial programming. The polynomial program with homogeneous polynomial functionsand its application to portfolio selection problem involving higher order moments in financial optimization have been deeply studied in this part.Finally, in the last part, we present our research on optimization problems under constraints of semi-definite matrices via our DC programming approaches. This part is dedicated to the resolution of the BMI and QMI feasibility problems in the field of optimal control.All these proposed methods have been implemented with MATLAB, C++ etc., that allowing us to confirm the practical use and enrich our research works.

Basés sur les outils théoriques et algorithmiques de la programmation DC et DCA, les travaux de recherche dans cette thèse portent sur les approches locales et globales pour l'optimisation non convexe et l'optimisation globale en variables mixtes entières. La thèse comporte 5 chapitres. Le premier chapitre présente les fondements de la programmation DC et DCA, et techniques de Séparation et Evaluation (B&B) (utilisant la technique de relaxation DC pour le calcul des bornes inférieures de la valeur optimale) pour l'optimisation globale. Y figure aussi des résultats concernant la pénalisation exacte pour la programmation en variables mixtes entières. Le deuxième chapitre est consacré au développement d'une méthode DCA pour la résolution d'une classe NP-difficile des programmes non convexes non linéaires en variables mixtes entières. Ces problèmes d'optimisation non convexe sont tout d'abord reformulées comme des programmes DC via les techniques de pénalisation en programmation DC de manière que les programmes DC résultants soient efficacement résolus par DCA et B&B bien adaptés. Comme première application en optimisation financière, nous avons modélisé le problème de gestion de portefeuille sous le coût de transaction concave et appliqué DCA et B&B à sa résolution. Dans le chapitre suivant nous étudions la modélisation du problème de minimisation du coût de transaction non convexe discontinu en gestion de portefeuille sous deux formes : la première est un programme DC obtenu en approximant la fonction objectif du problème original par une fonction DC polyèdrale et la deuxième est un programme DC mixte 0-1 équivalent. Et nous présentons DCA, B&B, et l'algorithme combiné DCA-B&B pour leur résolution. Le chapitre 4 étudie la résolution exacte du problème multi-objectif en variables mixtes binaires et présente deux applications concrètes de la méthode proposée. Nous nous intéressons dans le dernier chapitre à ces deux problématiques challenging : le problème de moindres carrés linéaires en variables entières bornées et celui de factorisation en matrices non négatives (Nonnegative Matrix Factorization (NMF)). La méthode NMF est particulièrement importante de par ses nombreuses et diverses applications tandis que les applications importantes du premier se trouvent en télécommunication. Les simulations numériques montrent la robustesse, rapidité (donc scalabilité), performance et la globalité de DCA par rapport aux méthodes existantes. / Based on theoretical and algorithmic tools of DC programming and DCA, the research in this thesis focus on the local and global approaches for non convex optimization and global mixed integer optimization. The thesis consists of 5 chapters. The first chapter presents fundamentals of DC programming and DCA, and techniques of Branch and Bound method (B&B) for global optimization (using the DC relaxation technique for calculating lower bounds of the optimal value). It shall include results concerning the exact penalty technique in mixed integer programming. The second chapter is devoted of a DCA method for solving a class of NP-hard nonconvex nonlinear mixed integer programs. These nonconvex problems are firstly reformulated as DC programs via penalty techniques in DC programming so that the resulting DC programs are effectively solved by DCA and B&B well adapted. As a first application in financial optimization, we modeled the problem pf portfolio selection under concave transaction costs and applied DCA and B&B to its solutions. In the next chapter we study the modeling of the problem of minimization of nonconvex discontinuous transaction costs in portfolio selection in two forms: the first is a DC program obtained by approximating the objective function of the original problem by a DC polyhedral function and the second is an equivalent mixed 0-1 DC program. And we present DCA, B&B algorithm, and a combined DCA-B&B algorithm for their solutions. Chapter 4 studied the exact solution for the multi-objective mixed zero-one linear programming problem and presents two practical applications of proposed method. We are interested int the last chapter two challenging problems: the linear integer least squares problem and the Nonnegative Mattrix Factorization problem (NMF). The NMF method is particularly important because of its many various applications of the first are in telecommunications. The numerical simulations show the robustness, speed (thus scalability), performance, and the globality of DCA in comparison to existent methods.

Dans les chaînes d’approvisionnement, les producteurs font souvent appel à des entreprises de transport pour livrer leurs marchandises. Cela peut entraîner une concurrence entre les transporteurs qui cherchent à maximiser leurs revenus individuels en desservant un produc- teur. Dans ce travail, nous considérons de telles situations où aucun transporteur ne peut garantir la livraison de la source à la destination en raison de son activité dans une région restreinte (par exemple, une province) ou de la flotte de transport disponible (par exemple, uniquement le transport aérien), pour ne citer que quelques exemples. La concurrence est donc liée à l’expansion de la capacité de transport des transporteurs. Le problème décrit ci-dessus motive l’étude du jeu d’expansion de réseau multi-agent joué sur un réseau appartenant à de multiples transporteurs qui choisissent la capacité de leurs arcs. Simultanément, un client cherche à maximiser le flux qui passe par le réseau en décidant de la politique de partage qui récompense chacun des transporteurs. Le but est de déterminer un équilibre de Nash pour le jeu, en d’autres termes, la strategie d’extension de capacité et de partage la plus rationnelle pour les transporteurs et le client, respectivement. Nous rappelons la formulation basée sur les arcs proposée dans la littérature, dont la solution est l’équilibre de Nash avec le plus grand flux, et nous identifions ses limites. Ensuite, nous formalisons le concept de chemin profitable croissant et nous montrons son utilisation pour établir les conditions nécessaires et suffisantes pour qu’un vecteur de stratégies soit un équilibre de Nash. Ceci nous conduit à la nouvelle formulation basée sur le chemin. Enfin, nous proposons un renforcement du modèle basé sur les arcs et une formulation hybride arc- chemin. Nos résultats expérimentaux soutiennent la valeur des nouvelles inégalités valides obtenues à partir de notre caractérisation des équilibres de Nash avec des chemins croissants rentables. Nous concluons ce travail avec les futures directions de recherche pavées par les contributions de cette thèse. / In supply chains, manufacturers often use transportation companies to deliver their goods. This can lead to competition among carriers seeking to maximize their individual revenues by serving a manufacturer. In this work, we consider such situations where no single carrier can guarantee delivery from source to destination due to its operation in a restricted region (e.g., a province) or the available transportation fleet (e.g., only air transportation), to name a few examples. Therefore, competition is linked to the expansion of transportation capacity by carriers. The problem described above motivates the study of the multi-agent network expansion game played over a network owned by multiple transporters who choose their arcs’ capacity. Simultaneously, a customer seeks to maximize the flow that goes through the network by deciding the sharing policy rewarding each of the transporters. The goal is to determine a Nash equilibrium for the game, in simple words, the most rational capacity expansion and sharing policy for the transporters and the customer, respectively. We recap the arc-based formulation proposed in literature, whose solution is the Nash equilibirum with the largest flow, and we identify its limitations. Then, we formalize the concept of profitable increasing path and we show its use to establish necessary and sufficient conditions for a vector of strategies to be a Nash equilibrium. This lead us to the first path-based formulation. Finally, we propose a strengthening for the arc-based model and a hybrid arc-path formulation. Our experimental results support the value of the new valid inequalities obtained from our characterization of Nash equilibria with profitable increasing paths. We conclude this work with the future research directions paved by the contributions of this thesis.

<p>Set-based methods have been leveraged in many engineering applications from robust control and global optimization, to probabilistic planning and estimation. While useful, these methods have most widely been applied to analysis over sets that are convex, due to their ease in both representation and calculation. The representation and analysis of nonconvex sets is inherently complex. When nonconvexity arises in design and control applications, the nonconvex set is often over-approximated by a convex set to provide conservative results. However, the level of conservatism may be large and difficult to quantify, often leading to trivial results and requiring repetitive analysis by the engineer. Nonconvexity is inherent and unavoidable in many applications, such as the analysis of hybrid systems and robust safety constraints. </p> <p>In this dissertation, I present a new nonconvex set representation named the hybrid zonotope. The hybrid zonotope builds upon a combination of recent advances in the compact representation of convex sets in the controls literature with methods leveraged in solving mixed-integer programming problems. It is shown that the hybrid zonotope is equivalent to the union of an exponential number of convex sets while using a linear number of continuous and binary variables in the set’s representation. I provide identities for, and derivations of, the set operations of hybrid zonotopes for linear mappings, Minkowski sums, generalized intersections, halfspace intersections, Cartesian products, unions, complements, point containment, set containment, support functions, and convex enclosures. I also provide methods for redundancy removal and order reduction to improve the compactness and computational efficiency of the represented sets. Therefore proving the hybrid zonotopes expressive power and applicability to many nonconvex set-theoretic methods. Beyond basic set operations, I specifically show how the exact forward and backward reachable sets of linear hybrid systems may be found using identities that are calculated algebraically and scale linearly. Numerical examples show the scalability of the proposed methods and how they may be used to verify the safety and performance of complex systems. These exact methods may also be used to evaluate the level of conservatism of the existing approximate methods provided in the literature.  </p>

In today's competitive environment, the importance of continuous production, quality improvement, and fast delivery has forced production and delivery processes to become highly reliable. Keeping equipment in good condition through maintenance activities can ensure a more reliable system. However, maintenance leads to temporary reduction in capacity that could otherwise be utilized for production. Therefore, the coordination of maintenance and production is important to guarantee good system performance. The central thesis of this dissertation is that integrating maintenance and production decisions increases efficiency by ensuring high quality production, effective resource utilization, and on-time deliveries. Firstly, we study the problem of integrated maintenance and production planning where machines are preventively maintained in the context of a periodic review production system with uncertain yield. Our goal is to provide insight into the optimal maintenance policy, increasing the number of finished products. Specifically, we prove the conditions that guarantee the optimal maintenance policy has a threshold type. Secondly, we address the problem of integrated maintenance planning and production scheduling where machines are correctively maintained in the context of a dynamic aircraft repair shop. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter periods. Our results show that the approach that uses logic-based Benders decomposition to solve the static sub-problems, schedules over longer horizon, and quickly adjusts the schedule increases the utilization of aircraft in the long term. Finally, we tackle the problem of integrated maintenance planning and production scheduling where machines are preventively maintained in the context of a multi-machine production system. Depending on the deterioration process of machines, we design decomposed techniques that deal with the stochastic and combinatorial challenges in different, coupled stages. Our results demonstrate that the integrated approaches decrease the total maintenance and lost production cost, maximizing the on-time deliveries. We also prove sufficient conditions that guarantee the monotonicity of the optimal maintenance policy in both machine state and the number of customer orders. Within these three contexts, this dissertation demonstrates that the integrated maintenance and production decision-making increases the process efficiency to produce high quality products in a timely manner.