Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.
Nenhuma Miniatura disponível
Data
2018
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
O Problema de Escalonamento de Tarefas em Máquinas Flexíveis Paralelas Idênticas com
Restrições de Ferramentas, consiste em alocar tarefas a um conjunto de máquinas flexíveis
paralelas, com o objetivo de minimizar o tempo máximo de processamento das tarefas
pelas máquinas. Especificamente, as tarefas possuem tempo de processamento igual em
qualquer máquina, porém, possuem tempo de preparo prévio que depende de todas as
tarefas anteriores sequenciadas na mesma máquina, devido a configurações de ferramentas
nas máquinas flexíveis. Neste trabalho, este problema NP-Difícil é abordado utilizando-se
a metaheurística paralela Algoritmo Genético de Chaves Aleatórias Viciadas hibridizada
com procedimentos de busca local organizados em uma Descida em Vizinhança Variável.
São apresentados resultados inéditos para um conjunto de 2880 instâncias da literatura,
incluindo resultados ótimos para 12,31% entre as menores instâncias. O método proposto é
comparado ao atual estado da arte e obtém 91,81% das melhores soluções. Novas melhores
soluções são apresentadas para 52,75% do total de instâncias. Adicionalmente, o método
proposto apresenta tempo de execução 92,69% menor, dominando assim o atual estado da
arte.
Descrição
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.
Palavras-chave
Máquinas-ferramenta, Algoritmos genéticos, Programação heurística
Citação
SOARES, Leonardo Cabral da Rocha. Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas. 2018. 88 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, 2018.