Problema de recobrimento de conjuntos com agrupamento: modelos e algoritmos
Fecha
2015-04-14Metadatos
Mostrar el registro completo del ítemResumen
Este trabalho aborda o problema de recobrimento de conjuntos com agrupamento, definido
como uma variante do problema de recobrimento de conjuntos clássico, na qual os conjuntos
estão dispostos em K agrupamentos disjuntos. São apresentadas duas aplicações práticas
para o problema encontradas na literatura. A primeira delas tem origem na engenharia elétrica,
especificamente no problema abordado por Fritzen et al (2012). Uma característica intrínseca
ao problema, levou à generalização da atribuição dos conjuntos aos agrupamentos, de forma
que a intersecção seja permitida. A segunda aplicação é oriunda da indústria de mineração e
devida a Bilal et al. (2014), que propõem um conjunto de instâncias e uma meta-heurística
baseada em iterated tabu search (ITS). Em se tratando de métodos de resolução, a primeira
contribuição apresentada neste trabalho consiste em uma formulação matemática com geração
de colunas para obtenção de limitantes superiores para as instâncias. Outras duas contribuições
se referem à meta-heurística ITS, sendo que a primeira consiste em uma abordagem paralela
para o componente de busca tabu, enquanto a segunda reside na adição de uma vizinhança resolvida
com programação inteira e que faz uso de hard variable fixing. A ideia subjacente ao
uso da vizinhança é ocupar o tempo economizado na paralelização com o aperfeiçoamento de
soluções promissoras obtidas pela busca tabu. Os resultados computacionais obtidos mostram
melhora na qualidade da solução para a ampla maioria das instâncias. Dada ainda a magnitude
dos custos envolvidos no problema, é possível concluir que o aprimoramento da meta-heurística
ITS com as sugestões deste trabalho pode ser de significativo benefício econômico.
Colecciones
El ítem tiene asociados los siguientes ficheros de licencia: