Hibridização de métodos exatos e heurísticos para resolução de problemas de otimização combina

• Ano de defesa: 2011
• Autor(a) principal: Stefanello, Fernando
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Santa Maria; BR; Ciência da Computação; UFSM; Programa de Pós-Graduação em Informática
• Palavras-chave em Português: Metaheurísticas híbridas; Problema das p-medianas capacitado; Problema de programação máquinas paralelas não relacionadas; Vizinhança de grande porte; Hybrid metaheuristics; Capacitated p-median problem; Unrelated parallel machine scheduling problem; Large-scale neighborhood; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.ufsm.br/handle/1/5378

The 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.