Metaheurísticas de busca local para o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência.
Nenhuma Miniatura disponível
Data
2014
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Este trabalho apresenta uma proposta e a avaliação computacional de quatro métodos
de busca local estocástica para o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência (UPMSP - unrelated parallel machine scheduling problem with sequence dependent setup times). As quatro abordagens metaheurísticas que são analisadas para o UPMSP baseam-se em: Simulated Annealing (SA), Iterated Local Search (ILS),
Late Acceptance Hill Climbing (LAHC) e Step Counting Hill Climbing (SCHC). A estrutura das vizinhancas, bem como os parâmetros dos algoritmos, foram amplamente testados e analisados, sendo possível verificar como os parâmetros afetam o comportamento de cada algoritmo implementado e pesquisar os melhores parâmetros. As comparações dos resultados obtidos foram realizadas com os resultados apresentados por Vallada e Ruiz (2011), proponentes do conjunto de 50 instâncias consideradas e, mais recentemente, por Haddad (2012). O método que obteve o melhor resultado nessas 50 instâncias foi testado para todas as 1.000 instâncias grandes, apresentadas por Vallada e Ruiz (2011), melhorando em 96,6% (966 instâncias) a melhor solução conhecida encontrada por esses últimos autores.
Descrição
Palavras-chave
Otimização combinatória, Simulated annealing, Processo sequencial - computação, Programação paralela - computação
Citação
SILVA, Cristiano Luís Turbino de França e. Metaheurísticas de busca local para o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência. 2014. 61 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Ouro Preto, Ouro Preto, 2014.