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).

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.

Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

O problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês Assembly Line Worker Assignment and Balancing Problem ) é uma extensão do problema simples de balanceamento de linhas na qual os tempos de execução de tarefas são dependentes dos trabalhadores. Este problema tem sua motivação prática oriunda de linhas de produção com trabalhadores deficientes. Neste trabalho, focamos em uma extensão para o problema que permite lidar com a possibilidade de layouts de linhas com estações em paralelo. Além disso, estudamos uma segunda variante do problema que permite que os trabalhadores colaborem uns com os outros em uma mesma estação. Apresentamos formulações matemáticas para ambas as versões do problema. Adicionalmente, a partir de adaptações de métodos existentes para o ALWABP serial, desenvolvemos heurísticas construtivas para o ALWABP paralelo e ALWABP colaborativo. Testes computacionais em instâncias da literatura e uma análise detalhada dos resultados são apresentados / The assembly line and worker assignment balancing problem is an extension of the classical simple assembly line balancing problem where task execution times are workerdependent. This problem is motivated by the situation faced when balancing assembly lines with disabled workers. In this study, we focus on an extension for the problem with the goal of including the possibility of having layouts with parallel workstations. We also study a second variation for this problem that allows workers collaborating with each other. We present mathematical formulations for both problems. Moreover, constructive heuristics are developed, based on heuristic methods for the serial assembly line worker assignment and balancing problem. Computational tests on literature instances and a detailed analysis of the results are reported

Este trabalho tem como objetivo solucionar problemas complexos em diferentes segmentos da Engenharia de Produção e Transporte a partir da utilização de técnicas de otimização. São consideradas as áreas de sistemas de saúde, transportes e análise sensorial, envolvendo problemas de formação de grade de horários e análise de clusters. De forma específica, as abordagens objetivam: (i) em relação ao setor hospitalar, alocar especialidades cirúrgicas em uma grade de horários de um hospital de modo a minimizar a variância do tempo pós-operatório; (ii) quanto à análise sensorial, desenvolver um índice capaz de identificar painelistas que necessitam de treinamento utilizando conceitos de análise de clusters; (iii) no setor aeroportuário, identificar aeroportos com baixa capacidade preditiva de demanda e relacioná-los com suas características físicas, a partir da análise de clusters. Em todos os problemas abordados, as soluções envolvendo métodos de otimização se mostraram adequadas, com resultados satisfatórios. / This study aims to solve complex problems in different segments of Production Engineering and Transportation using optimization techniques. Different areas are considered, such as the areas of health systems, transport and sensory analysis, involving the timetable scheduling problem and cluster analysis. Specifically, this works aims to: (i) in relation to the hospital sector, allocate surgical specialties in a timetable in order to minimize the variance of postoperative time; (ii) for the sensory analysis, develop an index able to identify panelists who require training, using concepts of cluster analysis; (iii) in the airport sector, identify airports with low predictive capacity of demand and relate them to their physical characteristics, using cluster analysis. In all addressed problems, solutions involving optimization methods were adequate, with satisfactory results.

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-02-28Bitstream added on 2014-06-13T20:48:40Z : No. of bitstreams: 1 costa_tm_me_sjrp.pdf: 1425800 bytes, checksum: f5b08954e14201ee5211145299b1e813 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, estamos interessados em apresentar uma abordagem relacionando a análise não suave com a otimização. Primeiramente, é realizado um estudo sobre conceitos da análise não suave, como cones normais, cone tangente de Bouligand, subdiferenciais proximal, estrita, limite e de clarke. Com esses conceitos exibimos uma série de resultados, por exemplo, uma caracterização par funções de Lipschitz, subdiferencais da soma, produto e máximo de funções semi-contínuas inferior, uma versão não suave dos multiplicadores de Lagrange, i.e., condições de primeira ordem para otimalidade de problemas de otimização não suaves. Também é feito um estudo sobre as condições de segunda ordem para otimalidade em problemas de otimização não suaves e para isso, foi necessário a apresentação de outros conceitos e propriedades como os de Hessiana generalizada, Jacobiana aproximada a Hessiana proximada. Após a apresentação desses resultados, é feita uma análise sobre dois Teoremas que fornecem, com abordagens distintas, condições suficiente de segunda ordem para problemas de otimização não suaves e este trabalho é finalizado com a aprsentação de um resultado que é considerado uma unificação desses dois Teoremas / In this work we are interested in the presentation of an approach relating Nonsmooth Analysis to Optimization. First we make a study about concepts of nonsmooth analysis such as, normal cone, Bouligand's tangent cone, proximal, strict and limiting Subdiferential, as well as Clarke's Suddifferential. After these, we exhibit a series of results, for example, a characterization of Lipschitz functions, Subdifferential sum, product and maxium rules of lower semicontinuous functions and a nonsmooth version of Lagrange's multiplier rule, that is, a first order necessary condition of optimality for nonsmooth optimization problems. We also made a study about second order optimality conditions for nonsmooth optimization problems. In order to do that, it was necessary to present other concepts and properties about generalized Hessian, approximate Jacobian and approximate Hessian. After presenting these concepts and results, an analysis of two theorems that provide, with different approches, second order conditions for optimality for nonsmooth problems is made. Finally, this dissertation is completed with the exposition of a result that is considered a unification of these two theorems

Submitted by Secretaria Pós de Produção (tpp@vm.uff.br) on 2017-07-27T19:52:32Z No. of bitstreams: 1 D2014 - Luiz Aizemberg.pdf: 13176203 bytes, checksum: 7bf48143ab75b243fe03ef2cad6ef82b (MD5) / Made available in DSpace on 2017-07-27T19:52:32Z (GMT). No. of bitstreams: 1 D2014 - Luiz Aizemberg.pdf: 13176203 bytes, checksum: 7bf48143ab75b243fe03ef2cad6ef82b (MD5) / Nesta tese de doutorado, foram estudados modelos matemáticos e outras técnicas de otimização para um problema de nível tático de transporte de óleo e derivados. O problema monoproduto e monomodal considera capacidades de estoque e tamanhos de lote discretos a serem transportados, objetivando atender as demandas ao longo de um horizonte de tempo. Testes exaustivos foram realizados com 75 instâncias retiradas da literatura e com 25 novas instâncias com maior grau de dificuldade do que as já existentes. Uma heurística baseada em geração de colunas foi desenvolvida para encontrar boas soluções viáveis em menos tempo do que os algoritmos heurísticos do otimizador comercial utilizado. Este estudo foi posteriormente utilizado no desenvolvimento de um modelo matemático multiproduto e multimodal, onde diversas restrições encontradas no planejamento logístico de uma empresa de petróleo são consideradas. Nesta etapa, foram pesquisadas e testadas técnicas de otimização com maior aderência a modelos matemáticos complexos. Optou-se por mudar o foco de métodos exatos para heurísticos. Uma heurística baseada em busca local foi construída e sua eficiência comprovada. Além das instâncias utilizadas no estudo anterior, instâncias baseadas em dados reais foram utilizadas, o que permitiu testar todas as restrições do modelo. / In this thesis, we study tactical models and other optimization techniques for a crude oil transportation problem. The problem with one product and one transportation mode considers inventory capacities and discrete lot sizes to be transported, aiming at meeting given demands over a finite time horizon. We use 75 instances from the literature and propose 25 new harder ones. A column generation-based heuristic is proposed to find good feasible solutions with less computational burden than the heuristics of the commercial solver used. The optimization study is then used in the development of a mathematical model with several products and transportation modes, where many real constraints found in the logistic management of a petroleum company are considered. Optimization techniques more adherent to complex mathematical models are studied. The focus changed from exact to heuristic methods. A local search heuristic was devised and its efficiency comproved. Instances from the previous study and new instances based on real data are used. These new instances allow testing the new constraints added in the model.

No description available.