O problema de alocação de aeronaves a voos, ou tail assignment problem (TAP), consiste em determinar qual aeronave realizará cada voo da malha de uma empresa aérea, visando a minimizar o custo total da operação e respeitando diversas restrições de conectividade de voos, permanência de aeronaves no solo, serviços obrigatórios de manutenção, limitações técnicas e desempenho de aeronaves, conexões de passageiros e tripulantes e famílias com diversos modelos de aeronaves. Este trabalho apresenta um modelo matemático exato e um método heurístico para a solução do TAP considerando todas as restrições citadas, o que não ocorre com os modelos encontrados na literatura. Os modelos desenvolvidos, baseados em programação linear inteira e na meta-heurística Busca Tabu, foram aplicados a problemas reais, extraídos da malha de uma empresa aérea brasileira, operadora de 35 aeronaves e cerca de 210 voos diários. Os resultados obtidos são compatíveis com a operação da empresa e apresentam ganhos em relação ao método de alocação de aeronaves utilizado na operação diária. Os tempos de processamento para solução pelo método exato são excessivamente longos, indicando que o método heurístico é mais adequado para a utilização em empresas aéreas, com resultados adequados obtidos em tempos de processamento satisfatórios. / The problem known as Aircraft Assignment or Tail Assignment Problem (TAP) is the problem of assigning flights to each aircraft of an airline\'s fleet, aiming at minimizing the total operating cost while complying with several constraints, such as network connectivity, aircraft time on ground, mandatory maintenance services, aircraft technical restrictions, passengers and crew connections, aircraft performance and aircraft families with more than one type. This work presents a deterministic mathematical model and a heuristic method to solve the TAP considering all constraints listed above, what does not happen with the models found in the literature. The proposed methods, based on mathematical integer programming and on the Tabu Search metaheuristic, were applied to problems obtained from the network of a Brazilian airline, operating 35 aircraft and around 210 daily flights. The results show the models are suitable to solve the problem and savings are observed when compared to the current assignment method. The long processing times intrinsic to the deterministic method show the heuristic method is more suitable for use in airlines, with suitable results obtained at acceptable computational times.

Orientador: Silvio Alexandre de Araujo / Banca: Helenice de Oliveira Florentino Silva / Banca: Maria do Socorro Nogueira Rangel / Resumo: Este trabalho trata do problema de corte de estoque unidimensional inteiro, que consiste em cortar um conjunto de objetos disponíveis em estoque para a produção de itens menores demandados, de tal forma que se otimize uma ou mais funções objetivos. Foi estudado o caso em que existe apenas um tipo de objeto em estoque em quantidades suficiente para atender a demanda. Três adaptações de um método heurístico baseadas nos conceitos dos algoritmos evolutivos multiobjetivo são propostas para resolver o problema considerando duas funções objetivo conflitantes, a minimização do número de objetos cortados e a minimização do número de diferentes padrões de corte. As adaptações utilizam as idéias presentes no método da Soma Ponderada, no Vector Evaluated Genetic Algorithm e no Multiple Objective Genetic Algorithm. Estas heurísticas são analisadas resolvendo-se instâncias geradas aleatoriamente. / Abstract: This work deals with the one-dimensional integer cutting stock problem, which consist of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to optimize one or more objective functions. On the case studied there is just one type of object in stock available in sufficient quantity to satisfy the demand. Three adaptations of a heuristic method based on the multi-objective evolutionary algorithms concepts are proposed to solve the problem considering two conflicting objective functions, the minimization of the number of objects to be cut and the minimization of the number of different cutting patterns. The adaptations consider the ideas from the Weighted Sum method, the Vector Evaluated Genetic Algorithm and the Multiple Objective Genetic Algorithm. These heuristics are analyzed by solving randomly generated instances. / Mestre

