In this thesis, two methods are proposed in order to rank units: Target-direction-set value efficiency analysis (TDSVEA) and mixed integer programming (MIP) technique. Besides its ranking ability based on preferences of a decision maker (DM), TDSVEA, which modifies the targeted projection approach of Value Efficiency Analysis (VEA) and Data Envelopment Analysis (DEA), provides important information to analyzer: targets and distances of units from these targets, proposed input allocations in order to project these targets, the lack of harmony between the DM and the manager of the unit etc. In MIP technique, units select weights of the criteria from a feasible weight space in order to outperform maximum number of other units. Units are then ranked according to their outperforming ability. Mixed integer programs in this technique are simplified by domination and weight-domination relations. This simplification procedure is further simplified using transitivity between relations. Both TDSVEA and MIP technique are applied to rank research universities and these rankings are compared to those of other ranking techniques.

This dissertation investigates optimization approaches applied to radiation therapy in cancer treatment. Since cancerous cells are surrounded by critical organs and normal tissues, there is conflicting objectives in the treatment design of providing sufficient radiation dose to tumor region, while avoiding normal healthy cells. In general, the goal of radiation therapy is to conform the spatial distribution of the prescribed dose to the tumor volume while minimizing the dose to the surrounding normal structures. A recent advanced technology, using multi-leaf collimator integrated into linear accelerator, provides much better opportunities to achieve this goal: the radiotherapy based on non-uniform radiation beams intensities is called Intensity-Modulated Radiation Therapy. My dissertation research offers a quadratic mixed integer programming approach to determine optimal beam orientations and beamlets intensity simultaneously. The problems generated from real patient cases are large-scale dense instances due to the physics of dose contributions from beamlets to volume elements. The research highlights computational techniques to improve solution times for these intractable instances. Furthermore, results from this research will provide plans that are clinically acceptable and superior in plan quality, thus directly improve the curity rate and lower the normal tissue complication for cancer patients.

