Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-20T17:51:30Z (GMT). No. of bitstreams: 0 / Neste trabalho é proposta uma análise entre o comportamento do algoritmo do Gradiente Projetado (GP), o qual é um algoritmo de enumeração de caminhos, e o algoritmo das Combinações Convexas (também conhecido como algoritmo de Frank-Wolfe), frente à resolução do Problema de Equilíbrio em Redes de Transporte. É também fornecida uma análise do Problema de Equilíbrio em Mercados, bem como a apresentação de um modelo matemático para resolvê-lo. Testes de aplicação dos algoritmos do GP e FW, são realizados em redes, geradas aleatoriamente, de vários tamanhos e carregamentos, a fim de comparar e avaliar as suas potencialidades frente à resolução do Problema de Equilíbrio em redes de transporte, apresentando e avaliando os resultados. As análises numéricas mostram que ambos os algoritmos são capazes de gerar bons resultados para resolver o problema aqui proposto, em tempo relativamente curto. Entretanto, o Método do Gradiente Projetado não apresenta problemas de convergência, enquanto que FW apresenta alguns casos de não convergência, gerando zig-zags. Sendo que, ainda pode-se salientar que as soluções fornecidas por GP são mais vantajosas por se resultarem distribuições baseadas em caminhos, ou seja, obtém-se variações de fluxo de arco a arco para cada caminho, proporcionando assim benefícios e oportunidades em certas aplicações. Algumas sugestões e considerações são apresentadas para o desenvolvimento de futuros trabalhos.

Made available in DSpace on 2014-06-11T19:26:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-10-26Bitstream added on 2014-06-13T19:33:57Z : No. of bitstreams: 1 silva_rt_me_guara.pdf: 445223 bytes, checksum: f6563e16194940a8f4f8abc7c03ac033 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / 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... / 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)

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.

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

Orientador: José Antonio Perrella Balestieri / Coorientador: João Andrade Carvalho Jr. / Banca: Ivonete Ávila / Banca: Christian Jeremi Coronado Rodriguéz / Resumo: Os gases siderúrgicos disponíveis em empresas do setor como resultado de seus principais processos de transformação são o gás de coqueria (COG), o gás de alto forno (BFG) e o gás de aciaria (LDG); que são bastante valorizados pelo fato de minimizarem a necessidade de emprego de gás natural ou outra fonte combustível. As centrais termelétricas estão entre as principais consumidoras desses combustíveis, e a distribuição de combustíveis siderúrgicos para as mesmas é um problema discutido na literatura técnica como uma forma de minimizar os desequilíbrios entre a geração e o consumo dos mesmos. Ao mesmo tempo, busca-se maximizar a eficiência energética da empresa e a confiabilidade/disponibilidade do seu suprimento às unidades consumidoras sem queima direta nas torres de queima (flares). A presente proposta de pesquisa tem por objetivo modelar e propor soluções para a otimização da distribuição de gases combustíveis em centrais termelétricas em ciclo combinado gás/vapor considerando os impactos que a troca de combustíveis operam sobre o acionador principal (no caso, o conjunto a gás) em termos de sua resposta à intercambiabilidade entre combustíveis. As modificações propostas neste trabalho otimizam simultaneamente a distribuição de gases subproduto no sistema de gases siderúrgicos; foram avaliadas 56 combinações de combustíveis, o que resultou numa faixa de potência ideal para a aplicação do estudo entre 30 MW e 80 MW, e outra faixa entre 10 MW e 30 MW que deve ser evitada quand... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The steel gases available in companies in the sector because of their main transformation processes are coke oven gas (COG), blast furnace gas (BFG) and steel gas (LDG). These are highly valued for minimizing the need to use natural gas or other fuel source. The thermoelectric power plants are among the main consumers of these fuels and the distribution of steel fuels for them is a problem discussed in the technical literature as a way to minimize the imbalances between generation and consumption. At the same time, it is a way to maximize the energy efficiency of the company and the reliability / availability of its supply to the consumer units without direct burning in the flares. The present research proposal aims to model and propose solutions for the optimization of the distribution of fuel gases in thermoelectric power stations in combined gas / steam cycle considering the impacts that the exchange of fuels operate on the main driver (in this case, the gas turbine) In terms of its response to interchangeability between fuels. The modifications proposed in this work simultaneously optimize the by-product gas distribution in the cogeneration gas system, 56 combinations of fuels were evaluated, which resulted in an ideal power range for the application of the study between 30,000 and 80,000 kW and another between 10,000 and 30,000 kW which should be avoided when the objective is positive net revenue. The case study shows that the proposed model finds the ideal solution in terms of total cost reduction when applying the COG in the NG mixture as well as in the substitution of NG by a mixture of by-products COG and BFG, which resulted in the three best net income results found in this analysis / Mestre