Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-20T07:26:10Z (GMT). No. of bitstreams: 1 186337.pdf: 495102 bytes, checksum: 2077bc80ca3d164d6934ab5544ad87c6 (MD5) / A busca de soluções para problemas de otimização das informações nas organizações por meio do computador constituiu a base deste trabalho. No que tange à Ciência da Computação, essa busca certamente requer a construção de algoritmos eficientes e exatos, mas nem sempre encontram-se boas soluções para muitos problemas de ordem prática, principalmente no que diz respeito ao tempo de execução. Existem problemas, dentre os quais estão os de otimização combinatorial, que diferem dos outros porque apresentam uma grande dificuldade para se obter soluções exatas, num tempo computacional aceitável. Existem técnicas, especialmente as metaheurísticas, tais como Tabu Search, Simulated Annealing, Algoritmos Genéticos e Redes Neurais, que vêm conseguindo sucesso na solução de problemas de otimização combinatorial e, mesmo não apresentando soluções exatas, têm mostrado bastante eficiência com suas soluções aproximadas. Este trabalho propõe um novo método, baseado no algoritmo Simulated Annealing (SA), modificado para trabalhar com múltiplas faixas de temperatura, de forma que os processos são executados de forma paralela, trocando informações de seus melhores resultados entre os processos existentes a cada início de uma nova faixa. Os experimentos são executados com instâncias euclidianas do Problema Caixeiro Viajante, que é um problema de otimização combinatorial de difícil solução, apresentando resultados bastante satisfatórios quando comparado com o SA de múltiplas faixas, executado de forma seqüencial

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-18T06:08:41Z (GMT). No. of bitstreams: 1 250657.pdf: 450883 bytes, checksum: 0da3746d8dd41bb89849d2e66115f5fa (MD5) / Atualmente observa-se uma forte tendência em se utilizar métodos aproximados na resolução de problemas de otimização combinatorial. Esses métodos, que muitas vezes vêm em substituição a métodos exatos, nem sempre garantem uma solução ótima para um problema, porém, normalmente são capazes de oferecer solução aproximada de boa qualidade, em um tempo de processamento aceitável. Neste trabalho é apresentada e investigada uma nova proposta de um método de aproximação baseado na combinação dos algoritmos Genético (AG) e Simulated Annealing (SA). Na observação do seu comportamento foi utilizado o notório problema de otimização combinatorial, de complexidade NP-completo, conhecido como o Problema do Caixeiro Viajante (PCV).

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-18T13:35:55Z (GMT). No. of bitstreams: 1 225675.pdf: 796704 bytes, checksum: 892abc8468e4e7c6715b6c3f2de50e51 (MD5) / A busca por soluções de problemas por meio do computador é o tema central da ciência da computação, relevante para grande parte da ciência e de suas aplicações tecnológicas. Essa busca, certamente, vai na direção de algoritmos eficientes e exatos mas que nem sempre boas soluções podem ser encontradas para muitos problemas de ordem prática, principalmente, no que diz respeito a tempo de execução. Existem problemas, dentre estes, os de otimização combinatorial que apresentam uma peculiaridade com relação aos outros, que é a grande dificuldade de se obter soluções exatas num tempo computacional aceitável. Atualmente, as novas técnicas, especialmente as metaheurísticas, tais como: Tabu Search, Simulated Annealing, Algoritmos Genéticos e Redes Neurais, vêm conseguindo sucesso na solução de problemas de otimização combinatorial, que mesmo não apresentando soluções exatas têm mostrado bastante eficiência com suas soluções aproximadas. Este trabalho propõe um novo método baseado no algoritmo Simulated Annealing (SA) através de mudanças bruscas nos valores da temperatura que são retiradas de múltiplas faixas, ao contrário do SA básico, onde esses valores são obtidos de uma faixa única, ou seja, num SA básico, os valores assumidos pela temperatura saem de um intervalo, partindo de um valor inicial, e vão diminuindo até um valor final. Tais mudanças bruscas acontecem exatamente no momento da mudança de faixa, pois o valor da temperatura que no final de uma faixa é pequeno, assume um valor correspondente a temperatura inicial da faixa seguinte, normalmente, bem maior. Posto a prova, com instâncias euclidianas do Problema Caixeiro Viajante, que é um problema de otimização combinatorial de difícil solução, o método apresenta resultados bastante satisfatórios quando comparado com o SA básico.

Made available in DSpace on 2014-11-10T11:09:53Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-30Bitstream added on 2014-11-10T11:57:47Z : No. of bitstreams: 1 000790195.pdf: 918459 bytes, checksum: 01e8141c5483f5a04a86fdd9a1917ef1 (MD5) / O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP’s optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time

Resumo: O Particle Swarm Optimization (PSO) pertence a uma classe de algoritmos inspirados em comportamentos sociais naturais inteligentes, chamada Swarm Intelligence (SI). O algoritmo PSO tem sido aplicado com sucesso na resolução de problemas de otimização contínua, no entanto, o seu potencial em problemas discretos não foi suficientemente explorado. Trabalhos recentes têm proposto a implementação de PSO usando algoritmos de busca local e Path relinking com resultados promissores. Este trabalho tem como objetivo apresentar um algoritmo PSO como um meta-modelo que utiliza internamente busca local e Path relinking, mas diferentemente das abordagens anteriores, o algoritmo proposto mantém o conceito principal de PSO para a atualização da velocidade da partícula. O trabalho descreve o algoritmo proposto como uma plataforma geral para problemas combinatórios. Tal proposta é validada em duas implementações: uma aplicada ao Problema do Caixeiro Viajante e outra ao Problema da Mochila. As peculiaridades e uma série de experimentos de calibragem de ambos os algoritmos são relatados. Finalmente, a qualidade do algoritmo proposto é testada na comparação com outros PSO discretos da literatura recente e também com outro conhecido algoritmo de metaheurística: o Ant Colony Optimization (ACO). Os resultados são encorajadores e reforçam a idéia de que o algoritmo PSO também pode ser competitivo em espaço de busca discreto, assim como levam a crer que a utilização de métodos dependentes do problema pode ser uma excelente alternativa na aplicação de PSO a este tipo de problema.

Orientador: Maria do Socorro Nogueira Rangel / Banca: Maristela Oliveira dos Santos / Banca: Valeriano Antunes de Oliveira / Resumo: O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / Abstract: The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP's optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time / Mestre

Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-21T13:12:10Z (GMT). No. of bitstreams: 1 Rodrigues_RosianedeFreitas_M.pdf: 9358851 bytes, checksum: aa44aaf61d515209c1ff85e92e7915a9 (MD5) Previous issue date: 1996 / Resumo: Times Assíncronos (do inglês Asynchronous Teams ou A-Teams) constituem uma abordagem multi-algorítmica para a resolução aproximada de problemas, cujo princípio básico é a cooperação sinérgica entre um conjunto de algoritmos, que se comunicam assincronamente através de memórias compartilhadas, propiciando soluções de melhor qualidade do que as geradas pelos mesmos algoritmos quando executados isoladamente. Este método tem sido aplicado com sucesso em problemas combinatórios com uma única função objetivo. O presente trabalho apresenta Times Assíncronos como sendo adequado à resolução de problemas de otimização combinatória com múltiplas funções objetivo. Diferentes estratégias para a manipulação de soluções multidimensionais foram desenvolvidas, tornando possível a rápida obtenção de soluções próximas ou mesmo pertencentes ao Pareto Ótimo do problema. Em especial, foi desenvolvida uma estrutura de manipulação de soluções multidimensionais que possibilita a consideração simultânea de todos os objetivos envolvidos para a geração de soluções. É proposto um novo problema NP-dificil como uma generalização do clássico Problema do Caixeiro Viajante (do inglês Traveling Salesman Problema ou TSP), onde ao invés de apenas uma matriz de distância existem múltiplas matrizes, sendo intitulado Problema do Caixeiro Viajante com Múltiplas Distâncias (do inglês Multi-Distance Traveling Salesman Problem ou MDTSP) e ao qual foi aplicado o método de Times Assíncronos. Os testes computacionais foram realizados de forma concorrente e paralela, obtendo-se conjuntos de soluções não-dominadas bem distribuídas dentro de uma ampla faixa de valores fornecidos pelas funções objetivo envolvidas, para todas as instâncias, mesmo envolvendo várias dimensões. Isto demonstra que os melhores conjuntos de soluções não-dominadas gerados pelos AT eams foram numerosos e contiveram soluções significativamente distintas entre s~ abrangendo todo o espectro desejado. Para as menores instâncias foi possível constatar que o melhor conjunto de soluções não-dominadas obtido fora o próprio Pareto Otimo. Ainda, foram desenvolvidos algoritmos para o novo problema que incorporam conceitos adequados a problemas multiobjetivos / Abstract: Asynchronous Teams or A-Teams constitute a mu1ti-algorithm approach for approximated problem solving, whose basic principle is the sinergic cooperation among a set of algorithms that communicate asynchronously through shared memories, providing solutions of better quality than those generated by the same algorithms when executed separately. This method has been successfully applied to Combinatorial Optimization Problems with a single objective function. This work presents Asynchronous Teams as an adequated method to solving Combinatorial Optimization Problems with multiple objective junctions. Different strategies to the manipulation of multi-dimensional solutions were developed, allowing it possible to obtain near-optimal or Pareto Optimal solutions quickly. In special, was developed a structure for multidimensional solution manipulation that allowing it possible the simultanea consideration of all objectives involved to the solution generation. It is proposed a new NP-hard problem as a generalization of classic Traveling Salesman Problem or TSP, which, instead of only one distance matrix, has various matrices. It has been entitled of Multi-Distance Traveling Salesman Problem or MDTSP and to which was applied the Asynchronous Teams method. The implementation tests were accomplished in a concurrent and parallel way, obtaining set of non-dominated solutions well-distributed on a wide range of values provided by the objective functions involved, over the tested instances. This demonstrates that the best sets of non-dominated solutions obtained are numerous and contain solutions significantly distinct among them. To the small instances was possible to show that the best set of non-dominated solutions generated was the Pareto Optimal. Algorithms have been developed for the new problem with the incorporation of compromisse decision and dominance concepts. Still, were developed algorithms to the new problem that incorpore adequated concepts to multiobjective problems / Mestrado / Mestre em Ciência da Computação