Abstract The removal of overlying waste rock in open pit mines to dumps is conventionally undertaken by draglines or by trucks and shovels, or by a combination of these. Waste rock dumps are the largest remnant structures of open cut mining operations and can absorb a large proportion of the mine operating costs. If the dumps are not properly developed they can be excessively expensive and can become a major safety risk and environmental hazard. There are many examples worldwide where poor design and construction of waste rock dumps have resulted in failures causing considerable loss of life and widespread damage, or have resulted in erosion and seepage that have led to severe environmental pollution. The proper design and scheduling of waste rock dumps and haul routes can significantly reduce costs, minimise the possibility of failures, and avoid harming the environment. This Thesis is limited to the consideration of trucks and shovels for waste rock haulage in open cut mining operations. It describes the development and application of a waste rock dump scheduling model using the Operations Research technique of Mixed-Integer Linear Programming, implemented in the mathematical modelling language AMPL. The model focuses on minimising the haulage cost for each block of waste rock taken from the open pit and placed in the dump. Allowance is made for the selective placement of benign and reactive waste rock, based on an open pit block model that delineates benign and reactive waste rock. The formulation requires input data including the xyz-coordinates of the block model for the open pit, information on whether the waste rock blocks are benign or reactive, the proposed time scheduling of waste rock haulage from the open pit, unit haulage costs, and the geometry of the waste rock dump, including the delineation of the zones that are benign and those that are reactive. The model was successfully tested by using both simple test data and actual mine site data. The application of the model to a simple case confirmed that it produces results that meet the Objective Function in producing an optimal haulage time and cost, and meets the various Constraints imposed. This model for scheduling the removal of waste rock from open cut mining operations with trucks and shovels will require further research and testing and, because the results are generated in a numerical format, there will also be a need to convert them to a graphical format to facilitate their interpretation. Ultimately, it will have the potential to provide a relatively low-cost scheduling tool that meets operators’ economic, safety and environmental goals.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Problems of scheduling on batch processing machines to minimize makespan are widely exploited by academic literature, mainly motivated by reliability testing in the semiconductor industry. These problems consist in grouping jobs as a batch and scheduling the processing in single or parallel machines. The jobs have non-identical processing times and non-identical sizes and the total size of the batch cannot exceed the machine capacity. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs with nonidentical release times can also be considered, and in this case a batch can only be processed after the job with the longest release time in the batch is available. We consider four different problems of scheduling on batch processing machines with non-identical job size and different characteristics: single batch processing machine (1|sj,B|Cmax), single batch processing machine with non-identical job release times (1|rj,sj,B|Cmax), identical parallel batch processing machines (Pm|sj,B|Cmax), and identical parallel batch processing machines with non-identical job release times (Pm|rj,sj,B|Cmax). New mathematical models are proposed with formulations that exploit characteristics of each problem. The mathematical models are solved using CPLEX and the computational results show that the proposed models performed better than other models from literature. The new models for 1|sj,B|Cmax and 1|rj,sj,B|Cmax are compared with previously published meta-heuristics and the results show that the models provide better solutions than meta-heuristics methods with competitive computational times. / Problemas de minimização do makespan no dimensionamento e programação de bateladas em máquinas de processamento são extensamente explorados pela literatura acadêmica, motivados principalmente por testes de confiabilidade na indústria de semicondutores. Estes problemas consistem em agrupar tarefas em bateladas e programar o processamento em uma ou mais máquinas em paralelo. As tarefas possuem tempos de processamento e tamanhos não idênticos e o tamanho total da batelada não pode exceder a capacidade da máquina. Para cada batelada é definido um tempo de processamento que será igual ao maior tempo de processamento das tarefas que foram alocadas a ela. As tarefas podem considerar também tarefas com tempos de liberação não idênticos, neste caso as bateladas só poderão ser processadas depois que a tarefa com o maior tempo de liberação for disponibilizada. Este trabalho aborda quatro diferentes problemas de dimensionamento e programação de bateladas com tarefas de tamanhos não idênticos, que consideram diferentes características: máquina de processamento única (1|sj,B|Cmax), máquina de processamento única e tarefas com tempos de liberação não idênticos (1|rj,sj,B|Cmax), máquinas de processamento paralelas idênticas (Pm|sj,B|Cmax) e máquinas de processamento paralelas idênticas e tarefas com tempos de liberação não idênticos (Pm|rj,sj,B|Cmax). São propostos novos modelos matemáticos com formulações que exploram características de cada problema. Os modelos matemáticos são resolvidos utilizando CPLEX e os resultados computacionais comprovam que os modelos propostos possuem um desempenho melhor do que outros modelos da literatura. Os modelos propostos para 1|sj,B|Cmax e 1|rj,sj,B|Cmax são comparados com meta-heurísticas previamente publicadas e os resultados mostram que os novos modelos oferecem soluções melhores com tempos computacionais competitivos.

Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2228.pdf: 979050 bytes, checksum: ffa6f96c8eada124b6f1e6ba3ebe02da (MD5) Previous issue date: 2008-12-11 / Financiadora de Estudos e Projetos / Cutting and packing problems are important in the production planning of various industrial segments involving goals such as minimizing the negative efects generated by waste of materials or idle spaces. The loss of material due to an inadequate programming of the cutting or packing patterns, can be substantial, and, in general, parts of these losses can be avoided only with a more eficient production planning, not resulting in additional investments in production processes. This study aimed at evaluating the performance of the Benders decomposition method, applied to the manufacturer and distributor pallet loading models. The manufacturer pallet loading model involves packing equal boxes on a pallet, so as to optimize its use. The distributor pallet loading model involves packing boxes of diferent sizes on a pallet, also a way to optimize its use. The approach based on Benders decomposition, defines a relaxation algorithm that partitions the original problem in two other problems easier to be solved. To check the effectiveness of the approach, computational tests were carried out by comparing the results with those obtained by a computational package composed of a modeling language (GAMS) and a last generation optimization solver (CPLEX ). / Os problemas de corte e empacotamento são importantes no planejamento da produção de vários segmentos industriais envolvendo objetivos como, por exemplo, minimizar os efeitos negativos gerados por desperdício de materiais ou espaços ociosos. As perdas de material, devido a uma programação pouco adequada dos padrões de corte ou empacotamento, podem ser substanciais, sendo que, em geral, parte destas perdas pode ser evitada apenas com uma programação da produção mais eficiente, não implicando em investimentos adicionais nos processos de produção. O objetivo deste estudo é verificar o desempenho do método de decomposição de Benders aplicado a modelos de carregamento de paletes do produtor e do distribuidor. O problema de carregamento de paletes do produtor envolve empacotar caixas iguais sobre um palete, de maneira a otimizar o aproveitamento deste. O problema de carregamento de paletes do distribuidor envolve empacotar caixas de tamanhos diferentes sobre um palete, também de maneira a otimizar o aproveitamento deste. A abordagem baseada na reformulação de Benders define um algoritmo de relaxação que particiona o problema original em dois outros problemas mais simples de serem resolvidos. Para verificar a eficiência da abordagem, realizaram-se testes computacionais, comparando os resultados obtidos com os obtidos pelo pacote computacional composto de uma linguagem de modelagem (GAMS) e um software de otimização de última geração (CPLEX).

