Mostrar registro simples

dc.creatorStefanello, Fernando
dc.date.accessioned2011-11-18
dc.date.available2011-11-18
dc.date.issued2011-03-04
dc.identifier.citationSTEFANELLO, Fernando. Hybridization of exact and heuristic methods to solve combinatorial optimization problem. 2011. 88 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Santa Maria, Santa Maria, 2011.por
dc.identifier.urihttp://repositorio.ufsm.br/handle/1/5378
dc.description.abstractThe evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches.eng
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior
dc.formatapplication/pdfpor
dc.languageporpor
dc.publisherUniversidade Federal de Santa Mariapor
dc.rightsAcesso Abertopor
dc.subjectMetaheurísticas híbridaspor
dc.subjectProblema das p-medianas capacitadopor
dc.subjectProblema de programação máquinas paralelas não relacionadaspor
dc.subjectVizinhança de grande portepor
dc.subjectHybrid metaheuristicseng
dc.subjectCapacitated p-median problemeng
dc.subjectUnrelated parallel machine scheduling problemeng
dc.subjectLarge-scale neighborhoodeng
dc.titleHibridização de métodos exatos e heurísticos para resolução de problemas de otimização combinapor
dc.title.alternativeHybridization of exact and heuristic methods to solve combinatorial optimization problemeng
dc.typeDissertaçãopor
dc.description.resumoA recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.por
dc.contributor.advisor1Müller, Felipe Martins
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/5941686828835081por
dc.contributor.referee1Gendreau, Michel
dc.contributor.referee2Santos, José Vicente Canto dos
dc.contributor.referee2Latteshttp://lattes.cnpq.br/3054875168089226por
dc.creator.Latteshttp://lattes.cnpq.br/0922268140311827por
dc.publisher.countryBRpor
dc.publisher.departmentCiência da Computaçãopor
dc.publisher.initialsUFSMpor
dc.publisher.programPrograma de Pós-Graduação em Informáticapor
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor


Arquivos deste item

Thumbnail

Este item aparece na(s) seguinte(s) coleção(s)

Mostrar registro simples