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.

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.

Este trabalho apresenta uma proposta de modelagem por otimização robusta aplicada ao problema incerto de demanda contratada de potência ativa enfrentado por consumidores de alta tensão tarifados no sistema convencional, e que podem estabelecer contratos de demanda de 30 a 300 kW, inseridos no Pólo Industrial de Manaus - PIM/AM. Os dados utilizados nas análises foram simulados considerando as principais características das curvas de carga de consumidores industriais, sendo propostos sete cenários relevantes, sob critérios de linearidade (linear e não linear), variância (baixa, média e alta) e tendência das curvas (crescente, decrescente e constante), nos quais o modelo de otimização foi aplicado obedecendo às prescrições da Agência Nacional de Energia Elétrica - ANEEL. Em seguida, foi aplicado o modelo heurístico de otimização robusta resultando na demanda ótima contratada considerando todos os cenários propostos, no período de contrato determinado. Os resultados foram comparados com um método determinístico da demanda contratada em cada cenário, e mostraram que, com exceção de apenas um entre sete cenários, o modelo heurístico com a otimização robusta foi melhor que o modelo de contratação determinístico.

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 processo de produção, no ambiente da Construção Civil, é abordado segundo certos princípios gerenciais que absorvem conceitos vindo da Engenharia de Produção. Para obter a qualidade na produção, pelo critério competitivo que envolve prazos e confiabilidade de entrega, é fundamental a integração entre o projeto do produto e a produção através do projeto da produção. O processo de planejamento, no contexto do projeto da produção, requer o uso de ferramentas de suporte à tomada de decisão, fazendo da programação uma etapa essencial para o ganho de consistência deste processo decisório. A pesquisa trata da programação de projetos com limitação de recursos, a fim de encontrar uma boa solução para o problema de programação de forma simples e satisfatória. O método utiliza como ferramenta de apoio o software Microsoft Project para manipular os projetos com mais agilidade e flexibilidade, considerando as regras de prioridades que são usadas a depender dos critérios gerenciais adotados pelas empresas. O método é baseado na classe de procedimentos heurísticos: Job Oriented Heuristic Scheduling, já que o grau de prioridade dos projetos orienta o desenvolvimento da programação conjunta, denominada Programação multi-projetos. / The production process in the Civil Construction environment is approached according to some management principles that reinforce concepts from Production Engineering. To obtain Quality in production through the competitive criterion, which comprehends fast delivery time and on-time delivery, it is fundamental the integration between Product Design and production through Production Design. The planning process requires the use of procedures to support the decision-making process concerning global production systems in construction companies. Thus scheduling would be an essential stage for the acquisition of decision consistence. This dissertation deals with the resource-constrained Project Scheduling Problem using a heuristic method based on priority rules. Heuristic procedures are used to obtain a good solution to the problem in a practical and satisfactory way. The method uses Microsoft Project as a supporting tool to deal with the projects with more agility and flexibility. The priority rules are based on management criteria adopted by the companies. The method is based on the category of heuristic procedures known as Job Oriented Heuristic Scheduling, since the project priority degrees orient the steps of the multi-project scheduling.

La delincuencia es uno de los mayores problemas que hay en el Perú, especialmente, en Lima. En nuestra capital, el aumento de robos y delitos genera una gran preocupación ya que los policías no actúan rápido y no llegan a tiempo para impedir un robo o capturar ladrones. La situación actual es que las comisarías vigilan con sus patrullas los distritos sin considerar las zonas con mayor índice de criminalidad. Este criterio es de suma importancia pues puede ayudar a que los vehículos policiales velen por la seguridad de los ciudadanos de manera más estratégica. El presente proyecto contribuye ante esta problemática es desarrollar un sistema integral que permita la recepción de denuncias informales por medio de los ciudadanos y que genere, mediante un algoritmo que se retroalimente con los delitos registrados, una propuesta de distribución cercana a la óptima de vehículos policiales. La solución brindada por el sistema tiene como variables los datos propios de la comisaría, cantidad de vehículos, horarios y las frecuencias de los delitos con el fin de convertir la labor policial de manera proactiva. / Tesis

Orientador: Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Ciências da Computação, 2013

Este trabalho apresenta o desenvolvimento e a implementação computacional de um algoritmo para a localização de faltas em linhas de transmissão. O algoritmo proposto é baseado em métodos heurísticos, isto é, Algoritmos Genéticos (AG) e Pattern Search (PS), sendo capaz de identificar o ponto de ocorrência da falta utilizando fasores de tensão e corrente de pré e pós-falta, estimados a partir de medições disponíveis apenas no terminal local da linha de tranmsissão. Nesta abordagem, ambas as ferramentas de otimização possuem natureza heurísticas sendo menos propensas a cair em valores mínimos locais, o que implica uma maior eficiência e precisão na determinação da localização da falta. Além disso, o método utiliza potências de curto-circuito monofásicas e trifásicas de ambos os terminais da linha (local e remoto), a fim de obter seus equivalentes de Thévenin, e os parâmetros elétricos da linha de transmissão. Com o objetivo de avaliar o desempenho do algoritmo proposto, consideram-se nas simulações quatro sistemas de transmissão diferentes, que representam sistemas reais de transmissão brasileiros. O primeiro está constituído por uma típica linha de transmissão de 138 [kV] com circuito duplo, e os outros três sistemas são constituídos por linhas de transmissão típicas de 230, 500 e 765 [kV] com circuito simples. A partir dos quatro sistemas de transmissão simulados no software Alterative Transients Program (ATP/EMTP), foram gerados um total de 928 situações de falta. A versão do algoritmo desenvolvido para localização de faltas foram descritas e implementadas, através do software científico MATrix LABoratory (MATLAB), apresentando resultados com altos níveis de precisão. / This paper presents the development and implementation of a computational algorithm for location faults in transmission line. The proposed algorithm is based on heuristic methods, namely AG and PS, being able to identify the occurrence of the fault point using phasor voltage and current pre and post-fault, estimated from measurements available only on the local terminal of the transmission line. In this approach, both optimization tools have heuristic nature being less prone to falling into local minimum values, which implies grater efficiency and accuracy in the determination of fault location. Moreover, the method use singles-phase and three-phase short-circuit powers of both the line terminals (Local and remote), to obtain the Thévenin equivalent and the electrical parameters of the transmission line. In order to evaluate the performance of the proposed algorithm were considered four different transmission systems; these systems represent real systems of Brazilian transmission. The first this made up of a transmission line typical of 138 [kV] with double circuit, the other three systems are made up of transmission line typical of 230, 500 and 765 [kV] of single circuit. Whereas the four simulated transmission systems in the softwareATP/ EMTP, generated a total of 928 situations fault. The version of the algorithm designed to locate faults, have been described and implemented through scientific software MATLAB, presenting results high levels of accuracy.

Este trabalho apresenta o desenvolvimento e a implementação computacional de um algoritmo para a localização de faltas em linhas de transmissão. O algoritmo proposto é baseado em métodos heurísticos, isto é, Algoritmos Genéticos (AG) e Pattern Search (PS), sendo capaz de identificar o ponto de ocorrência da falta utilizando fasores de tensão e corrente de pré e pós-falta, estimados a partir de medições disponíveis apenas no terminal local da linha de tranmsissão. Nesta abordagem, ambas as ferramentas de otimização possuem natureza heurísticas sendo menos propensas a cair em valores mínimos locais, o que implica uma maior eficiência e precisão na determinação da localização da falta. Além disso, o método utiliza potências de curto-circuito monofásicas e trifásicas de ambos os terminais da linha (local e remoto), a fim de obter seus equivalentes de Thévenin, e os parâmetros elétricos da linha de transmissão. Com o objetivo de avaliar o desempenho do algoritmo proposto, consideram-se nas simulações quatro sistemas de transmissão diferentes, que representam sistemas reais de transmissão brasileiros. O primeiro está constituído por uma típica linha de transmissão de 138 [kV] com circuito duplo, e os outros três sistemas são constituídos por linhas de transmissão típicas de 230, 500 e 765 [kV] com circuito simples. A partir dos quatro sistemas de transmissão simulados no software Alterative Transients Program (ATP/EMTP), foram gerados um total de 928 situações de falta. A versão do algoritmo desenvolvido para localização de faltas foram descritas e implementadas, através do software científico MATrix LABoratory (MATLAB), apresentando resultados com altos níveis de precisão. / This paper presents the development and implementation of a computational algorithm for location faults in transmission line. The proposed algorithm is based on heuristic methods, namely AG and PS, being able to identify the occurrence of the fault point using phasor voltage and current pre and post-fault, estimated from measurements available only on the local terminal of the transmission line. In this approach, both optimization tools have heuristic nature being less prone to falling into local minimum values, which implies grater efficiency and accuracy in the determination of fault location. Moreover, the method use singles-phase and three-phase short-circuit powers of both the line terminals (Local and remote), to obtain the Thévenin equivalent and the electrical parameters of the transmission line. In order to evaluate the performance of the proposed algorithm were considered four different transmission systems; these systems represent real systems of Brazilian transmission. The first this made up of a transmission line typical of 138 [kV] with double circuit, the other three systems are made up of transmission line typical of 230, 500 and 765 [kV] of single circuit. Whereas the four simulated transmission systems in the softwareATP/ EMTP, generated a total of 928 situations fault. The version of the algorithm designed to locate faults, have been described and implemented through scientific software MATLAB, presenting results high levels of accuracy.

O processo de produção, no ambiente da Construção Civil, é abordado segundo certos princípios gerenciais que absorvem conceitos vindo da Engenharia de Produção. Para obter a qualidade na produção, pelo critério competitivo que envolve prazos e confiabilidade de entrega, é fundamental a integração entre o projeto do produto e a produção através do projeto da produção. O processo de planejamento, no contexto do projeto da produção, requer o uso de ferramentas de suporte à tomada de decisão, fazendo da programação uma etapa essencial para o ganho de consistência deste processo decisório. A pesquisa trata da programação de projetos com limitação de recursos, a fim de encontrar uma boa solução para o problema de programação de forma simples e satisfatória. O método utiliza como ferramenta de apoio o software Microsoft Project para manipular os projetos com mais agilidade e flexibilidade, considerando as regras de prioridades que são usadas a depender dos critérios gerenciais adotados pelas empresas. O método é baseado na classe de procedimentos heurísticos: Job Oriented Heuristic Scheduling, já que o grau de prioridade dos projetos orienta o desenvolvimento da programação conjunta, denominada Programação multi-projetos. / The production process in the Civil Construction environment is approached according to some management principles that reinforce concepts from Production Engineering. To obtain Quality in production through the competitive criterion, which comprehends fast delivery time and on-time delivery, it is fundamental the integration between Product Design and production through Production Design. The planning process requires the use of procedures to support the decision-making process concerning global production systems in construction companies. Thus scheduling would be an essential stage for the acquisition of decision consistence. This dissertation deals with the resource-constrained Project Scheduling Problem using a heuristic method based on priority rules. Heuristic procedures are used to obtain a good solution to the problem in a practical and satisfactory way. The method uses Microsoft Project as a supporting tool to deal with the projects with more agility and flexibility. The priority rules are based on management criteria adopted by the companies. The method is based on the category of heuristic procedures known as Job Oriented Heuristic Scheduling, since the project priority degrees orient the steps of the multi-project scheduling.