Orientador : Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-01T22:11:51Z (GMT). No. of bitstreams: 1 Garcia_ViniciusJacques_M.pdf: 1139020 bytes, checksum: 17565f60e3c310bc25176ac8734a07b6 (MD5) Previous issue date: 2002 / Mestrado

[pt] A dissertação estuda o problema do sequenciamento de uma única máquina com tempos de preparação dependentes da sequência da produção e penalidades por antecipação e atraso. Ilustra um método com uma aplicação a um exemplo de processo de fabricação por usinagem. Dessa forma, pretende-se reunir as metodologias de resolução e os trabalhos existentes na literatura sobre o Problema do Sequenciamento e aplicar ao caso específico de um dos Processos de Fabricação mais comuns existentes na indústria. / [en] The dissertation studies the single machine scheduling problem with sequence dependent setup times, with earliness and tardiness penalties, applied to an example of Machining Process Manufacturing. Thus, it is intended to collect the methodologies of resolution and main studies in the literature about the Problem of Sequencing and apply to the specific case of one of the most common manufacturing processes existing in the industry.

Made available in DSpace on 2016-05-17T16:51:22Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-08-14. Added 1 bitstream(s) on 2016-05-17T16:54:57Z : No. of bitstreams: 1 000863325_20170814.pdf: 1379523 bytes, checksum: db1556043273e4889e27702a2bf223ce (MD5) Bitstreams deleted on 2017-08-18T12:37:07Z: 000863325_20170814.pdf,. Added 1 bitstream(s) on 2017-08-18T12:37:52Z : No. of bitstreams: 1 000863325.pdf: 2314226 bytes, checksum: 152290accc1d5181a771e05181b739cf (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / A Pesquisa Operacional se tornou uma aliada de diversos problemas reais, principalmente de problemas da indústria, cujo objetivo é minimizar seus custos. Um dos problemas de muitos gestores é determinar quanto produzir, quando produzir e em que ordem produzir. Para responder essas três perguntas simultaneamente é têm-se que resolver o problema integrado de dimensionamento de lotes e sequenciamento da produção. O presente trabalho vem trazer modelos matemáticos que podem ser adaptados em diversos estudos de casos para responder a questão tríplice: quanto, quando e em que ordem, tudo isso, minimizando os custos de estoque, atraso e troca. A tese responde a seguinte pergunta, até então uma lacuna na literatura, entre os modelos que integram dimensionamento e sequenciamento da produção, qual é o melhor? Cinco modelos foram propostos e estudados do ponto de vista teórico e computacional para então descobrir o melhor. A construção dos modelos foi baseada no artigo de Oncam et al. (2009) que apresenta resultados teóricos e computacionais para mostrar qual o melhor modelo para o problema do caixeiro viajante. Esperava-se que os resultados fossem similares. Porém, o melhor modelo para o problema integrado de dimensionamento de lotes e sequenciamento da produção é diferente do melhor modelo para o problema do caixeiro viajante / Operational Research has become an ally of several real problems, especially problems of industry, whose objective is to minimize their costs. One of the problems of many managers is to determine how much to produce, when to produce and in what order produce. To answer these three questions simultaneously simply solve the integrated problem of lot sizing and sequencing of production. This work presents mathematical models that can be adapted in several case studies to answer the threefold question: how much, when and in what order, all while minimizing inventory costs, delay and return. This thesis is interested on the question, What is the best model for the integrate lot sizing and scheduling problem?. ItWere proposed five models and theys were studied in the theoretical and computational viewpoint. All models was based in the travelling salesman problem (TSP). And the results show that the integrate lot sizing and scheduling problem based in the TSP isn't the same model for the TSP / FAPESP: 2010/19006-0