Made available in DSpace on 2014-06-11T19:28:35Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-02-24Bitstream added on 2014-06-13T19:37:19Z : No. of bitstreams: 1 elisei_jl_me_guara.pdf: 537523 bytes, checksum: 734f8ee50705919f4566cda9329f25fa (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O presente trabalho é fruto da observação de um problema real encontrado em uma indústria de autopeças, que produz peças estampadas em aço para caminhões, automóveis e tratores, utilizando prensas de alta capacidade. As prensas utilizadas necessitam de um ferramental, que precisa ser montado na prensa antes de começar a produção. Devido a esse fato, o setup de uma prensa pode variar de acordo com a sequência de produção que for realizada. Além disso, como o ferramental é único, quando uma peça está sendo produzida em uma prensa, outra peça que utilize o mesmo ferramental não poderá ser produzida em qualquer outra prensa. Neste trabalho procurou-se resolver o problema de programação da produção para esta indústria, que caracteriza-se como um problema de sequenciamento com máquinas paralelas e com tempo de setup dependente da sequência de produção. Para resolver tal problema, foram formulados alguns modelos matemáticos para obtenção de soluções exatas. No entanto, como trata-se de um problema de Otimização Combinatória NPdifícil, foi desenvolvido também um método heurístico híbrido utilizando as técnicas VND (Variable Neighborhood Descent) e ILS (Iterated Local Search) para a obtenção de soluções para grandes exemplares do problema em um tempo computacional razoável / The present work is based on a real world problem found in the auto parts industry, which produces steel stamped parts for trucks, cars and tractors, using highcapacity presses. The presses used need a tooling that has to be mounted on the press before production begins. Because of this, the setup of a press can vary according to the sequence of production that is performed. Moreover, as the tooling is unique for each type of auto part, when an auto part is being produced on a press, another auto part of the same type can not be produced in any other press. In this work one tried to solve the problem of production scheduling for a specific plant, which is characterized as a scheduling problem with parallel machines and sequence-dependent setup times. To solve this problem, some mathematical models were formulated to obtain exact solutions. However, as the problem is a NP-hard Combinatorial Optimization problem, a hybrid heuristic method was also developed, using the techniques VND (Variable Neighborhood Descent) and ILS (Iterated Local Search) to obtain approximate solutions for large problem instances in a reasonable execution time

Tese (Doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-18T17:16:54Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-09T02:26:47Z : No. of bitstreams: 1 138808.pdf: 2927189 bytes, checksum: 9cf1f9ccd1f27cd7bb89b20051cf1039 (MD5)

Orientador: Edson Luiz França Senne / Banca: Marcos Antonio Pereira / Banca: Antonio Augusto Chaves / Resumo: O presente trabalho é fruto da observação de um problema real encontrado em uma indústria de autopeças, que produz peças estampadas em aço para caminhões, automóveis e tratores, utilizando prensas de alta capacidade. As prensas utilizadas necessitam de um ferramental, que precisa ser montado na prensa antes de começar a produção. Devido a esse fato, o setup de uma prensa pode variar de acordo com a sequência de produção que for realizada. Além disso, como o ferramental é único, quando uma peça está sendo produzida em uma prensa, outra peça que utilize o mesmo ferramental não poderá ser produzida em qualquer outra prensa. Neste trabalho procurou-se resolver o problema de programação da produção para esta indústria, que caracteriza-se como um problema de sequenciamento com máquinas paralelas e com tempo de setup dependente da sequência de produção. Para resolver tal problema, foram formulados alguns modelos matemáticos para obtenção de soluções exatas. No entanto, como trata-se de um problema de Otimização Combinatória NPdifícil, foi desenvolvido também um método heurístico híbrido utilizando as técnicas VND (Variable Neighborhood Descent) e ILS (Iterated Local Search) para a obtenção de soluções para grandes exemplares do problema em um tempo computacional razoável / Abstract: The present work is based on a real world problem found in the auto parts industry, which produces steel stamped parts for trucks, cars and tractors, using highcapacity presses. The presses used need a tooling that has to be mounted on the press before production begins. Because of this, the setup of a press can vary according to the sequence of production that is performed. Moreover, as the tooling is unique for each type of auto part, when an auto part is being produced on a press, another auto part of the same type can not be produced in any other press. In this work one tried to solve the problem of production scheduling for a specific plant, which is characterized as a scheduling problem with parallel machines and sequence-dependent setup times. To solve this problem, some mathematical models were formulated to obtain exact solutions. However, as the problem is a NP-hard Combinatorial Optimization problem, a hybrid heuristic method was also developed, using the techniques VND (Variable Neighborhood Descent) and ILS (Iterated Local Search) to obtain approximate solutions for large problem instances in a reasonable execution time / Mestre

Resumo: A produção de grades horárias em instituições de ensino é uma tarefa complexa e de difícil solução, pois, neste contexto, existem muitas restrições necessárias à validade e aplicabilidade das respostas produzidas. Na literatura, a produção de grades horárias e, na verdade, uma das variações de timetabling, o qual, em essência, é um problema de escalonamento de eventos em um periodo finito de tempo, sujeito a restrições, como por exemplo, tempo, recursos humanos disponíveis (professores), recursos físicos existentes (salas de aula) e atividades a serem desenvolvidas (exames, aulas, entre outros). Para solucionar esse problema e automatizar o processo, abordagens de Inteligência Artificial têm sido aplicadas com sucesso, mais especificamente, os métodos da Computação Evolutiva. A computação evolutiva define uma classe de algoritmos que modelam computacionalmente os conceitos da teoria da Evolução de Charles Darwin. Esses algoritmos aplicam operadores genéticos sobre populações de indivíduos, visando à produção de indivíduos mais aptos que os antigos. Como resultado, obtêm-se indivíduos ou soluções candidatas com um alto grau de aptidão para solucionar um problema específico. O objetivo principal deste trabalho é estudar e implementar uma solução para o problema de Geração de Grades Horárias, com base na Computação Evolutiva. O método evolutivo escolhido é denominado Algoritmo Coevolutivo Cooperativo. Esse método subdivide um problema complexo em problemas menores, sendo que cada um deles é representado por uma população pertencente ao dominio do problema. Cada uma dessas populações possui características individuais e, no processo, todas evoluem paralelamente, de maneira cooperativa, por meio de sucessivas aplicações de operadores genéticos. Ao final do processo, os representantes de cada uma das populações formam, em conjunto, uma solução completa. Para verificar a validade do método para a resolução do problema em estudo, implementou-se um algoritmo cooperativo. Os resultados dos experimentos mostraram que algoritmos cooperativos são ferramentas poderosas, capazes de resolver problemas complexos de otimização numérica sujeitos a restrições.

Resumo: O Problema do Roteamento de Veículos Capacitados com Restrições Tridimensionais de Carregamento (3L – CVRP) é um recente avanço da pesquisa operacional para a resolução de problemas logísticos de alta complexidade. O interesse prático reside no transporte e distribuição de mercadorias de baixa densidade, cujo carregamento dos itens deve atender a restrições espaciais, como, eletrodomésticos, componentes mecânicos, móveis, entre outros. O 3L – CVRP também apresenta um grande desafio teórico na medida em que generaliza dois dos mais conhecidos problemas de otimização combinatória: O Problema do Roteamento de Veículos Capacitados e o Problema do Bin Packing Tridimensional. A solução do 3L – CVRP requer a determinação de rotas de menor custo para uma frota de veículos de mesma capacidade, de forma que se atenda a demanda de clientes dispersos em uma região. Tal demanda consiste em caixas retangulares que precisam ser carregadas atendendo a restrições operacionais. A resolução integrada implica na evocação iterativa de um método que resolve o problema do carregamento na medida em que o problema do roteamento vai sendo resolvido. Este trabalho apresenta uma nova abordagem para a resolução do 3L – CVRP. O método proposto resolve de forma heurística o problema do roteamento em dois estágios: o primeiro deles consiste em agrupar os clientes conforme sua demanda volumétrica enquanto que o segundo estágio constrói uma rota inicial refinando-a sequencialmente. O problema do carregamento é resolvido por um software comercial com licença trial. Foi desenvolvida uma nova estratégia para a integração entre os dois problemas baseada em limites de ocupação volumétrica do veículo. Os testes computacionais foram realizados em três etapas: Primeiramente avaliou-se o desempenho da heurística para o problema do roteamento de veículos capacitados. Testes foram realizados com instâncias clássicas da literatura e comparados com outras abordagens existentes (exatas e heurísticas), produzindo resultados satisfatórios tanto em termos de eficácia, quanto de eficiência. O segundo estágio de estes avaliou o software de carregamento para instâncias referentes ao problema de carregamento de contêineres e o problema do Bin Packing tridimensional. A comparação com outras abordagens existentes aponta um desempenho satisfatório do software. O terceiro e último estágio foi feito sobre instâncias do 3L – CVRP e comparadas com outros trabalhos existentes, produzindo resultados superiores em termos de eficácia para algumas instâncias, dependendo das configurações de restrição de carregamento, com melhorias em termos de eficiência para a grande maioria das instâncias testadas.

Orientadora: Ivanise Guilherme Branco / Banca: Cassia Roberta Malacrida Mayer / Banca: Izabel Cristina Freitas Moraes / Resumo: O alginato, presente na parede celular das algas marinhas pardas, apresenta coloração marrom, sendo necessário seu branqueamento para melhor aceitabilidade do mercado consumidor. O gás ozônio (O3) tem mostrado grande potencial de aplicabilidade como agente clareador mais sustentável. O presente estudo visa a otimização, utilizando a análise de superfície de resposta, dos parâmetros de clareamento (tempo, fluxo de oxigênio e temperatura), utilizando ozônio como agente branqueador, sobre os parâmetros colorimétricos (porcentagem de transmitância e índice de luminosidade), composição química (razão entre os ácidos manurônico (M) e gulurônico (G) M/G) e propriedades reológicas (viscosidade dinâmica, viscosidade intrínseca e massa molar) do alginato de sódio extraído de algas pardas (Sargassum spp.). Nas condições otimizadas de clareamento também foi verificada a influência da ozonização sobre a atividade antioxidante do alginato. O tempo é a variável independente que apresentou maior influência nas respostas, seguido da temperatura e fluxo de oxigênio. A condição otimizada encontrada foi um tratamento com fluxo de oxigênio de 2 L/min por 35 minutos à 25oC. A amostra clareada na condição otimizada apresentou capacidade antioxidante maior que a amostra comercial, indicando que o processo de clareamento por ozonização pode ser menos prejudicial aos compostos bioativos. Além disso, os antioxidantes naturais presentes no alginato de sódio aqui estudado podem agregar valor aos produtos que utilizam esse composto em preparações alimentícias / Abstract: Alginate is a polysaccharide which can be found in the cell wall of brown algae. Its original color is brown that is why a bleaching process is needed to improve this visual impairment. The ozone gas (O3) has shown a great potential as a more sustainable bleaching agent. The present study aims the optimization of bleaching parameters (time, oxygen flow rate and temperature) of sodium alginate from brown seaweeds (Sargassum spp.) using ozone gas as the bleaching agent on the colorimetrics parameters (percent transmittance and index of luminosity), chemical compositon (mannuronic (M) and guluronic (G) acid ratio M/G) and rheological properties (intrinsic viscosity, dynamic viscosity and molar mass). Once it was found the optimal conditions of bleaching, it was also verified the influence of ozonation on antioxidant activity of sodium alginate. The findings point out that ozonation time is the independent variable that most affects the responses, followed by the temperature and oxygen flow rate. The optimized bleaching conditions were determinated with an oxygen flow rate at 2 L/min, during 35 min at 25oC. The bleached sample on the optimized conditions presented a higher antioxidant capacity than the commercial sodium alginate sample, highlighting that the discoloration by ozone might be less harmful to bioactive compounds. Besides, natural antioxidants of sodium alginate can add value to products that use this compound in food preparations / Mestre

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 2013-07-16T01:31:20Z (GMT). No. of bitstreams: 1 223154.pdf: 452480 bytes, checksum: 32034bdd69509f5e45a87f49f8215540 (MD5) / A busca por soluções de problemas envolvendo otimização combinatorial tem sido motivo de estudos e pesquisas há muito tempo. Grande parte dos métodos propostos para a resolução de problemas desse tipo, que buscam soluções ótimas, está baseada em técnicas conhecidas como branch-and-bounds. Entretanto, o principal problema desse tipo de abordagem consiste no esforço computacional exigido. O tempo de computação necessário para a determinação de uma solução pode atingir níveis impraticáveis, tornando-os muitas vezes inviáveis em aplicações práticas. Como alternativa, atualmente, diversos métodos de aproximação estão sendo propostos. São abordagens que buscam soluções aceitáveis, próximas às soluções ótimas, porém, com tempos de processamento viáveis. Como exemplos típicos dessa abordagem podem ser citados os algoritmos das Formigas, Genéticos, Simulated Anneling, etc. Nesta dissertação é apresentado um novo algoritmo de aproximação que poderá ser empregado em problemas dessa natureza. Basicamente, o que está sendo proposto é a utilização do algoritmo Simulated Annealing em sua forma original, combinado com os operadores crossovers dos Algoritmos Genéticos. Além da hibridização dos algoritmos aludidos, também é explorada neste trabalho a potencialidade da paralelização dos mesmos em um ambiente multiprocessado. Na implementação e nos testes do modelo proposto foi utilizado o clássico Problema do Caixeiro Viajante que é um dos representantes desta classe de problema de otimização combinatorial, mais utilizados como benchmark.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2015-11-18T19:42:59Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_AnáliseOtimizaçãoProblema.pdf: 4135579 bytes, checksum: 6b71bbbade1f42caa848c5149be42bca (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-11-19T17:56:51Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_AnáliseOtimizaçãoProblema.pdf: 4135579 bytes, checksum: 6b71bbbade1f42caa848c5149be42bca (MD5) / Made available in DSpace on 2015-11-19T17:56:51Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_AnáliseOtimizaçãoProblema.pdf: 4135579 bytes, checksum: 6b71bbbade1f42caa848c5149be42bca (MD5) Previous issue date: 2015 / Para explorar a interseção entre problemas de roteamento de veículos propostos na literatura, esta dissertação propõe um problema de roteamento de veículos com muitos objetivos e janelas de tempo flexíveis (MOPRV). É proposta uma abordagem baseada em dois algoritmos evolucionários multiobjetivo (NSGA-II e NSGA-III) e um método para a redução e visualização de objetivos (Árvores de Agregação) é proposta. Através de um estudo sobre a harmonia e conflito entre os objetivos do problema, foi observada a possibilidade de agregação entre os mesmos, reduzindo o problema de seis para três objetivos. Os experimentos demonstram que as soluções para o problema reduzido possuem bons valores para todos os objetivos quando comparado com as soluções do problema completo. Mais ainda, os resultados demonstram que é mais vantajoso visualizar a relação entre os objetivos do MOPRV e em seguida otimizar o problema com menos objetivos do que tentar otimizar diretamente o problema considerando todos os objetivos do MOPRV. ____________________________________________________________________________________ / ABSTRACT: In order to explore the intersection between vehicle routing problems proposed in the literature, this dissertation proposes a many-objective vehicle routing problem with flexible time windows. We propose an approach based on two multiobjective evolutionary algorithms (NSGA-II and NSGA-III) and a method for reduction and visualization of objectives (Aggregation Trees). We observed the possibility of aggregation between the objectives through a study of the harmony and conflict between them, reducing the problem from six to three objectives. The experiments show the solutions for the reduced problem have good values for all objectives when compared to solutions for the complete problem. Moreover, the results show that it is more advantageous to visualize the relationship between objectives for the many-objective vehicle routing problem and then to optimize the reduced problem than to directly optimize the original formulation of the problem considering all six objectives.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Universidade Federal de Ouro Preto. / Submitted by giuliana silveira (giulianagphoto@gmail.com) on 2016-02-16T17:53:54Z No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2016-02-19T13:16:22Z (GMT) No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Made available in DSpace on 2016-02-19T13:16:22Z (GMT). No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) Previous issue date: 2015 / O presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos e heur ísticos, sequenciais e paralelos, para a resolu c~ao do problema da enumera c~ao de cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com vertices ponderados, onde o objetivo e encontrar todos os cliques maximais com peso acima de um limiar. Os algoritmos estudados neste trabalho são aplicados na separa ção de cortes no contexto de Programa ção Inteira. Encontrar todos os cliques acima de um dado peso e equivalente ao problema de encontrar todas as desigualdades violadas de clique. Foram desenvolvidas adapta ções em algoritmos conhecidos na literatura, para a resolução do problema. Para o algoritmo de Bron-Kerbosch, uma adapta c~ao foi realizada para resolver o PECPL. Al em disso, v arias melhorias foram propostas a m de melhorar a efi ciência na resolu ção das instâncias do problema. Foram propostas uma versão iterativa do algoritmo, originalmente recursivo, e uma versão paralela. O algoritmo de Ostergard e a heur stica busca tabu com multi-vizinhanças tamb ém foram implementados e modi ficados para re etir o problema abordado no presente trabalho. Por m, a metaheur stica Simulated Annealing foi proposta e desenvolvida utilizando-se das mesmas estruturas de vizinhan ca utilizadas na heur stica busca tabu com multivizinhanças. A diferen ça das duas t ecnicas est a na estrat égia de resolu ção do problema: enquanto a primeira utiliza-se do conceito de lista tabu, a ultima simula o processo de recozimento de metais. Nos experimentos computacionais, foram utilizadas 7292 instâncias, oriundas de quatro conjuntos referentes a separa ção de cortes em problemas formulados por meio do uso de programa c~ao inteira. Os experimentos foram conduzidos em duas partes: em um primeiro momento, as instâncias foram utilizadas para resolu ção do PECPL. Posteriormente, o foco foi a resolu ção do problema do clique de peso m áximo (PCPM). Quanto a resolu c~ao do PECPL, os resultados obtidos comprovam a efi ciência do algoritmo de Bron-Kerbosch, quando comparado aos demais algoritmos, ao encontrar a solu ção ótima para todas as instâncias e em um tempo consideravelmente menor do que as outras t ecnicas. Quando a an alise dos resultados foi direcionada a resolu c~ao do PCPM, todas as t écnicas implementadas obtiveram bons resultados, com destaque para a heur stica busca tabu com multi-vizinhan cas, a qual resolveu todas as instâncias de forma ótima, com o menor tempo computacional em rela c~ao as demais abordagens. Como trabalhos futuros, são sugeridos a ado c~ao de operadores l ogicos para a representa c~ao do grafo no algoritmo de Bron-Kerbosch, a melhoria da vers~ao paralela do algoritmo e o estudo do projeto das metaheurí sticas Simulated Annealing e busca tabu. __________________________________________________________________________________ / ABSTRACT : This work deals with the design, implementation and evaluation of exact and heuristic algorithms, sequential and parallel to the resolution of clique enumeration problem with weight above a threshold (PECPL). This problem considers a graph with weighted vertices, where the goal is to nd all maximal cliques with weight above a threshold. The algorithms studied in this work are applied in the separation cuts in the context of Integer Programming. Find all clique above a certain weight is equivalent to the problem of nding all the inequalities violated clique. Adaptations were developed algorithms known in the literature, to solve the problem. For the Bron-Kerbosch algorithm, an adaptation was made to solve the PECPL. In addition, several improvements were proposed in order to improve e ciency in the resolution of problem instances. It has been proposed an iterative version of the algorithm, recursive originally, and a parallel version. The Ostergard algorithm and multi-neighborhoods tabu search heuristic were also implemented and modi ed to re ect the problem addressed in this paper. Finally, the Simulated Annealing metaheuristic was proposed and developed using the same neighborhood structures used in multi-neighborhoods tabu search heuristic. The di erence of the two techniques is in solving strategy problem: while the rst is used the concept of tabu list, the last simulates the process of annealing of metals. In the computational experiments, we used 7292 instances, belonging to four sets related to the separation cuts in problems formulated by using integer programming. The experiments were conducted in two parts: at rst, the instances were used for solving the PECPL. Later, the focus was on resolving the maximum weight clique problem (PCPM). As for the resolution of the PECPL, the results prove the e ciency of Bron-Kerbosch algorithm, when compared to other algorithms to nd the optimal solution for all instances and in a considerably shorter time than the other techniques. When analyzing the results was directed to resolving the PCPM, all techniques implemented performed well, particularly the multi-neighborhoods tabu search heuristic, which solved all instances optimally with less computational time compared to other approaches. As future work, it is suggested the adoption of logical operators for the representation of the graph in Bron-Kerbosch algorithm, improved parallel version of the algorithm and the study design of simulated annealing and tabu search metaheuristics.

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-20T16:05:26Z (GMT). No. of bitstreams: 1 195928.pdf: 2356678 bytes, checksum: 164754abb834f5498d839239ae33e9d7 (MD5) / Problemas combinatorias são utilizados em muitas áreas de pesquisa, devido a sua simplicidade de compreensão e a sua aplicabilidade prática em vários domínios. Porém são intratáveis devido ao elevado tempo de processamento e de armazenamento de dados, sendo assim conhecidos e classificados como problemas NP-completos. Visando resolver estes problemas, diversos algoritmos têm sido propostos ao longo de vários anos de estudo, entre eles os Algoritmos Genéticos (AG) e o Algoritmo Simulated Annealing (SA). Estes algoritmos dão um tratamento polinomial aos problemas de otimização, buscando uma boa solução próxima a ótima em um tempo de processamento aceitável. Este trabalho concentra-se no estudo do AG e do SA aplicados ao clássico "Problema do Caixeiro Viajante". Propõe-se uma abordagem híbrida baseada no desenvolvimento do algoritmo SA em ambiente distribuído acrescido do operador "crossover" dos AG. A utilização em conjunto destas abordagens busca aumentar a potencialidade de obtenção de melhores resultados quando aplicados a problemas de otimização, sendo avaliado através de testes computacionais com instâncias públicas disponíveis via internet e instâncias construídas, também com suas soluções, conhecidas a priori.