Metaheurísticas para a minimização do atraso total no problema de sequenciamento em máquinas paralelas com divisão de tarefas

• Ano de defesa: 2013
• Autor(a) principal: Oliveira Júnior, Paulo Lúcio de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa; BR; Metodologias e técnicas da Computação; Sistemas de Computação; Mestrado em Ciência da Computação; UFV
• Palavras-chave em Português: Sequenciamento em máquinas paralelas; Atraso total; GRASP; Algoritmo genético; Simulated Annealing; Busca tabu; Busca local; Path Relinking; Sequencing on parallel machines; Total tardiness; GRASP, Genetic Algorithm; Tabu Search; Local Search; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://locus.ufv.br/handle/123456789/2653

Este trabalho aborda o problema de escalonar n tarefas independentes em m máquinas paralelas idênticas com o objetivo de minimizar o atraso total das tarefas. Assume-se que uma tarefa possa ser dividida em sub-tarefas e estas possam ser processadas independentemente nas máquinas paralelas idênticas. Este problema é considerado NP-difícil, o que significa que, encontrar a solução ótima para este problema, levará um tempo computacional não aceitável. Por tal razão, métodos alternativos, como heurísticas, são utilizados para que boas soluções sejam obtidas em tempo razoável. Algumas heurísticas baseadas nas metaheurísticas GRASP (Greed Randomized Adaptive Search procedure) e no Algoritmo Genético são propostas. Além disso, três regras de dominâncias são utilizadas para melhorar as soluções. São comparados os resultados destes algoritmos com os resultados de outros dois algoritmos propostos na literatura.