O conteúdo deste trabalho trata da formulação para solução do problema de otimização estrutural com minimização de massa em estruturas unifilares, sujeitas a restrição de tensão, flambagem das barras isoladas e fadiga. São considerados três casos de otimização: paramétrica, de forma e dimensional. Os problemas de singularidades nas restrições de tensão e flambagem são evitados através de uma formulação que faz uso de programação inteira para solução do problema. Outra singularidade encontrada na otimização topológica é a singularidade na matriz de rigidez da estrutura. Este problema foi evitado através de uma formulação que considera a existência de matriz de rigidez regular como restrição do problema. O método de solução utilizado para resolver problema de otimização é o método dos algoritmos genéticos. As restrições do problema são impostas através da penalização da função objetivo. O método de solução mostrou-se adequado para solução dos problemas estudados. A formulação implementada é validada através da solução de problemas clássicos de otimização estrutural. Os resultados obtidos são comparados com a literatura onde verificou-se a coerência dos mesmos. Após realizar a validação, a formulação é utilizada em um estudo que tem como base uma estrutura real: uma torre de queima de gases (flare) oriundos do processo de extração e armazenagem de petróleo em uma unidade flutuante. Para o problema da torre as restrições foram determinadas com base em critérios de falha estabelecido na norma DNV. A otimização do flare permitiu minimizar a massa da estrutura sem que os critérios de falha fossem violados. Verificou-se que a metodologia proposta é adequada para solução com grande número de restrições e com diversos casos de carregamento. / The purpose of this work is the development of a methodology to solve the structural optimization problem of frame structures subject to stress, buckling of isolated members, and fatigue constraints. Three types of structural optimization problems are considered: sizing, shape and topological. The stress and buckling singularity problems are avoided by an integer design variable formulation, using integer programing to obtain the optimization problem solution. Another issue found in optimization problems is the stiffness matrix singularity. The proposed formulations include the linear system stability as a constraint in the optimization problem. A genetic algorithm is used to solve the general optimization problem. All constraints of the problem are included with a penalization equation. The results show that genetic algorithm is a good approach to solve the proposed formulation. The proposed formulation is tested for solving classical optimization problems. The obtained results are consistent with the literature. A real engineering problem is solved with proposed methodology: a gas burning tower (flare). In this problem, all constraints are based on failure criteria recommended by DNV standards. The structural optimization of this problem shows that structural mass minimization is possible without violating the failure criteria. It is observed that solution methodology deals successfully with problems with multiple constraints and load cases

Nesta dissertação, discute-se o problema de otimização de carteiras de investimento para estratégia passiva de Index Tracking. Os objetivos principais são (i) apresentar um modelo de otimização de Index Tracking e (ii) a solucionar esse modelo com uso do método heurístico de Algoritmos Genéticos (AG) para formação de carteiras com número reduzido de ativos. O índice de referência utilizado é o Ibovespa, para o período de Janeiro/2009 a Julho/2012, com um total de 890 observações diárias de preços. A partir de uma amostra de 67 ativos, são formadas carteiras sem limite de ativos e limitadas a 40, 30, 20, 10 e 05 ativos; os intervalos de rebalanceamento das carteiras são 20, 40 e 60 períodos (dias úteis), ou seja, rebalanceamento mensal, bimestral e trimestral. É verificado que, para essa amostra, não é possível formar carteiras de 20 ou menos ativos via otimização direta com o solver Cplex com menos de 1 hora de processamento e gap abaixo de 5%. Com uso da heurística de Algoritmos Genéticos, são formadas carteiras de 10 e 05 ativos com tempo de processamento em torno de 5 minutos; nesse caso, o gap médio fica abaixo de 10% para ambos os tipos de carteira. E, com tempo de processamento do AG um pouco maior, em torno de 8 minutos, o algoritmo fornece soluções para carteiras de 10 e 05 ativos com gap médio abaixo de 5%. / In this master’s thesis it is discussed the portfolio optimization problem using the passive investment strategy of Index Tracking. The main goals are (i) to present an optimization model for the Index Tracking problem and (ii) to solve this model using the heuristic approach of Genetic Algorithms (GA) to create portfolios with reduced amount of stocks. The benchmark used is the Ibovespa Index (main reference for the Brazilian Stock Market), during the period from January/2009 to July/2012 (using a total of 890 daily stock prices). The sample contains 67 assets, and the model is used to build portfolios without limit in the amount of assets and portfolios limited to 40, 30, 20, 10 and 05 assets; the ranges of time to rebalance the portfolios are 20, 40, and 60 trading days, which means to rebalance monthly, bimonthly and quarterly. The results show that, considering this sample, it is not possible to build portfolios with 20 stocks (or less than 20) through direct optimization using the solver Cplex with computational processing time less than 1 hour and results with gap below 5%. On the other hand, using the Genetic Algorithms heuristic approach, portfolios limited to 10 and 05 stocks are built with computational time close to 5 minutes; for both types of portfolio, the solutions provided by the GA have average gap below 10%. Also, with a computational time slightly bigger, close to 8 minutes, the algorithm provides solutions with average gap below 5% for portfolios limited to 10 and 05 stocks.

Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.

