CPU-GPU heuristics and cuts separation on MILP : analysis for the generalized assignment project scheduling problems.

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCoelho, Igor Machado-
Autor(es): dc.contributorPenna, Puca Huachi Vaz-
Autor(es): dc.contributorPenna, Puca Huachi Vaz-
Autor(es): dc.contributorCoelho, Igor Machado-
Autor(es): dc.contributorMoreira, Gladston Juliano Prates-
Autor(es): dc.contributorCarvalho, Marco Antonio Moreira de-
Autor(es): dc.contributorPinheiro, Rian Gabriel Santos-
Autor(es): dc.contributorSouza, Uéverton dos Santos-
Autor(es): dc.creatorSouza, Danilo Santos-
Data de aceite: dc.date.accessioned2025-08-21T15:31:47Z-
Data de disponibilização: dc.date.available2025-08-21T15:31:47Z-
Data de envio: dc.date.issued2024-11-07-
Data de envio: dc.date.issued2024-11-07-
Data de envio: dc.date.issued2023-
Fonte completa do material: dc.identifierhttps://www.repositorio.ufop.br/handle/123456789/18942-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1017532-
Descrição: dc.descriptionPrograma 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.-
Descrição: dc.descriptionNeste trabalho apresentamos abordagens inovadoras de para resolver problemas de otimização combinatória, combinando técnicas exatas e heurísticas e utilizando de recursos computacionais CPU-GPU. O foco principal está no Problema de Alocação Generalizada (PAG), no qual a alocação de tarefas à agentes deve ser realizada com recursos limitados minimizando os custos gerados por tal alocação. A proposta inicial aproveita dos recursos computacionais das Unidades de Processamento Gráfico (GPUs) para desenvolver um método que gera eficientemente um pool de soluções utilizando critérios da lista Tabu e um mecanismo de Cadeia de Ejeção, combinado com uma Busca no \textit{Pool} com Programação Binária (BPPB). Os resultados experimentais demonstram a competitividade dessa abordagem em relação aos algoritmos existentes na literatura. Além disso, realizamos várias investigações e experimentos computacionais para introduzir geradores de planos de corte inovadores. Esses geradores utilizam recursos computacionais CPU-GPU e são projetados para aprimorar resolvedores de Programação Linear Inteira Mista (PLIM), conforme descrito na literatura existente. Os resultados obtidos mostraram promissores quando aplicados a algumas instâncias do PSPLib e MIPLib, especialmente quando comparados com técnicas similares de resolvedores comerciais. Finalmente, discutimos as vantagens e desvantagens do uso de arquiteturas de computação paralela, bem como o uso de técnicas exatas e heurísticas para o Problema de Alocação Generalizada.-
Descrição: dc.descriptionThis thesis presents innovative optimization approaches, combining both exact and heuristic techniques while enjoying heterogeneous computational resources. It focuses primarily on the Generalized Assignment Problem (GAP), wherein the al- location of jobs to agents with limited resources aims to minimize costs. The initial proposal harnesses the substantial computational capabilities of Graphics Processing Units to devise a method efficiently generating a solution pool using Tabu list cri- teria and an Ejection Chain mechanism, combined with Binary Programming Pool Search (BPPS). Experimental findings demonstrate the competitiveness of this ap- proach against existing algorithms in the literature. Furthermore, we conducted several investigations and computational experiments to introduce novel cutting plane generators. These generators utilize heterogeneous resources and are designed to enhance MILP solvers as described in the existing literature. The results showed promise when applied to instances from the PSPLib and MIPLib, especially when compared with similar techniques from commercial solvers. Finally, we discuss the advantages and disadvantages of using parallel archi- tectures, as well as the use of exact and heuristic techniques for the Generalized Assgiment Problem.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsaberto-
Direitos: dc.rightsAttribution-NonCommercial-ShareAlike 3.0 United States-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-sa/3.0/us/-
Direitos: dc.rightsAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 30/10/2024 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais.-
Palavras-chave: dc.subjectGeneralized assignment problem-
Palavras-chave: dc.subjectCombinatorial optimization problems and metaheuristic-
Palavras-chave: dc.subjectCutting plane generators-
Título: dc.titleCPU-GPU heuristics and cuts separation on MILP : analysis for the generalized assignment project scheduling problems.-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.