Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.

dc.contributor.advisorCarvalho, Marco Antonio Moreira dept_BR
dc.contributor.authorSoares, Leonardo Cabral da Rocha
dc.contributor.refereeCarvalho, Marco Antonio Moreira dept_BR
dc.contributor.refereeToffolo, Túlio Ângelo Machadopt_BR
dc.contributor.refereeArroyo, José Elias Claudiopt_BR
dc.date.accessioned2019-01-09T12:35:32Z
dc.date.available2019-01-09T12:35:32Z
dc.date.issued2018
dc.descriptionPrograma 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.pt_BR
dc.description.abstractO 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.pt_BR
dc.description.abstractenThe Identical Parallel Flexible Machines With Tooling Constraints Problem consists in scheduling tasks to a set of flexible parallel machines, with the objective of minimizing the maximum processing time of the tasks by the machines. Particularly, the tasks have the same processing time in any machine, however, they have a setup time which depends on the all of sequence of tasks scheduled on the same machine, owing to tool configurations on the flexible machine. In this work, this NP-Hard problem is addressed using a parallel Biased Random-Key Genetic Algorithm hibridized with local search procedures organized in a Variable Neighborhood Descent. Results for a set of 2,880 benchmark instances from the literature are presented for the first time, including optimal solutions for 12,31% among the smallest instances. The proposed method is compared with the state of-the-art method and achieves 91,81% of the best results. New best results are presented for 52,75% of the instances. Additionally, the proposed method is 91,69% faster than the compared method, thus dominating the current state-of-art.pt_BR
dc.identifier.citationSOARES, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/10616
dc.language.isopt_BRpt_BR
dc.rightsabertopt_BR
dc.rights.licenseAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 21/12/2018 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. Não permite o uso para fins comerciais nem a adaptação.pt_BR
dc.subjectMáquinas-ferramentapt_BR
dc.subjectAlgoritmos genéticospt_BR
dc.subjectProgramação heurísticapt_BR
dc.titleUma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.pt_BR
dc.typeDissertacaopt_BR
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
DISSERTAÇÃO_AbordagemEvolucionáriaProblema.pdf
Tamanho:
35.38 MB
Formato:
Adobe Portable Document Format
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
924 B
Formato:
Item-specific license agreed upon to submission
Descrição: