Consideramos nesta dissertação um problema, NP-difícil, de seqüenciamento de padrões, vizando minimizar o número máximo de pilhas abertas em torno de uma máquina industrial de corte. Estamos interessados em métodos frugais, os quais, seguindo à terminologia de Halldórson (91), são aqueles - métodos - que além de utilizar poucos recursos computacionais - tempo e espaço - possuem idéias de implementações simples. A modelagem do problema pela Teoria dos Grafos foi a escolhida para obtenção de tais métodos, na tentativa de se identificarem aspectos estruturais que, porventura, pudessem emergir e auxiliar na sua resolução. A partir daquela modelagem, descobrimos ser o grafo complementar bastante esparso e possuidor de um conjunto independente maximal surpreendentemente grande, se comparado ao número de vértices do grafo. Através da informação adicional, fornecida por estes dois aspectos estruturais encontrados no grafo modelada, um método geral, baseado no clique maximal, foi desenvolvido. A frugalidade do método está no uso de uma conhecida heurística gulosa, de tempo linear no número de vértices, para detecção de conjuntos independentes. A partir do método geral, duas heurísticas puderam ser desenvolvidas: a primeira, de detecção de circuitos hamiltonianos, obtidos através de uma versão do algoritmo extensão-rotação para grafos randônicos, com o circuito inicial composto pelos vértices do clique maximal; e a segunda, de contratação recursiva de cliques. Realizamos testes computacionais comparando as nossas heurísticas com aquelas pertencentes ao estado da arte encontrado na literatura. Os resultados demonstram que as duas heurísticas desenvolvidas através do método proposto são competitivas, tanto em termos de tempo e espaço como de erro médio, além da facilidade de implementação.

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.

O crescente número de acidentes aeronáuticos, nas fases de decolagem e pouso das aeronaves, vem se tornando um grande desafio para a comunidade aeronáutica internacional na perseguição de novos meios e métodos de desmistificação das causas envolvidas. Este trabalho apresenta uma metodologia para a análise de investigações de acidentes aeronáuticos, baseada em técnicas heurísticas de tratamento das equações padronizadas da dinâmica do vôo das aeronaves para a restauração das trajetórias destas. O trabalho procura maximizar a coerência e a quantidade de informações sobre o desempenho das aeronaves e das tripulações envolvidas no meio ambiente operacional crítico, através dos parâmetros registrados pelo Gravador de Dados de Vôo (Flight Data Recorder - FDR) e pelo Gravador de Voz da Cabine do Comando (Cockpit Voice Recorder - CVR). A pesquisa restringe-se a aeronaves comerciais motorizadas, de asa fixa e a operações de vôo características, que ocorrem em áreas terminais, durante as fases de decolagem e pouso. A relevância deste trabalho enquadra-se na disponibilização, para as autoridades de investigação de acidentes aeronáuticos, de um protótipo de ferramenta, de fácil implementação, para análise dos principais grupos de fatores contribuintes nas investigações de acidentes aeronáuticos.

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.

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.

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