As decisões operacionais de produção em uma indústria de fiação são planejadas na prática determinando soluções dos sub-problemas de dimensionamento e sequenciamento de lotes e da mistura de fardos de algodão. As tarefas são: definir o tamanho, a sequência, o tempo e alocação de cada lote de produção e quais fardos de algodão devem ser utilizados na produção. Por si só, os sub-problemas representam grandes desafios no planejamento da produção. Entretanto, para melhor representar o ambiente produtivo e alcançar custos de produção mais baixos, indústrias de processo, como as de fiação, procuram integrar mais e mais seus sub-problemas de planejamento. O objetivo dessa tese é apresentar modelos matemáticos e métodos de solução para auxiliar a tomada de decisão no nível operacional do planejamento da produção. Três formulações matemáticas para o dimensionamento e sequenciamento de lotes em um sistema de dois estágios com produção sincronizada são propostas. Um novo método baseado em programação matemática e metaheurísticas e também desenvolvida para a solucão desse sub-problema. Além disso, a integração das decisões relativas a matéria-prima (fardos de algodão) ao dimensionamento e sequenciamento de lotes é analisada. As novas formulações propostas representam de forma mais realista o problema de dimensionamento e sequenciamento de lotes da indústria de fiação e de indústrias de processo com ambiente produtivo similares. O método de solução encontra boas soluções para o problema e supera outros méodos similares presentes em softwares comerciais. Além disso, o método é geral o suficiente para a solução de outros problemas de otimização. O problema integrado de dimensionamento e sequenciamento de lotes e mistura comprovou que restrições relativas à qualidade dos fios influenciam os custos e viabilidade do planejamento da produção. O planejamento integrado dessas óperações trata o sistema considerando restrições que se relacionam, definindo planos de produção mais realistas / In the practice of a spinning industry, the operational decisions of the production planning are determined by the hierarchical solution of the lot-sizing and scheduling problem and the blending problem of the cotton bales. The tasks are: to define the size, sequence, timing and allocation of each production lot and to select which cotton bales are used for production. Each of these problems represents a large challenge in planning the production. However, in order to better represent the production environment and to reach lower production costs, process industries (as the spinning industry) are integrating more and more of the production sub-problems into the planning. The aim of this thesis is to propose novel mathematical models and solution methods to assist the decision maker to plan the production at the operational level. Three formulations for the synchronized two-stage lot sizing and scheduling are proposed. A new method based on mathematical programming and metaheuristics is also developed to solve this sub-problem. In addition, the integration of the lot sizing and scheduling with decisions related to the raw materials (cotton bales) is analyzed. The novel models represent a more realistic lot sizing and scheduling for the spinning industry and process industries of similar production environment. The solution method finds good solutions to the mentioned problem and outperforms other state-of-the-art methods incorporated in commercial softwares. Moreover, the method is general enough to solve other optimization problems. The integrated lot-sizing, scheduling and blending prove that constraints related to the yarn quality influence the costs and the feasibility of the production planning. The integrated planning of these operations approaches the system considering the constraint relationship and defines more realistic production plans

In this dissertation, we introduce and study robust optimization models and decomposition algorithms in order to deal with the uncertainties such as terrorist attacks, natural disasters, and uncertain demand that are becoming more and more signicant in power systems operation and planning. An optimal power grid hardening problem is presented as a defender-attacker-defender (DAD) sequential game and solved by an exact decomposition algorithm. Network topology control, which is an eective corrective measure in power systems, is then incorporated into the defender-attacker-defender model as a recourse operation for the power system operator after a terrorist attack. Computational results validate the cost-eectiveness of the novel model. In addition, a resilient distribution network planning problem (RDNP) is proposed in order to coordinate the hardening and distributed generation resource placement with the objective of minimizing the distribution system damage under uncertain natural disaster events. A multi-stage and multi-zone based uncertainty set is designed to capture the spatial and temporal dynamics of a natural disaster as an extension to the N-K worst-case network interdiction approach. Finally, a power market day-ahead generation scheduling problem, i.e., robust unit commitment (RUC) problem, that takes account of uncertain demand is analyzed. Improvements have been made in achieving a fast

Le moteur de traction ferroviaire est destiné à fonctionner dans de larges gammes de couple/vitesse. L'objectif principal de cette thèse est de développer des méthodes de conception par optimisation de machines électriques pour la traction ferroviaire avec la prise en compte des cycles (missions). Puis, d'incorporer ces méthodes dans un outil informatique. Après une prise en main des modèles électromagnétiques existants et leur transfert dans le langage Matlab, des modèles thermiques transitoires ont été établis et validés par rapport aux mesures expérimentales. À partir de là, la problématique des temps de simulations prohibitifs sur cycles a été mise en évidence et des solutions de réduction de cycles ont été proposées et validées sur les différents types de cycle. Enfin, une approche de conception par optimisation en deux niveaux a été développée. Le premier niveau concerne les variables continues et le second gère les variables discrètes. / The rail traction motor is designed to operate in wide range of torque/speed performance. The main aims of this thesis is to develop methods of designing by optimization electric machines over railway driving cycle. Then, to implement these methods in a usable software. Firstly, existing electromagnetic models were transferred to Matlab and two thermal models were developed and validated by experimental measurements. The use of accurate models for the optimization over à driving cycle is highly time consuming so, after identification of this constraint, some solutions to reduce this time without losing the accuracy were proposed and validated. Finally, multi-level optimization approach has been developed for electric machine design to solve mixed integer problem. This approach takes into account the driving cycle by using the methods of cycle reduction developed during this thesis.

O processo de escolha de portfólios é um problema clássico da área financeira. Neste problema, o investidor busca aplicar seu dinheiro em um mercado de ações de forma a obter um bom compromisso entre o retorno esperado e o risco. Em geral, quanto maior o retorno esperado da carteira, maior o risco a ela associado. Neste trabalho foram estudadas modelagens para o problema de escolha de portfólio ótimo e suas aplicações ao mercado brasileiro. Do ponto de vista de modelagem foi proposta a inclusão do risco diversificável e não-diversificável ao modelo linear estudado. O risco diversificável foi incluído através de uma restrição que impõe um número mínimo de ativos na composição do portfólio ótimo, enquanto o risco não-diversificável foi adicionado considerando o beta da carteira. Do ponto de vista de aplicação, foi considerada a atribuição de valores de probabilidade para os retornos históricos dos ativos utilizados na análise do problema, visando incorporar informações do comportamento apresentado pelo mercado nos resultados. Na geração dos resultados, foram desenvolvidos em CPLEX um método ótimo de solução para o problema e um método para geração de uma curva de soluções Pareto ótimas / The process of selecting a portfolio is a classical problem in finance, where the investor intends to invest money in the stock market in such way that a reasonable trade-off between expected return and risk is obtained. In general, the higher the expected return of the portfolio is, the higher his risk will be. In this work the single period portfolio optimization problem is studied in terms of modeling and application for the Brazilian stock market. Referring to the model, changes are proposed to include the diversifiable and nondiversifiable risk. The diversifiable risk is included by imposing a minimum number of assets on the portfolio, while the nondiversifiable risk is controlled by restricting the portfolios beta. On the applications side, a method to estimate the probability of the assets historical returns is proposed, so more information about the market behavior is considered on the problem. The results were obtained by a optimal method to find the best solution and another one to generate the Pareto-optimal solutions, both developed using CPLEX

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.