Perturbações na malha aérea ocorrem em todo o mundo e afetam econômica e operacionalmente as empresas aéreas. Em 2016, os gastos que essas perturbações causaram às empresas aéreas e aos seus clientes giraram em torno de US$60 bilhões, cerca de 8% da receita de todas as empresas aéreas do mundo. Este trabalho apresenta uma Heurística Matemática Híbrida, envolvendo otimização por programação inteira mista, para resolver o Problema da Recuperação da Malha Aérea de uma empresa, em até vinte minutos, para uso do Centro de Controle Operacional (CCO) da empresa aérea. A solução consiste em uma nova programação de voos que minimiza os custos da alteração da malha aérea e atenda as restrições impostas por um cenário de múltiplas perturbações, quais sejam: atrasos, cancelamentos de voos, fechamento ou redução de capacidade aeroportuária e manutenções não-programadas. Além da heurística, apresenta-se também um modelo de fluxo em rede com programação inteira para resolver de forma exata o Problema da Recuperação da Malha. Esse modelo obteve resultados em instância de até 500 voos, para todo tipo perturbação, em tempo de execução razoável, exceto para as instâncias em que a capacidade aeroportuária estava muito comprometida. A heurística matemática híbrida apresentou resultados com diferenças de até 5% com relação ao ótimo para as instâncias com até 6000 voos, independentemente do nível de perturbação imposta à malha aérea, com tempo de execução que permite o seu uso prático. / Schedule disruptions occurs worldwide and affect economically and operationally the airlines. In 2016, disruptions cost airlines and their customers around $60 billion, or about 8% of worldwide airline revenue. In this thesis, a Hybrid Math-Heuristic including a mixed-integer linear optimization is presented. It is aimed at assisting airlines to solve the Aircraft Recovery Problem through their Operations Control Centers (OCC) in up to twenty minutes. The solution consists in a new changed schedule that minimizes the cost of changes and deals with constraints related to a scenario with multiple disruptions: delays, flight cancelations, closures or airport capacity reduction and non-scheduled maintenance. Besides the heuristic, a network flow integer programming model is presented to provide exact solutions to the Aircraft Recovery Problem. The Exact Model achieved optimal results for instances with up to 500 flights subjected to all kinds of disruptions in reasonably times, except for instances with highly constrained airport capacity. The Hybrid Math-Heuristic achieved results with maximum optimal GAP of up to 5% for instances with up to 6.000 flights, no matter the level of the imposed disruption, with time of execution that permits its use in practice.

