Orientador : Prof. Dr. Cassius Tadeu Scarpin / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 10/02/2017 / Inclui referências : f.86-94 / Resumo: Nesse trabalho, aplicou-se uma estratégia baseada na heurística relax-and-fix como método de solução para o Problema de Roteamento em Arcos Capacitado e Periódico (Periodic Capacitated Arc Routing Problem - PCARP). Considerou-se o caso especial em que os veículos não têm a necessidade de voltar ao depósito no final de um período e, ainda, têm a possibilidade de folgar em qualquer dia do horizonte de tempo. O PCARP é um problema pouco explorado na literatura. Configura-se como um problema NP-hard, sendo comumente aplicado em coleta de resíduos urbano, inspeção de linhas de força, despejo de sal em vias com neve, monitoramento de rodovias, inspeção de ferrovias, irrigação de árvores entre outros. Desenvolveu-se 5 estratégias diferentes para heurística relax-and-fix e uma variação denominada enhanced relax-and-fix avaliando-se seus desempenhos. Os testes computacionais realizados indicaram que as estratégias propostas para heurística são rápidas na determinação de soluções iniciais para o problema estudado. Destaca-se que das 23 instâncias testadas em nenhum caso se esgotou a memória do computador, fato que ocorre com frequência na tentativa de resolver o problema por métodos exatos. Palavras-chave: Relax-and-Fix. Problema de Roteamento em Arcos Capacitado e Periódico. Heuristica. Relaxation Induced Neighborhood Search. / Abstract: On this research it was applied a strategic solution approach based on the heuristic relax-and-fix for the Periodic Capacitated Arc Routing Problem (PCARP). A special case was considered on which the vehicles do not need to return to a depot when finishing the route. In addition there is the possibility of some vehicles that do not work in any day during the time horizon. The PCARP is not so explored in the literature. It is a NP-Hard Problem, usually applied in urban waste collection, inspection of power lines, winter gritting, road monitoring, inspection of railroads and watering trees. To tackle the problem, it was developed five different strategies for the relax-and-fix heuristic and one variation named enhanced relax-and-fix. All these approaches had their performance evaluate and the computational results show that they are fast to find initial solutions. It is important to highlight that the solver, while running, did not stop by running out of memory, this fact frequently occurs when solving this problem by exact methods. Key-words: Relax-and-Fix. Periodic Capacitated Arc Routing Problem. Heuristic. Relaxation Induced Neighborhood Search.

Resumo: O problema da geração de padrões de corte bidimensionais é um importante problema de otimização combinatória, e tem forte representatividade em diversos setores da indústria, como por exemplo os setores moveleiro, têxtil, de produção de vidro e papel. Tal problema pode ser formulado como um Problema da Mochila Bidimensional, cujo objetivo consiste em encontrar o melhor arranjo de itens a ser cortado a partir de um objeto, a fim de que sejam minimizadas as sobras e conseqüentemente o custo com material. Considera-se neste estudo que o corte seja regular, portanto trata-se de itens e objetos retangulares. Este trabalho apresenta uma estratégia de resolução para a geração de padrões de corte bidimensionais com corte do tipo guilhotinado, no qual o mesmo se estende de um lado ao outro do objeto. Foram considerados dois diferentes tipos de padrões de corte: padrões não-estagiados e padrões em dois estágios, e trabalhou-se ainda com a possibilidade de rotação dos itens, caracterizando ao todo quatro abordagens para a resolução do problema. A metodologia proposta subdivide-se em duas etapas: primeiramente utilizam-se Algoritmos Genéticos para a seleção e agrupamento dos itens em subconjuntos, e então aplica-se uma técnica de encaixe para criar o arranjo geométrico dos mesmos, sendo que o corte não-estagiado possui uma técnica de encaixe baseada no algoritmo construtivo de Wang (1982), enquanto no corte em dois estágios utiliza-se uma heurística de encaixe seqüencial dos itens. O método proposto foi testado sobre instâncias da literatura, para quatro abordagens distintas, que são: corte não-estagiado sem rotação de itens, corte não-estagiado com rotação de itens, corte em dois estágios sem rotação de itens, e corte em dois estágios com rotação de itens; e os resultados obtidos foram comparados com as soluções ótimas conhecidas. Tais resultados foram satisfatórios, pois o método gerou padrões de corte com um aproveitamento médio do objeto entre 90 e 95%, num tempo computacional reduzido e praticamente instantâneo para algumas instâncias testadas.

Resumo: A técnica de radioterapia tem sido uma das principais alternativas para o tratamento de diversos tipos de câncer na atualidade. Com o desenvolvimento tecnológico, principalmente tratando-se da radioterapia conformacional 3D, diversos cenários antes contraindicados, hoje são aceitáveis e recomendados. Um tratamento considerado adequado é aquele que permite com que a dose prescrita pelo médico chegue ao tumor de maneira que afete o mínimo possível os tecidos nobres e saudáveis. Desta forma, na fase do planejamento da radioterapia, problemas de otimização multiobjetivo aparecem. Este trabalho apresenta um modelo de programação multiobjetivo para o problema da intensidade de dose, que foi resolvido por método exato por meio do software MATLAB R2009b, utilizando a metodologia da função ponderada. Duas situações foram desenvolvidas, uma figurativa com efeito de melhor compreensão da metodologia utilizada, e outra utilizando dados reais, contando com apoio do Hospital Erasto Gaertner, Curitiba-PR. As fronteiras de Pareto, mostraram a importância do especialista decisor, que deve escolher entre uma dose mais próxima da prescrita, mesmo prejudicando os tecidos nobres e saudáveis, ou então proteger ao máximo os tecidos nobres e saudáveis, relaxando a dose necessária para destruir o tumor. Além disso, para comparação, foram realizados testes considerando a heterogeneidade dos tecidos irradiados e sem considerá-los, mostrando que pode existir uma diferença grande entre a dose emitida dependendo do tipo de tecido da região atingida por radiação.U

Resumo: Regras de operação de reservatórios são importantes para a gestão de recursos hídricos. Várias técnicas de otimização têm sido aplicadas para obter métodos efecientes de operação de reservatórios, entretanto, um método eficiente ainda se faz necessário devido a complexidade de um sistema de reservatórios, especialmente os de pequenas dimensões. Neste trabalho, um método de otimização melhorado, baseado em Enxame de Partículas, é apresentado. As melhorias envolvem o uso de um algoritmo que única os dois esquemas do algoritmo de Enxame de Partículas em um único, sem comprometer o desempenho computacional. É adotada a combinação do coeficiente de constrição ao coeficiente de inércia para o controle da velocidade das partículas. Uma nova abordagem da variação da inércia _e utilizada para melhorar o desempenho do algoritmo. O algoritmo proposto _e aplicado ao problema de otimização diária do planejamento de geração de pequenas centrais hidrelétricas, através de um modelo simplificado de otimização, que utiliza penalização da função objetivo para lidar com as restrições não lineares do problema. Esta abordagem mostrou boa performance e obteve resultados promissores, quando comparada ao algoritmo de Enxame de Partículas padrão e a outras técnicas heurísticas, como o Recozimento Simulado, por exemplo.

Made available in DSpace on 2015-09-17T15:24:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-08-13. Added 1 bitstream(s) on 2015-09-17T15:48:23Z : No. of bitstreams: 1 000846659.pdf: 263878 bytes, checksum: 594979ca4ad458c27d2f2ff121025ca7 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho apresenta uma sequência de atividades voltadas ao ensino de Análise Combinatória utilizando a Geometria do Táxi, que é uma geometria capaz de modelar as trajetórias, dos cidadãos e dos veículos que se deslocam entre quarteirões, ao longo dos eixos de ruas e avenidas. Estas atividades foram aplicadas a um grupo de alunos do Ensino Médio, tendo como recurso didático um jogo e usando como metodologia a Resolução de Problemas. A intenção foi proporcionar aulas que fujam daquela velha rotina de uma metodologia tradicional onde somente são envolvidos os recursos como giz, quadro ou livro didático, buscando atrair mais a atenção dos alunos e conectar o ensino de Matemática ao cotidiano deles / This work presented a sequence of activities which aim at teaching of Combinatorial Analysis using the Taxicab Geometry, a geometry that is able of modeling the trajectories, of citizens and vehicles moving on blocks, along the axis of streets and avenues. These activities have been applied to a group of High School students, having as a teaching resource a game and using the Problem Solving methodology. The intention was to purpose lessons to flee that old routine of a traditional methodology where the resources are only involved as chalk, blackboard or textbook, trying to attract more students' attention and connect teaching of Mathematics to them life

Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

Resumo: Este trabalho aborda a implementação paralela da técnica Branch-and-Bound em problemas de otimização combinatoria, especificamente busca em grafos. E utilizado na implementação o modelo de programação paralela por troca de mensagens com o uso da biblioteca Parallel Virtual Machine (PVM) sobre o sistema operacional Linux em uma arquitetura multicomputador. E analisado o comportamento da técnica Branch-and-Bound, em particular a relação entre (a) três critérios de busca, (b) a utilização dos recursos de memória e (c) granularidade de, processamento e comunicação entre processos. E proposto um esquema de implementação com processos mestre-escravos semi-distribuído, onde o processo mestre é responsável pela distribuição de tarefas e os processos escravos pela disseminação de resultados parciais no sistema. Resultados experimentais dessa implementação são exibidos e analisados, assim como algumas características relevantes ao desempenho global encontradas no uso da biblioteca PVM para esta arquitetura. De um modo geral obtivemos em média para os problemas investigados uma eficiência da execução paralela da ordem de 98% em comparação à execução serial.

Resumo: Esta dissertação aborda uma proposta de metodologia de resolução de um problema de entregas que abrange a integração de dois problemas clássicos de Otimização Combinatória: o Problema de Carregamento de Container (PCC) e o Problema de Roteamento de Veículos (PRV). O problema específico analizado está na logística empregada no carregamento e entrega de eletrodomésticos (linha branca) vendidos à pessoa física. Para representar esta situação, assume-se um cenário fictício em que a empresa que vende os produtos possui um Centro de Distribuição de Produtos (CD) localizado na cidade de Curitiba e uma lista de doze possíveis produtos a serem vendidos. A partir desta lista foram gerados 160 pedidos diferentes para serem entregues em vinte endereços aleatórios localizados também na cidade de Curitiba. Para a resolução deste problema, apresenta-se uma metodologia baseada em formação de torres de caixas e um Algoritmo Bottom-Left para realizar o carregamento dos pedidos no compartimento de carga dos veículos e um Algoritmo Genético para realizar a otimização evolutiva da solução até que se encontre uma solução suficientemente próxima à solução ótima do problema, buscando diminuir, a cada geração, a distância total percorrida pelos veículos de entrega. Para demonstração e utilização desta metodologia, apresenta-se uma implementação dos algoritmos e técnicas de pesquisa operacional descritos acima para a resolução desenvolvida em linguagem de programação Microsoft Visual Basic. Utilizando-se esta implementação e o cenário construído para testes, obteve-se bons resultados em relação à distância total percorrida pelos veículos de entrega, com redução de 25% a 45% em relação às soluções iniciais aleatórias, sendo que em alguns casos, esta melhoria alcançou até 60%.

Orientador: Galeno José de Sena / Banca: Marcos Antonio Pereira / Banca: Anibal Tavares de Azevedo / Resumo: A Organização Internacional do Trabalho estima que existem cerca de 650 milhões de pessoas com deficiência em idade produtiva. No entanto, esta parcela da população possui altos índices de desemprego devido a várias barreiras. Uma alternativa para facilitar a inclusão dessas pessoas é a criação de Centros de Trabalho para pessoas com Deficiência (CTD's) onde as pessoas com deficiência tenham a oportunidade de experimentar um ambiente de trabalho real antes de irem para um emprego "normal". Neste tipo de ambiente, onde é impossível ao gestor prever quais trabalhadores estarão disponíveis a cada dia devido às altas taxas de absenteísmo, há a necessidade de se definir uma organização mais produtiva diariamente. Neste contexto se torna oportuna a utilização do Problema de Balanceamento de Linha e Designação de Trabalhadores (em inglês ALWABP), onde se busca minimizar o tempo de ciclo a partir de um dado número de trabalhadores, alocando tarefas às estações de trabalho e trabalhadores às estações, tendo em vista que alguns trabalhadores podem ser muito lentos para executar certas tarefas ou até incapazes, devido a alguma deficiência que eles apresentam, e muito eficientes na execução de outras. O objetivo geral desta dissertação consiste em empregar diferentes meta-heurísticas para resolver o ALWABP, comparando com os melhores resultados das instâncias encontradas na literatura. Dentre várias meta-heurísticas disponíveis na literatura foram utilizados o Harmony Search (HS), o Adaptive Large Neighborhood Search (ALNS) e o Clustering Search (CS) utilizando o HS e o ALNS como heurísticas geradoras de soluções. Cada uma das quatro implementações foram testadas em 320 instâncias propostas na literatura divididas em quatro famílias. Os experimentos computacionais mostraram bons resultados... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The International Labour Organization estimates that there are approximately 650 million disabled people in working age. However, this population presents high rates of unemployment due to numerous barriers. An alternative to facilitate the inclusion of these people is the establishment of Centers for Working People with Disabilities where people with disabilities have the opportunity to experience a real work environment before going to a "normal" job. In this type of environment, where it is impossible to predict which workers will be available each day due to high rates of absence in this population, there is a need to define a more productive organization on a daily basis. In this context it becomes appropriate to use the Assembly Line Worker Assignment and Balancing Problem (ALWABP), which seeks to minimize the cycle time for a given number of workers, assigning tasks to workstations and workers to stations, considering that some workers may be too slow to perform certain tasks, or even unable due to some deficiency they present, and very efficient in performing others. The aim of this dissertation is to employ different meta-heuristics to solve the ALWABP, comparing with the best results of instances found in the literature. Among several meta-heuristics available in the literature were used Harmony Search (HS), Adaptive Large Neighborhood Search (ALNS) and Clustering Search (CS) using the HS and ALNS as heuristics for the generation of solutions. Each of the four implementations has been tested in 320 instances proposed in the literature, classified into four families. The computational experiments showed good results, and in some instances obtaining better solution values best known. Conclusions regarding... (Complete abstract click electronic access below) / Mestre

Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.