Toffolo, Túlio Ângelo MachadoFonseca, George Henrique Godim daFigueiroa, Guilherme Baumgratz2022-04-112022-04-112021FIGUEROA, 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.http://www.repositorio.ufop.br/jspui/handle/123456789/14859Programa 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.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.pt-BRabertoFix-and-optimizeHeurística matemáticaDissertacaoAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 06/04/2022 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.