Submitted by Maria Cristina (library@lncc.br) on 2017-05-02T19:25:42Z No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-05-02T19:25:53Z (GMT) No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) / Made available in DSpace on 2017-05-02T19:26:02Z (GMT). No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) Previous issue date: 2017-02-21 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Many emerging challenges currently arising in science relate to understanding the dynamics and structure of complex systems consisting of interacting components. People on online social networks, power grids, air transportation networks, human brain connections, and agents in the financial market are some examples of network systems present in many domains. These systems, given their scale and non-trivial connectivity patterns, are called complex networks. In this sense, the dimension of these networks turns imperative the adoption of computing systems in support to their analysis. In this case, graphs are the usual tool for the representation of complex networks. Moreover, as the scientific investigation for these graphs is of great significance for many domains, the researcher and developer communities have proposed many computing platforms for their processing. However, the multitude of graph processing platforms brings up questions about the implications of their adoption, given the analysis, network and computing environment characteristics of the analysts. Therefore, in this dissertation, we propose a multi-perspective model for the performance evaluation of graph processing platforms which differs from related works in simultaneously approaching the topic from four perspectives: algorithms, computing environment, networks, and platforms. Additionally, we carry out a performance evaluation study that follows the directives indicated by the proposed model for a representative set of algorithms, platforms, and networks, demonstrating the proposed model applicability as exhibits the relationship between algorithms, networks and platforms efficiency. / Alguns dos desafios mais relevantes que surgem no cenário científico atual envolvem a compreensão da dinâmica e estrutura de sistemas complexos constituídos por componentes em interação. Pessoas em redes sociais online, sistemas de distribuição de energia, malhas aéreas, conexões no cérebro humano ou mesmo agentes no mercado financeiro são apenas alguns exemplos de tais sistemas em rede oriundos de diversas áreas. Esses sistemas, por causa de sua escala e da não trivialidade de seus padrões de conectividade, são chamados de redes complexas. Nesse contexto, a dimensão dessas redes torna imprescindível a utilização de sistemas computacionais em apoio às suas análises, sendo grafos a ferramenta típica de representação de redes complexas para sua modelagem computacional e estudo. Mais ainda, como a análise de grafos em diversos domínios é de grande relevância, muitas plataformas computacionais para o seu processamento têm sido propostas recentemente; o que provoca questionamentos pertinentes de quais as implicações da escolha de uma delas, dadas as características de análise, rede e ambiente computacional dos interessados. Portanto, esta dissertação propõe um modelo multiperspectiva de avaliação de desempenho de plataformas de processamento de grafos, o qual se distingue da literatura ao abordar o problema considerando simultaneamente quatro perspectivas: algoritmos, arquitetura computacional, plataformas e redes. Além disso, um estudo de avaliação de desempenho de um conjunto diverso e representativo de algoritmos, plataformas computacionais e redes é realizado utilizando as diretivas indicadas pelo modelo, demonstrando sua aplicabilidade ao expor o relacionamento entre as características de redes complexas e algoritmos com a eficiência computacional das plataformas.

A Análise Envoltória de Dados (DEA) é uma ferramenta da estatística não-paramétrica que avalia a eficiência de unidades tomadoras de decisão (DMUs), comparando entidades que realizam tarefas similares e se diferenciam pela quantidade de recursos (inputs) e de bens (outputs) envolvidos. Enquanto os modelos clássicos de DEA baseiam-se em liberdade total de ação, tanto na utilização de recursos como na produção de bens, há casos em que essa liberdade não existe. Neste trabalho são propostos quatro modelos tipo DEA baseados em inputs/outputs limitados, nos quais a distribuição dos recursos/produtos pode ser influenciada tanto pelos inputs como pelos outputs envolvidos. Os modelos foram construídos de acordo com o perfil geométrico da fronteira CCR tridimensional, podendo ter forma hiperbólica ou esférica, dependendo da natureza da variável que queremos distribuir. Os modelos desenvolvidos são aplicados em dois estudos de caso relacionados com o Sistema Integrado de Supervisão e Gestão de Parâmetros Operacionais (SISGPO), projeto do Comando da Aeronáutica (COMAER).

Existem vários trabalhos na literatura de pesquisa operacional sobre a distribuição de inputs e outputs. Da mesma forma, existem muitos trabalhos teóricos e práticos sobre Análise de Envoltória de Dados (Data Envelopment Analysis - DEA). No entanto, poucos são os que realizam a distribuição de inputs e outputs limitados utilizando DEA ou que empregam o DEA paramétrico. O objetivo deste trabalho é apresentar um modelo DEA paramétrico, chamado de Modelo de Fronteira Esférica Ajustado (MFEAj), que realiza a distribuição de um novo input contínuo para um conjunto de unidades tomadoras de decisão, considerando os seus inputs e outputs. O modelo busca, após a inclusão do novo input, tornar todas as DMU's DEA eficientes, considerando o retorno de escala constante e arbitrando que a fronteira de eficiência DEA é esférica. Exemplos numéricos mostraram que o MFEAj apresentou melhores resultados que outros modelos da literatura. Além disso, o MFEAj apresentou uma desejável propriedade, chamada de propriedade de redistribuição coerente, que não foi observada em outros modelos. Após a definição dessa propriedade, apresenta-se um teorema demonstrando que, de fato, o MFEAj pode assegurá-la. Esta propriedade viabilizou o estudo de limites de ruídos nos dados de input e output de todas as unidades envolvidas. Também é apresentado resumidamente o Modelo de Fronteira Hiperbólica Ajustado, um aperfeiçoamento do Modelo de Fronteira Hiperbólica, que faz a distribuição de uma quantidade limitada de um output e torna também todas as DMU's eficientes.

O presente trabalho apresenta um modelo que propõe quantificar as variações nos outputs (produtos) de um sistema quando um novo input (insumo) é acrescentado, ou quando há variação nos inputs já presentes. As fórmulas propostas consideram os outputs antes das alterações, os inputs inseridos ou alterados e alguns parâmetros conhecidos a priori. A variação destes parâmetros é analisada, e algumas propriedades do modelo, quando analisado via DEA-CCR, são consideradas. Quando os parâmetros assumem alguns conjuntos de valores específicos, duas propriedades são observadas e demonstradas: (i) as eficiências DEA-CCR de nenhuma DMU decresce após a inclusão de um novo input e alteração dos outputs conforme modelo proposto; (ii) para um conjunto de valores dos parâmetros do modelo, a distribuição final dos outputs depende apenas da distribuição final dos inputs, não dependendo de alterações intermediárias nestes inputs.

This essay presents the construction of a two-steps approach using Weapon-Targeting Assignment (WTA) problem mathematical modeling and Analytical Hierarchy Process (AHP) addressing two phases of the the targeting cycle, concerning both targeting and weaponeering activities on the context of a small Joint Force Air Component, in order to support timely, feasible, and conflict-consistent decision-making on weapon-target assignments. It starts clarifying the motivation for this work, related to personal operational activities. It is assumed that this past experience allowed the perception of staff difficulties which are presented as effects whose causes led to scoping this essay into constructing a suitable approach for using WTA models and AHP for supporting Command and Control processes. The relevant concepts of Command and Control are introduced, and it follows with nsiderations about WTA and targeting on related work, as well as about AHP being suitable to support the addressed problem. At this point the asset-target evaluation and tradeoff assessment are assumed as risks and benefits of the possible alternatives. The WTA formulation is made to include doctrinal and restrain criteria to approximate the provided solutions to the needs of the decision-makers, pointing out to the advantage of defining few alternatives from the large combinatorial realm, which simplifies the use of AHP. This work also describes a case for the proposed approach which clarifies the concepts presenting their practical usage. The discussion of this case leads finally to the conclusions of the approach suitability and to suggested ideas for field evaluation.

Inicialmente este problema é enquadrado no contexto mais amplo de Corte e Empacotamento e uma forma exata de resolver o problema é apresentada. O problema é NP-'Arduo no sentido forte e extremamente difícil de ser resolvido na prática, por isso uma atenção especial aos algoritmos aproximativos e seus desempenhos, não poderia ser omitida. Como resultado, uma classe de algoritmos aproximativos (heurísticas e meta-heurísticas) foi desenvolvida e seus desempenhos avaliados com relação às heurísticas famosas. O procedimento para o preenchimento dos itens dentro dos bins utiliza o bem conhecido princípio da alocação em pontos de cantos. Os critérios para a estabilidade estática dos itens dentro dos bins são apresentados com detalhes. Uma abordagem distribuída também foi usada como forma de resolver o problema, com o intuito de diminuir o tempo de execução computacional dos algoritmos aproximativos que levam em conta a estabilidade estática dos itens dentro dos bins. Grande quantidade de experimentos computacionais são apresentados para problemas com até 90 itens (com e sem estabilidade estática) e os resultados são comparados com aqueles obtidos da literatura. Por último, foi sugerida algumas idéias para o direcionamento das futuras pesquisas sobre o problema.

O grande crescimento da quantidade de aplicações de soluções computacionais nos mais diversos segmentos da sociedade levaram a atenção de pesquisadores e desenvolvedores também para a área de ensino. Contudo, o foco tem sido mais dirigido para aplicações de software e hardware paradidáticos, de apoio ao ensino propriamente. Pouco tem sido feito para melhorar a gestão do ensino, mais especificamente na montagem de cursos, no apoio à construção de sua grade horária, o qual é objeto de interesse deste trabalho. Recentemente, o problema de Montagem de Grade Horária tem ganhado um status mais importante, com segmentos de congressos especialmente dedicados ao tema dada sua complexidade, uma vez que o número de soluções passíveis de serem consideradas na busca de uma solução pelo menos satisfatória é muito grande. Sendo assim, a implementação de soluções eficientes emerge como um desafio potencial assim como a comparação entre as mesmas, dada a diversidade surgida ao longo dos anos. Este trabalho apresenta dois protótipos de software para a solução do problema utilizando como base métodos, ou ferramentas, de Inteligência Artificial, Algoritmo Genético e Simulated Annealing, que têm se demonstrado promissores e de comprovada eficiência. Os protótipos oferecem duas propostas de implementação dos algoritmos, representação de conhecimento e avaliação de soluções candidatas, assim como sua avaliação de desempenho. O trabalho também apresenta uma análise comparativa do desempenho das duas implementações, sob a ótica de métricas importantes para a análise dos referidos algoritmos aplicados à solução do problema em estudo, comparando-as e estabelecendo ponderações para futuros estudos similares e implementações.

O presente estudo visa complementar o desenvolvimento de um modelo de alocação de insumos, de soma constante, paramétrico, que se adapta as características da Análise Envoltória de Dados, DEA (Data Envelopment Analysis), e que garante uma solução fortemente eficiente ("strongly efficient") para todas as Unidades Tomadoras de Decisão, DMUs (Decision Making Units), em modelos com retorno constante de escala. Trata-se do Modelo EFM, Ellipsoidal Frontier Model, baseado numa fronteira de eficiência paramétrica em formato elipsoidal, capaz de distribuir inputs levando em conta os valores de inputs e outputs do problema. O EFM fornece várias possibilidades de soluções em razão da sua flexibilidade, atribuída aos graus de liberdade (excentricidades) do modelo. Por esta razão, despertou-se o interesse em orientar o decisor na escolha da melhor solução, objetivo do presente trabalho. Assim, são propostas três análises, classificadas como: Análises Local 1 (AL1), Análise Local 2 (AL2) e Análise Global (AG). A primeira (AL1) busca uma solução que obtenha o menor valor do input enquanto a segunda (AL2), a menor variabilidade, ambos associados a uma determinada DMU. E por fim, a AG, com vistas a uma solução com a menor variabilidade total do conjunto dos dados, ou seja, de todas as DMUs da distribuição. Para cada uma das análises são propostos também um Problema de Otimização Não Linear (PNL) para sua resolução. Desse modo, indicam-se a combinação de excentricidade com uma redistribuição dos inputs considerada mais favorável ao decisor.

O sucesso de uma organização depende, entre outros fatores, da qualidade dos produtos e serviços que esta organização oferece ao mercado. Entretanto, a fase de desenvolvimento de um produto aeronáutico é mais longa que a da maioria dos bens de consumo, e exige investimentos usualmente muito maiores. Esses dois fatores associados fazem com que uma decisão incorreta na escolha do próximo projeto a ser implantado possa levar uma indústria aeronáutica à falência. O processo de escolha do melhor projeto é bastante complexo e aprimorá-lo constantemente é o desafio a ser vencido por uma indústria aeronáutica que busca atuação perene em um mercado extremamente competitivo. Este trabalho tem por objetivo apresentar a utilização do método AHP com Ratings na determinação das características de jatos executivos leves, em uma indústria aeronáutica. Este trabalho propõe o uso do método para solucionar um problema com 1.490.244 alternativas, até a presente data, não havia na literatura registro algum da aplicação do método AHP com Ratings em problemas com esse número de alternativas. Para aplicação do método foi desenvolvido um software que permitiu encontrar a melhor alternativa.