A Análise de Envoltória de Dados (DEA) é uma metodologia baseada em programação linear que se destina à avaliação da eficiência relativa das DMU's e à estimação de fronteiras de produção. DMU's são entidades gerenciais ou produtivas que transformam fatores de produção em produtos. DEA é um método não-paramétrico porque não é necessário que se imponha uma forma ao processo produtivo. Além disso, ele permite que se trabalhe num complexo contexto com múltiplos fatores e múltiplos produtos. Por outro lado, DEA é um método determinístico e, portanto, não consegue acomodar ruídos de natureza aleatória nos dados. Como a eficiência relativa das DMU's está relacionada com sua distância até a fronteira de produção estimada, um aspecto crítico é garantir que esta fronteira não seja gerada por pontos contaminados por erros. Pontos atípicos ("outliers") dessa natureza podem afetar severamente a estimativa de eficiência de outras DMU's e são chamados de pontos influentes. Nesta dissertação, medidas de eficiência tradicionais são analisadas e três métodos para a detecção e tratamento de pontos influentes baseados nessas medidas são apresentados e analisados. Além disso, são desenvolvidas variações desses métodos. A investigação de medidas de eficiência recentemente propostas também é enfocada, assim como seu uso potencial para a identificação de "outliers". Os métodos supracitados para detecção de "outliers" e avaliação de influência são aplicados a um problema que usa dados reais. Os resultados numéricos produzidos por esses métodos são comparados e analisados. Os pontos influentes são postos em evidência.

Este trabalho aborda o problema dos atrasos de pousos e decolagens de aeronaves devido à sobrecarga dos Aeroportos Brasileiros, principalmente na Terminal São Paulo isto é, Aeroportos de Campo de Marte, Congonhas e Guarulhos. Dentro desta grande área é bem conhecido o descompasso entre os horários previstos para pouso e decolagem e os horários reais. Descompasso esse que por tornar-se cada vez maior passa a ser crítico aos operadores do sistema aéreo, implicando ainda em um maior consumo de combustível e assim como em um aumento, sempre maior, da poluição atmosférica. O trabalho oferece duas contribuições ao problema do seqüenciamento de aeronaves, sob o ponto de vista econômico na redução do consumo de combustível fóssil, uma vez que as filas de aeronaves nas áreas terminais podem ser diminuídas. Mais ainda, o consumo total de combustível do Brasil pode ser reduzido devido ao fato do combustível usado por este setor ter grande impacto no consumo total do País. A outra contribuição tem cunho social, podendo ser traduzida na menor quantidade de emissão de poluentes. Lembrando que a emissão de poluentes está se tornando crítica, principalmente nas vizinhanças de São Paulo onde os aeroportos estão em operação.

Análise de Envoltória de Dados (Data Envelopment Analysis - DEA) é uma metodologia baseada em programação matemática usada para comparar a eficiência de organizações que desempenham atividades similares, como por exemplo, empresas de um mesmo ramo de negócios, agências governamentais, hospitais e universidades. Estas organizações que utilizam tipos similares de entradas (recursos) e produzem saídas (produtos) similares são conhecidos como DMUs (Decision Making Units).Rede Neural de Kohonen é uma metodologia que objetiva a identificação de agrupamentos em um conjunto de objetos a partir: 1) da descrição das características específicas destes objetos, e 2) da definição da função de medida de similaridade entre esses objetos. Esta técnica tem sido aplicada com sucesso em problemas de classificação de padrões como reconhecimento de imagens e de processamento de sinais.Esta dissertação objetiva investigar e comparar a aplicação dessas duas metodologias, DEA e Rede Neural de Kohonen, na análise da eficiência relativa de um grupo de 21 empresas de telefonia fixa que atuam no Brasil a partir dos seus dados reais (receita liqüída, acessos fixos em serviço, força de trabalho geral e investimento).

Neste trabalho efetua-se uma análise dos algoritmos de Data Mining através de estudos de caso. Esses estudos de caso envolvem desde a simples utilização das informações dos algoritmos, como suporte à tomada de decisão na construção de modelos de análise de desempenho, até a construção de modelos com os próprios algoritmos. Os estudos de caso são dedicados a uma análise de aplicação e desempenho de algoritmos específicos. No primeiro estudo, que se refere à Previsão de Solvência de Empresas, são aplicados os algoritmos de Árvore de Classificação. No problema de Procedimentos em Saúde Pública são utilizados os algoritmos de Regras de Associação e as técnicas de Visualização de Dados. No estudo de caso de Predição do Comportamento de Ações aplicam-se os algoritmos de Árvore de Regressão. No estudo de caso principal são utilizados todos os algoritmos e técnicas apresentadas neste trabalho. Trata-se da construção de um modelo de eficiência através da metodologia DEA - Data Envelopment Analysis. Os algoritmos de Data Mining são utilizados como suporte nas diversas escolhas ocorridas durante a construção dos modelos.Em todos os problemas analisados, os resultados obtidos mostram a utilidade dos algoritmos de Data Mining.

Focalizamos, nesta tese, o problema de minimizar o número máximo de pilhas abertas em torno de uma máquina de corte. Desenvolvemos métodos exatos para alguns casos especiais do problema, uma nova heurística e um novo limite inferior para o problema. Propomos, também, aperfeiçoamentos em um método enumerativo apresentado anteriormente na literatura. Testes computacionais com a heurística e métodos desenvolvidos, foram realizados, mostrando os ganhos conseguidos com os novos desenvolvimentos.

Nos últimos anos, o tráfego aéreo tem demonstrado crescimento em seu volume e o não acompanhamento dessa tendência nos auxílios aos vôos vem ocasionando congestionamento no espaço aéreo e em alguns aeroportos do mundo. Esses congestionamentos provocam atrasos. Motivado por esse problema e observando que atrasos em solo são preferíveis a atrasos no ar, este trabalho propõe um modelo de programação binária com o objetivo de minimizar esses atrasos. Basicamente o modelo indica um novo horário de partida dos vôos, de forma a se evitar um desbalanceamento entre a demanda e a capacidade nos diversos elementos da malha aérea. Com isso, diminuem-se os atrasos em vôo/órbita e como conseqüência, garante-se maior segurança e economia para os diversos usuários do sistema. Para finalizar, este estudo apresenta os resultados do modelo para três diferentes situações e compara um dos resultados encontrados com uma solução obtida anteriormente através de um algoritmo heurístico.

Esta tese melhora o upper bound de tempo e de espaço da resolução paralela do Subset-Sum Problem (SSP) - que é uma variante do Problema da Mochila - numa máquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura científica, isto é, tanto na abordagem através das listas como por programação dinâmica. Com relação ao primeiro paradigma, é apresentada uma paralelização ótima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaço O(2n/2), onde 1 p < 2n/2/n2. Como esse algoritmo seqüencial tem até hoje a melhor complexidade de tempo para a resolução do Problema da Mochila, então nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teórico de toda a literatura. Além disso, são apresentados três algoritmos paralelos adaptativos baseados no paradigma da programação dinâmica, que são os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaço O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaço do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente até o momento.

The Subset-sum Problem (SSP) consists of finding a subset of a set of integers whose sum is as close as possible to a target amount, without exceeding it. The problem is NP-complete, but there are dynamic programming-based algorithms which can solve many instances in reasonable time. Most of these algorithms attempt to minimize the time taken to find the solution for &quot;hard&quot; problem instances, but have sub-optimal performance when dealing with &quot;easy&quot; instances, either containing few items or with multiple equivalent solutions of which just one needs to be found. In this work, we analyze the characteristics of several well-known approaches, including standard dynamic-programming Bellman recursion, Horowitz-Sahni decomposition and core algorithms, and suggest variations which improve their average-case performance for easy instances, without harming their worst-case performance significantly. One variation improves the performance of the YS87 single state - multiple stages algorithm for sparse instances. Another minimizes the amount of work required by decomposition-based approaches before a solution is found, allowing the computation to be aborted earlier for dense instances with many exact solutions; this is achieved by using the programming concept of generators in order to compute partial solutions only when they are needed. We also examine the characteristics of several SSP test instance types which are commonly used to compare algorithm performances, analyzing how the distribution of partial solutions varies according to the type and size of the instances. The times taken by several algorithm implementations to solve each of the SSP instance types are measured and compared, and the variations in their behavior when dealing with each one are explained based on the instances'; characteristics.

A geração de grades horárias tem sido estudada extensivamente pela comunidade acadêmica desde que os computadores modernos tornaram-se disponíveis para instituições de ensino. É importante reconhecer sua relevância acadêmica, por ser um problema NP-Completo desafiador, e também prática, já que o planejamento acadêmico define a maioria do orçamento e desempenho operacional do período letivo. Este trabalho objetiva duas contribuições principais para a literatura de Pesquisa Operacional e construção de grades horárias: fornecendo um exemplo real completo de geração automática de grade horária em uma escola de ensino básico brasileira utilizando-se algoritmos híbridos e também um exemplo real de designação de docentes utilizando-se o Simulated Annealing paralelo em GPU em uma grande instância de uma universidade brasileira. Obteve-se 100% de alocação dos docentes para o primeiro caso, além de uma redução no número de janelas da ordem de 16% em relação ao planejamento vigente. Para o segundo caso, obteve-se uma redução no número de docentes sem alocação da ordem de 37.5% e também uma redução no custo médio por crédito alocado da ordem de 6,6%. Os resultados indicam que os modelos propostos são superiores às práticas vigentes.

O presente trabalho propõe um modelo que ajudará os tomadores de decisão a identificar os municípios mais eficientes que poderão ser candidatos a receber uma escola profissionalizante dentro de um determinado estado no Brasil. Será aplicada a Análise Envoltória de Dados (DEA - Data Envelopment Analysis) para ranquear os municípios através da avaliação de eficiência. Os indicadores que serão utilizados pela DEA foram definidos por um modelo utilizado pelo Instituto de Pesquisa e Estratégia Econômica do Ceará (IPECE). Os municípios do estado objeto do estudo serão classificados por regiões conforme os Arranjos Produtivos Locais (APLs). Os resultados obtidos serão confrontados com os cenários de investimentos industriais previstos pelo Governo para cada região para validar a escolha do município-candidato.