abstract: A Pairwise Comparison Matrix (PCM) is used to compute for relative priorities of criteria or alternatives and are integral components of widely applied decision making tools: the Analytic Hierarchy Process (AHP) and its generalized form, the Analytic Network Process (ANP). However, a PCM suffers from several issues limiting its application to large-scale decision problems, specifically: (1) to the curse of dimensionality, that is, a large number of pairwise comparisons need to be elicited from a decision maker (DM), (2) inconsistent and (3) imprecise preferences maybe obtained due to the limited cognitive power of DMs. This dissertation proposes a PCM Framework for Large-Scale Decisions to address these limitations in three phases as follows. The first phase proposes a binary integer program (BIP) to intelligently decompose a PCM into several mutually exclusive subsets using interdependence scores. As a result, the number of pairwise comparisons is reduced and the consistency of the PCM is improved. Since the subsets are disjoint, the most independent pivot element is identified to connect all subsets. This is done to derive the global weights of the elements from the original PCM. The proposed BIP is applied to both AHP and ANP methodologies. However, it is noted that the optimal number of subsets is provided subjectively by the DM and hence is subject to biases and judgement errors. The second phase proposes a trade-off PCM decomposition methodology to decompose a PCM into a number of optimally identified subsets. A BIP is proposed to balance the: (1) time savings by reducing pairwise comparisons, the level of PCM inconsistency, and (2) the accuracy of the weights. The proposed methodology is applied to the AHP to demonstrate its advantages and is compared to established methodologies. In the third phase, a beta distribution is proposed to generalize a wide variety of imprecise pairwise comparison distributions via a method of moments methodology. A Non-Linear Programming model is then developed that calculates PCM element weights which maximizes the preferences of the DM as well as minimizes the inconsistency simultaneously. Comparison experiments are conducted using datasets collected from literature to validate the proposed methodology. / Dissertation/Thesis / Ph.D. Industrial Engineering 2013

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.

Context: Unmanned Aerial Vehicles are being widely being used for various scientific and non-scientific purposes. This increases the need for effective and efficient path planning of Unmanned Aerial Vehicles.Two of the most commonly used methods are the A-star algorithm and Mixed Integer Linear Programming.Objectives: Conduct a simulation experiment to determine the performance of A-star algorithm and Mixed Integer Linear Programming for path planning of Unmanned Aerial Vehicle in a simulated environment.Further, evaluate A-star algorithm and Mixed Integer LinearProgramming based computational time and computational space to find out the efficiency. Finally, perform a comparative analysis of A star algorithm and Mixed Integer Linear Programming and analyse the results.Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of Objectives: Conduct a simulation experiment to determine the performance of A-star algorithm and Mixed Integer Linear Programming for path planning of Unmanned Aerial Vehicle in a simulated environment.Further, evaluate A-star algorithm and Mixed Integer LinearProgramming based computational time and computational space to find out the efficiency. Finally, perform a comparative analysis of A star algorithm and Mixed Integer Linear Programming and analyse the results.Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of these methods. These methods are then implemented on these test scenarios and the computational times for both the scenarios were observed.A hypothesis is proposed to analyse the results. A performance evaluation of these methods is done and they are compared for a better performance in the generated environment. Results: It is observed that the efficiency of A-star algorithm andMILP algorithm when no obstacles are considered is 3.005 and 12.03functions per second and when obstacles are encountered is 1.56 and10.59 functions per seconds. The results are statistically tested using hypothesis testing resulting in the inference that there is a significant difference between the computation time of A-star algorithm andMILP. Performance evaluation is done, using these results and the efficiency of algorithms in the generated environment is obtained.Conclusions: The experimental results are analysed, and the Conclusions: The experimental results are analysed, and the efficiencies of A-star algorithm and Mixed Integer Linear Programming for a particular environment is measured. The performance analysis of the algorithm provides us with a clear view as to which algorithm is better when used in a real-time scenario. It is observed that Mixed IntegerLinear Programming is significantly better than A-star algorithm.

The recent increase in performance of embedded processors has enabled the use of computationally heavy asymmetric cryptography in small and power efficient embedded systems. The goal of this thesis is to analyze whether it is possible to use this type of cryptography to enhance the security in access systems. This report contains a literature study of the complications related to access systems and their functionality. Also a basic introduction to cryptography is included. Several cryptographic algorithms were implemented using the public library LibTomCrypt and benchmarked on an ARM7-processor platform. The asymmetric coding schemes were ECC and RSA. The tested symmetric algorithms included AES, 3DES and Twofish among others. The benchmark considered both codesize and speed of the algorithms. The two asymmetric algorithms, ECC and RSA, are possible to be used in an ARM7 based access system. Although, both technologies can be configured to finish the calculations within a reasonable time-frame of 10 Sec, ECC archives a higher security level for the same execution time. Therefore, an implementation of ECC would be preferable since it is faster and requires less resources. Some further suggestions of improvements to the implementation is discussed in the final chapters.

Fixed interval scheduling problems have wide range of practical use in production planning, transportation, in hospitals or in schools when planning timetables. When solving these problems we often encounter requirement of integrality of solutions. Ignoring this condition is often not possible. In this thesis we propose some formulations of scheduling problems and their stochastic extensions. We also propone a new formulation of stochastic FIS problem, for which integrality of solution is byproduct of its definition. We present Gâteaux derivative and its relationship to stability of optimal value function of stochastic optimization problems under the influence of contamination. We propose a new theorem on the stability of such functions for fixed interval scheduling problems.