Um GRASP reativo para o problema de sequenciamento de máquinas paralelas não relacionadas com recurso escasso adicional
Carregando...
Data
2023-02-24
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Este trabalho aborda o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com recurso escasso adicional (Unrelated Parallel Machine Scheduling Problem with Secondary Resources – UPMR). Neste problema, um determinado conjunto de tarefas serão distribuídas em um conjunto de máquinas. O objetivo é minimizar o instante de conclusão da última tarefa (makespan). A cada instante de tempo existe uma quantidade máxima de recursos disponível para processar as tarefas do sequenciamento, cada tarefa demanda uma certa quantidade desse recurso ao ser processada. Caso o limite total de recurso seja ultrapassado, a solução se torna infactível. Para resolução do problema, propomos um algoritmo GRASP Reativo juntamente com um método de busca local VND. Um método guloso para o reparo de soluções infactíveis foi proposto e aplicado em conjunto com o GRASP Reativo. Um conjunto de instâncias da literatura é usado para a validação e comparação dos resultados. Análises realizadas com os resultados obtidos indicaram que a abordagem proposta obteve resultados satisfatórios em boa parte das instâncias em relação à abordagens existentes na literatura.
Descrição
Palavras-chave
Programação heurística, GRASP(Sistema operacional de computador), Alocação de recursos, Processamento paralelo (Computadores)