Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente.
No Thumbnail Available
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
O Problema de Sequenciamento em Máquinas Paralelas Não Relacionadas considera um
conjunto de tarefas e um conjunto de máquinas homogêneas ou heterogêneas que trabalham
em paralelo. Todas as tarefas do conjunto devem ser processadas, sendo necessário escolher
em qual máquina cada tarefa será executada. O objetivo é escalonar as tarefas nas máquinas
de forma a minimizar o tempo total necessário para executar todas as tarefas, conhecido como
makespan, dado pela máquina com maior tempo de processamento. Este trabalho estuda um
caso do problema em que as tarefas são independentes, as máquinas heterogêneas e existe um
tempo de preparo para execução de cada tarefa, que pode variar dependendo da sequência
das tarefas e da máquina. Os principais modelos matemáticos propostos para o problema
foram avaliados utilizando o conjunto de instâncias apresentado por Vallada e Ruiz (2011).
Dentre os modelos e métodos analisados, o modelo proposto por Avalos-Rosales et al. (2015) e o
algoritmo exato proposto por Fanjul-Peyro et al. (2019) obtiveram os melhores resultados tanto
em termos de qualidade de solução quanto em termos de tempo de processamento. Assim, com
o intuito de abordar instâncias maiores do problema, este trabalho propõe o uso de heurísticas
matemáticas Fix-And-Optimize que utilizando os principais modelos disponíveis na literatura.
As metodologias propostas consistem em decompor de forma heurística o problema por meio
da fixação de um conjunto de tarefas e máquinas. Cada fixação resulta em um subproblema
que pode ser resolvido por um modelo matemático ou método exato. Duas variações do
algoritmos foram avaliadas, usando os modelos de Avalos-Rosales et al. (2015) e Fanjul-Peyro
et al. (2019). Os resultados computacionais mostram que ambos algoritmos propostos obtêm
valores próximos do melhor conhecido na literatura. Foram obtidas, ainda, diversas soluções
melhores do que a melhor conhecida até então. Dentre as duas abordagens propostas, o
algoritmo que utiliza o método de Fanjul-Peyro et al. (2019) para resolver subproblemas
obteve os melhores resultados, sendo capaz de obter soluções melhores do que a melhor da
literatura para 338 das 1000 instâncias de grande porte consideradas.
Description
Programa 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.
Keywords
Fix-and-optimize, Heurística matemática
Citation
FIGUEROA, Guilherme Baumgratz. Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente. 2021. 55 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2021.