Submitted by Jesiel Ferreira Gomes (jesielgomes@ufcg.edu.br) on 2018-04-20T20:05:55Z No. of bitstreams: 1 Paulo Aliberto Barros PUCU – TESE (PPGEQ) 2015.pdf: 1544520 bytes, checksum: 9f0c94dbee5a50446ebe3c2ab8e538a5 (MD5) / Made available in DSpace on 2018-04-20T20:05:55Z (GMT). No. of bitstreams: 1 Paulo Aliberto Barros PUCU – TESE (PPGEQ) 2015.pdf: 1544520 bytes, checksum: 9f0c94dbee5a50446ebe3c2ab8e538a5 (MD5) Previous issue date: 2015-02-24 / O Brasil possui atualmente 115 plataformas de petróleo, sendo 79 fixas e 34 flutuantes, com capacidade de produção de 2,1 milhões de barris diários de petróleo. Diante desta produção torna-se necessária uma estratégia eficiente para a distribuição deste petróleo para as refinarias, onde será processado e refinado. O petróleo proveniente das plataformas é transportado para as refinarias através de navios ou dutos, sendo que grande parte do custo operacional de produção é devido ao seu transporte. Por este motivo a minimização do custo de transporte é extremamente importante. Este trabalho tem por objetivo, utilizando a técnica de programação matemática (Programação Linear Inteira Mista – PLIM), reduzir os custos decorrentes do sistema de transporte. O modelo consiste em uma frota heterogênea de navios, os quais apresentam compartimentos que só podem ser ocupados por um único tipo de produto em cada viagem. Inicialmente são geradas todas as possíveis rotas e, posteriormente, selecionados os navios, associados às respectivas rotas, de forma a atender as demandas das refinarias e a necessidade de retirada de petróleo dos tanques de armazenamento das plataformas. Para a implementação do modelo foi utilizado o software GAMS (General Algebraic Modeling System), juntamente com os solveres de otimização CPLEX e BONMIN. / Currently, Brazil has 115 petroleum platforms, been 79 fixed and 34 floating, with daily production capacity of 2.1 million barrels of oil. Given this production is necessary a strategy for the efficient distribution of oil to refineries, where it will be processed and refined. Oil from the platforms is transported to refineries through pipelines or ships, with much of the operational cost of production is due to transport. For this reason the minimization of the cost of transport is extremely important. This work has for objective, using the technique of mathematical programming (linear mixed integer programming - LMIP), reduce costs arising from transport system. The model consists of a heterogeneous fleet of ships, which have compartments that can only be occupied by a single type of product on each trip. Initially are generated all possible routes and then selected the vessels, associated with their routes in order to attend the demand of refineries and the need for removal of oil in the storage tanks of the platforms. For the implementation of the model was used the software GAMS (General Algebraic Modeling System), together with the solveres of CPLEX and BONMIN optimization. The results were satisfactory.

Orientador: Marcos Julio Rider Flores / Resumo: Os problemas de planejamento da expansão de sistemas de transmissão e de fluxo de potência ótimo são de grande importância na área de sistemas de transmissão de energia elétrica. O primeiro consiste em determinar a expansão ótima do sistema, que deve ocorrer com o menor gasto monetário possível. No problema fluxo de potência ótimo deve-se encontrar o estado de operação do sistema de forma a minimizar um objetivo, no caso, os custos de geração. Ambos problemas possuem modelos de programação não-linear inteira mista. Além disto, o resultado ótimo de ambos deve cumprir com restrições operacionais, como o limite de tensão nas barras, os limites de fluxos nos ramos e os limites dos geradores. Para resolver os problemas citados, neste trabalho são apresentados modelos matemáticos de programação linear inteiro misto, aproximados, baseados em um modelo linearizado de fluxo de carga AC, que considera a presença da potência reativa, das perdas no sistema e magnitudes de tensões nas barras diferentes do valor nominal. Todos os modelos foram escritos na linguagem de modelagem matemática AMPL e resolvidos com o solver comercial CPLEX. Os modelos propostos foram testados com os sistemas IEEE de 14, 30, 57, 118 e 300 barras e com o sistema Garver para o planejamento da expansão de sistemas de transmissão. Os resultados foram comparados utilizando-se um fluxo de carga não linear, para verificar-se a precisão dos modelos propostos. / Abstract: The transmission network expansion planning and the optimal power flow problems are of great importance in the field of electricity transmission systems. The first consists in determining the optimal expansion of the system, which must be done with the least possible investment. In the optimal power flow problem it must found the operating status of the system in order to minimize an objective, in this case, generation costs. Both problems have mixed-integer nonlinear programming models. In addition, the optimal solution of both must comply with operating constraints, such as the voltage limit on buses, the limits flows in branches and the limits of the generators. To solve the problems cited, in this work are presented approximate mixed integer linear programming models based on a linearized AC load flow model, which considers the presence of reactive power, the losses in the system and of nominal bus voltage magnitudes. All models were written in mathematical modeling language AMPL and solved with the commercial solver CPLEX. The proposed models were tested with the IEEE systems of 14, 30, 57, 118 and 300 buses and with the Garver system for transmission network expansion planning. Results were compared using a nonlinear load flow model, to verify the accuracy of the proposed models. / Mestre

Submitted by CARLOS FRANCISCO SABILLON ANTUNEZ (cfsa27@gmail.com) on 2018-05-23T00:13:45Z No. of bitstreams: 1 20180522ATeseCarlos.pdf: 6005665 bytes, checksum: cc46f4ea50bb15771fa5c7f3ce3f8107 (MD5) / Approved for entry into archive by Cristina Alexandra de Godoy null (cristina@adm.feis.unesp.br) on 2018-05-24T14:51:28Z (GMT) No. of bitstreams: 1 sabillonantunez_cf_dr_ilha.pdf: 6416516 bytes, checksum: 8832a0c7772aecb5081e9daa768de603 (MD5) / Made available in DSpace on 2018-05-24T14:51:28Z (GMT). No. of bitstreams: 1 sabillonantunez_cf_dr_ilha.pdf: 6416516 bytes, checksum: 8832a0c7772aecb5081e9daa768de603 (MD5) Previous issue date: 2018-03-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / As redes de distribuição de energia elétrica devem estar preparadas para fornecer um serviço econômico e confiável a todos os clientes, bem como para integrar tecnologias relacionadas à geração distribuída, armazenamento de energia e veículos elétricos. Uma representação adequada da operação das redes de distribuição, considerando as tecnologias de redes inteligentes, é fundamental para atingir esses objetivos. Este trabalho apresenta formulações matemáticas para a operação em regime permanente das redes de distribuição, que consideram o desequilíbrio de redes trifásicas. Modelos matemáticos da operação de dispositivos relacionados à redes inteligentes presentes em redes de distribuição são desenvolvidos (e.g., dispositivos de controle volt-var, sistemas de armazenamento de energia e veículos elétricos). Além disso, características relacionadas à dependência da tensão das cargas, geração distribuída e limites térmico e de tensão também estão incluídos. Essas formulações constituem um marco matemático para a análise de otimização da operação das redes de distribuição de energia elétrica, o que possibilita modelar os processos de tomada de decisões. Objetivos diferentes relacionados a aspectos técnicos e/ou econômicos podem ser almejados dentro deste marco; Além disso, a extensão para otimização multi-período e multi-cenário é discutida. Os modelos apresentados são construídos com base em formulações de programação linear inteira mista, evitando o uso de formulações não-lineares inteiras mistas convencionais. A aplicação do marco apresentado é ilustrada em abordagens de controle para coordenação de carregamento de veículos elétricos, controle de magnitude de tensão e controle de geração distribuída renovável. Diversos métodos são desenvolvidos, com base no marco de otimização matemática, para otimizar a operação de sistemas de distribuição desbalanceados, considerando não apenas diferentes penetrações de veículos elétricos e fontes de energia renováveis, mas também a presença de sistemas de armazenamento e dispositivos de controle volt-var. A este respeito, o agendamento dinâmico e a otimização multi-período de janela rolante são frequentemente usados para alcançar uma operação ótima na rede. A eficácia e robustez das metodologias, bem como a confiabilidade do marco de otimização matemática, são verificados usando vários sistemas de teste (e.g., 123-node, 34-node e 178-node) com nós de média e baixa tensão, diferentes janelas de controle e várias disponibilidades de controle relacionadas aos dispositivos de rede inteligente. / Electric distribution networks should be prepared to provide an economic and reliable service to all customers, as well as to integrate technologies related to distributed generation, energy storage, and plug-in electric vehicles. A proper representation of the electric distribution network operation, taking into account smart grid technologies, is key to accomplish these goals. This work presents mathematical formulations for the steady-state operation of electric distribution networks, which consider the unbalance of three-phase grids. Mathematical models of the operation of smart grid-related devices present in electric distribution networks are developed (e.g., volt-var control devices, energy storage systems, and plug-in electric vehicles). Furthermore, features related to the voltage dependency of loads, distributed generation, and voltage and thermal limits are also included. These formulations constitute a mathematical framework for optimization analysis of the electric distribution network operation, which could assist planners in decision-making processes. Different objectives related to technical and/or economic aspects can be pursued within the framework; in addition, the extension to multi-period and multi-scenario optimization is discussed. The presented models are built based on mixed integer linear programming formulations, avoiding the use of conventional mixed integer nonlinear formulations. The application of the presented framework is illustrated throughout control approaches for plug-in electric vehicle charging coordination, voltage magnitude control, and renewable distributed generation control. Several methods are developed, based on this framework, to optimize the operation of unbalanced distribution systems considering not only different penetrations of electric vehicles and renewable energy sources but also the presence of storage systems and volt-var control devices. In this regard, dynamic scheduling and rolling multi-period optimization are often used to achieve optimal economic operation in the grid. The effective and robustness of the methodologies, as well as the reliability of the mathematical framework, are verified using many test systems (e.g., 123-node, 34-node, and 178-node) with medium and low voltage nodes, different operation control time frames, and several control availabilities related to the smart grid devices.

Dans cette thèse, nous avons examiné différentes possibilités d'intégration des décisions d'ordonnancement avec des informations provenant de systèmes avancés des contrôles des procédés dans la fabrication de semi-conducteurs. Nous avons développé des idées d'intégration et défini des nouveaux problèmes d'ordonnancement originales : Problème d'ordonnancement avec des contraintes de temps (PTC) et problème d'ordonnancement avec l'état de santé des équipement (PEHF). PTC et PEHF ont des fonctions objectives multicritères.PTC est un problème d'ordonnancement des familles de jobs sur des machines parallèles non identiques en tenant compte des temps de setup et des contraintes de temps. Les machines non identiques signifient que toutes les machines ne peuvent pas traités (qualifiés) tous les types de familles d'emplois. Les contraintes de temps nommés aussi Thresholds sont inspirées des besoins de l'APC. Elle est liée à l'alimentation régulière des boucles de contrôle de l'APC. L'objectif est de minimiser la somme des dates de fin et les pertes de qualification des machines lorsqu'une famille de jobs n'est pas ordonnancée sur la machine donnée avant un seuil de temps donné.D'autre part, PEHF est une extension de PTC. Il consiste d'intégrer les indices de santé des équipements (EHF). EHF est un indicateur associé à l'équipement qui donne l'état de la. L'objectif est d'ordonnancer des tâches de familles de jobs différents sur les machines tout en minimisant la somme des temps d'achèvement, les pertes de qualification de la machine et d'optimiser un rendement attendu. Ce rendement est défini comme une fonction d'EDH et de la criticité de jobs considérés. / In this thesis, we discussed various possibilities of integrating scheduling decisions with information and constraints from Advanced Process Control (APC) systems in semiconductor Manufacturing. In this context, important questions were opened regarding the benefits of integrating scheduling and APC. An overview on processes, scheduling and Advanced Process Control in semiconductor manufacturing was done, where a description of semiconductor manufacturing processes is given. Two of the proposed problems that result from integrating bith systems were studied and analyzed, they are :Problem of Scheduling with Time Constraints (PTC) and Problem of Scheduling with Equipement health Factor (PEHF). PTC and PEHF have multicriteria objective functions.PTC aims at scheduling job in families on non-identical parallel machines with setup times and time constraints.Non-identical machines mean that not all miachines can (are qualified to) process all types of job families. Time constraints are inspired from APC needs, for which APC control loops must be regularly fed with information from metrology operations (inspection) within a time interval (threshold). The objective is to schedule job families on machines while minimizing the sum of completion times and the losses in machine qualifications.Moreover, PEHF was defined which is an extension of PTC where scheduling takes into account the equipement Health Factors (EHF). EHF is an indicator on the state of a machine. Scheduling is now done by considering a yield resulting from an assignment of a job to a machine and this yield is defined as a function of machine state and job state.

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-06-21T21:21:46Z No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2017-06-29T18:27:23Z (GMT) No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-06-29T18:27:23Z (GMT). No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-02-22 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / In this work we applied an algorithm based on the resolution of integer linear models for the problem of packing boxes into a single container considering the cargo stability constraint. The problem consists of arranging items (boxes) of different sizes inside a large object (container) to maximize the occupied container volume while respecting the imposed constraints. Four methods are investigated and compared due to vertical cargo stability, in which three of these methods are proposed in this work and based on the equilibrium of rigid bodies, and the other one is based on the factor of support of boxes bottom faces. In the case of the factor of support, a set of constraints can be inserted totally in the integer formulation, while in the other methods cutting planes are inserted during optimization of the formulation by a branch-and-cut algorithm. Computational tests on instances from the literature show that the usage of a factor of support underestimates the value of the optimal solution. The computational tests showed that the use of the factor of support may underestimate the solution, but its use with integer linear programming models has the advantage that feasible solutions are stable, while the other developed methods only verify stability and thus they depend of the integer linear program to return feasible solutions more quickly. By the way, the methods for the cargo stability developed here also overcame the factor of support for tests involving different types of mesh to pack into the container. / Aplica-se um algoritmo baseado na resolução de modelos de programação linear inteira para o problema de carregamento de caixas dentro de um único contêiner considerando a restrição de estabilidade de carga. O problema em estudo consiste em arranjar itens (caixas) de diferentes tamanhos dentro de um objeto maior (contêiner), de maneira maximizar a ocupação do volume do contêiner enquanto respeita as restrições dadas. Quatro métodos são investigados e comparados quanto a estabilidade vertical do empacotamento, sendo que três deles são desenvolvidos neste trabalho e baseados em conceitos do equilíbrio de corpos rígidos, enquanto um deles é baseado no fator de suporte da base das caixas. No caso do fator de suporte, um conjunto de restrições pode ser inserido totalmente dentro da formulação inteira, enquanto nos demais métodos planos de corte são inseridos durante a resolução da formulação por um algoritmo branch-and-cut. Os testes computacionais mostraram que o uso do fator de suporte pode subestimar a solução, porém seu uso com modelos de programação linear inteira tem a vantagem das soluções viáveis poderem ser estáveis, enquanto os demais métodos desenvolvidos apenas verificam a estabilidade e, assim, dependem do programa linear inteiro retornar soluções viáveis mais rapidamente. Os métodos para a estabilidade de carga desenvolvidos neste trabalho mostraram-se superiores ao fator de suporte para testes envolvendo diferentes tipos de malhas para o empacotamento no contêiner.

Le problème de dimensionnement et planification d'agents en centre d'appels consiste à déterminer sur une période le nombre d'interlocuteurs requis afin d'atteindre la qualité de service exigée et minimiser les coûts induits. Ce sujet fait l'objet d'un intérêt croissant pour son intérêt théorique mais aussi pour l'impact applicatif qu'il peut avoir. Le but de cette thèse est d'établir des approches en contraintes en probabilités en considérant l'incertitude de la demande.Tout d'abord, la thèse présente un modèle en problème d'optimisation stochastique avec contrainte en probabilité jointe traitant la problématique complète en une étape afin d'obtenir un programme facile à résoudre. Une approche basée sur l'idée de continuité est proposée grâce à des lois de probabilité continues, une nouvelle relation entre les taux d'arrivées et les besoins théoriques et la linéarisation de contraintes. La répartition du risque global est faite pendant le processus d'optimisation, permettant une solution au coût réduit. Ces solutions résultantes respectent le niveau de risque tout en diminuant le coût par rapport à d'autres approches.De plus, le modèle en une étape est étendu pour améliorer sa représentation de la réalité. D'une part, le modèle de file d'attente est amélioré et inclus la patience limitée des clients. D'autre part, une nouvelle expression de l'incertitude est proposée pour prendre la dépendance des périodes en compte.Enfin, une nouvelle représentation de l'incertitude est considérée. L'approche distributionally robust permet de modéliser le problème sous l'hypothèse que la loi de probabilité adéquate est inconnue et fait partie d'un ensemble de lois, défini par une moyenne et une variance données. Le problème est modélisé par une contrainte en probabilité jointe. Le risque à chaque période est définie par une variable à optimiser.Un problème déterministe équivalent est proposé et des approximations linéaires permettent d'obtenir une formulation d'optimisation linéaire. / The staffing and shift-scheduling problems in call centers consist in deciding how many agents handling the calls should be assigned to work during a given period in order to reach the required Quality of Service and minimize the costs. These problems are subject to a growing interest, both for their interesting theoritical formulation and their possible applicative effects. This thesis aims at proposing chance-constrained approaches considering uncertainty on demand forecasts.First, this thesis proposes a model solving the problems in one step through a joint chance-constrained stochastic program, providing a cost-reducing solution. A continuous-based approach leading to an easily-tractable optimization program is formulated with random variables following continuous distributions, a new continuous relation between arrival rates and theoritical real agent numbers and constraint linearizations. The global risk level is dynamically shared among the periods during the optimization process, providing reduced-cost solution. The resulting solutions respect the targeted risk level while reducing the cost compared to other approaches.Moreover, this model is extended so that it provides a better representation of real situations. First, the queuing system model is improved and consider the limited patience of customers. Second, another formulation of uncertainty is proposed so that the period correlation is considered.Finally, another uncertainty representation is proposed. The distributionally robust approach provides a formulation while assuming that the correct probability distribution is unknown and belongs to a set of possible distributions defined by given mean and variance. The problem is formulated with a joint chance constraint. The risk at each period is a decision variable to be optimized. A deterministic equivalent problem is proposed. An easily-tractable mixed-integer linear formulation is obtained through piecewise linearizations.

Worst Case Execution Time (WCET) is an important metric for programs running on real-time systems, and finding precise estimates of a program’s WCET is crucial to avoid over-allocation and wastage of hardware resources and to improve the schedulability of task sets. Hardware Caches have a major impact on a program’s execution time, and accurate estimation of a program’s cache behavior generally leads to significant reduction of its estimated WCET. However, the cache behavior of an access cannot be determined in isolation, since it depends on the access history, and in multi-path programs, the sequence of accesses made to the cache is not fixed. Hence, the same access can exhibit different cache behavior in different execution instances. This issue is further exacerbated in shared caches in a multi-core architecture, where interfering accesses from co-running programs on other cores can arrive at any time and modify the cache state. Further, cache analysis aimed towards WCET estimation should be provably safe, in that the estimated WCET should always exceed the actual execution time across all execution instances. Faced with such contradicting requirements, previous approaches to cache analysis try to find memory accesses in a program which are guaranteed to hit the cache, irrespective of the program input, or the interferences from other co-running programs in case of a shared cache. To do so, they find the worst-case cache behavior for every individual memory access, analyzing the program (and interferences to a shared cache) to find whether there are execution instances where an access can super a cache miss. However, this approach loses out in making more precise predictions of private cache behavior which can be safely used for WCET estimation, and is significantly imprecise for shared cache analysis, where it is often impossible to guarantee that an access always hits the cache. In this work, we take a fundamentally different approach to cache analysis, by (1) trying to find worst-case behavior of groups of cache accesses, and (2) trying to find the exact cache behavior in the worst-case program execution instance, which is the execution instance with the maximum execution time. For shared caches, we propose the Worst Case Interference Placement (WCIP) technique, which finds the worst-case timing of interfering accesses that would cause the maximum number of cache misses on the worst case execution path of the program. We first use Integer Linear Programming (ILP) to find an exact solution to the WCIP problem. However, this approach does not scale well for large programs, and so we investigate the WCIP problem in detail and prove that it is NP-Hard. In the process, we discover that the source of hardness of the WCIP problem lies in finding the worst case execution path which would exhibit the maximum execution time in the presence of interferences. We use this observation to propose an approximate algorithm for performing WCIP, which bypasses the hard problem of finding the worst case execution path by simply assuming that all cache accesses made by the program occur on a single path. This allows us to use a simple greedy algorithm to distribute the interfering accesses by choosing those cache accesses which could be most affected by interferences. The greedy algorithm also guarantees that the increase in WCET due to interferences is linear in the number of interferences. Experimentally, we show that WCIP provides substantial precision improvement in the final WCET over previous approaches to shared cache analysis, and the approximate algorithm almost matches the precision of the ILP-based approach, while being considerably faster. For private caches, we discover multiple scenarios where hit-miss predictions made by traditional Abstract Interpretation-based approaches are not sufficient to fully capture cache behavior for WCET estimation. We introduce the concept of cache miss paths, which are abstractions of program path along which an access can super a cache miss. We propose an ILP-based approach which uses cache miss paths to find the exact cache behavior in the worst-case execution instance of the program. However, the ILP-based approach needs information about the worst-case execution path to predict the cache behavior, and hence it is difficult to integrate it with other micro-architectural analysis. We then show that most of the precision improvement of the ILP-based approach can be recovered without any knowledge of the worst-case execution path, by a careful analysis of the cache miss paths themselves. In particular, we can use cache miss paths to find the worst-case behavior of groups of cache accesses. Further, we can find upper bounds on the maximum number of times that cache accesses inside loops can exhibit worst-case behavior. This results in a scalable, precise method for performing private cache analysis which can be easily integrated with other micro-architectural analysis.

Les problèmes d’ordonnancement de rendez-vous en tête-à-tête sont des problèmes dans lesquels des personnes souhaitent se rencontrer par deux lors de courts rendez-vous qui se déroulent lors d’une session unique. Dans cette thèse, nous référençons plusieurs applications de ce type de problèmes et proposons des notations qui généralisent les notations standards de problèmes d’ordonnancement α|β|γ. Nous nous intéressons en particulier à un cas dans lequel deux populations distinctes se rencontrent, des participants peuvent arriver en retard et des rencontres sont interdites. L’objectif est de minimiser le nombre maximal d’attentes des participants. Nous étudions dans un premier temps la complexité de ces problèmes : nous démontrons que plusieurs cas sans rencontre interdite sont polynomiaux et que le cas général est NP-complet au sens fort. Nous proposons ensuite des bornes inférieures. Puis nous développons plusieurs méthodes de résolution. Des modèles de programmation linéaire en nombres entiers et un modèle de programmation par contraintes sont tout d’abord proposés. Des règles de dominance permettant de limiter les symétries sont intégrées à ces modèles dans le but de limiter l’espace des solutions. Enfin, nous proposons une recherche à divergence limitée (limited discrepancy search) qui est une méthode approchée basée sur l’exploration d’un arbre de recherche tronqué. Dans cette méthode, nous exploitons le plus possible les propriétés de symétrie du problème pour faciliter la convergence vers une bonne solution. Toutes ces méthodes sont testées et comparées sur un ensemble de 300 instances générées aléatoirement d’après des paramètres réalistes. / One-to-one meeting scheduling problems are problems where a population of actors want to meet each other during short time slots that take place in a single session. In this thesis, we reference several applications of this type of problems found in the literature and introduce a notation extending the well-known scheduling notation α|β|γ. We are particularly interested in a case in which two distinct populations meet, participants may arrive late and some meetings are forbidden. The objective is to minimize the maximum number of participants waiting slots. First, we study the complexity of these problems: we show that several cases with no forbidden meeting are polynomial and that the general case is NP-complete in the strong sense. We then propose lower bounds. After that, we develop several resolution methods. Integer linear programming models and a constraint programming model are developed. To limit the solution space, we add dominance rules based on symmetries to these methods. Finally, we present a limited discrepancy search (i.e. an approximate method based on the exploration of a truncated tree search). In this method, we use as much as possible the symmetry properties of the problem to facilitate the convergence to a good solution. All these methods are tested and compared on a set of 300 randomly generated instances from realistic parameters.

This thesis deals with application of optimisation methods based on linear and mixed-integer linear programming to various problems in the power sector related to electricity production. The thesis goal is to test the applicability of such methods to formulating and solving various instances from the class of real-world electricity production problems, and to find the advantages and disadvantages associated with using these methods. Introductory chapters describe the main characteristics of power markets, including the historical and regulatory context. Fundamental properties of power markets on both demand and supply side are also described, both from a real-world and a modelling point of view. Benefits of optimisation and modelling are discussed, in particular the solution feasibility and optimality as well as insights gained from sensitivity analysis which is often difficult to replicate with the original system. In the core of the thesis, optimisation techniques are applied to three case studies, each of which deals with a specific problem arising during electricity production. In the first problem, the profit of gas-fired power plant in Slovakia from selling power on the day-ahead market is maximised. The model is set up using both technical and commercial constraints. The second problem deals with the problem of representing a two-dimensional production function which primarily arises for a hydro generator with large variations in the level of its reservoir. Several representations of the original function using piecewise linear subsets are presented, compared, and characterised by their computational intensity both theoretically and practically. In the third problem, the prices on the German day-ahead market in 2011 are modelled. Contrary to the previous two models, the model does not capture an optimisation problem faced by a single producer, but incorporates a large subset of the whole market instead. Consequently the model is formed out of generic constraints relevant to all power plants whose parameters are estimated. By combining information about the aggregate availability of power plants with the estimated efficiencies a full supply curve for each day is created. Different scenarios are analysed to test the impact of uncertain inputs such as unknown or estimated constraints. The choice of the investigated problems stems from the attempt to cover electricity production problems from the point of view of multiple criteria. The three investigated electricity production problems span a broad range from the decisions of a single power plant to the modelling a power market as a whole. Formulations of the production function with different level of detail are presented ranging from a simple linear relationship to several bivariate function formulations. While each problem answers a specific question, they all illustrate the ease with which various electricity production problems can solved using optimisation methods based on linear and mixed-integer linear programming. This is mainly due to the ability of these methods to approximate even non-linear functions and constraints over non-convex domains and find global solutions in reasonable time. Moreover, models formulated with these methods allow sensitivity and scenario analyses to be carried out easily as is illustrated in each of the case studies.