???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tede.ufam.edu.br/handle/tede/7593
???metadata.dc.type???: Dissertação
Title: Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
Other Titles: Hybridization exact and heuristic methods for minimizing weighted tardiness scheduling in parallel machines
???metadata.dc.creator???: Silva, Marcos Thomaz da 
???metadata.dc.contributor.advisor1???: Rodrigues, Rosiane de Freitas
???metadata.dc.contributor.referee1???: Amorim, Rainer Xavier de
???metadata.dc.contributor.referee2???: Carvalho, José Reginaldo Hughes
???metadata.dc.contributor.referee3???: Barreto, Raimundo da Silva
???metadata.dc.contributor.referee4???: Pio, José Luiz de Souza
???metadata.dc.description.resumo???: Nesta dissertação estão sendo apresentados os resultados da investigação realizada sobre problemas de escalonamento em máquinas paralelas, com foco na minimização do atraso ponderado total das tarefas, com tempos de processamento e prazos estimados de término arbitrários. Este é um problema clássico muito encontrado em indústrias, ambientes de produção e cenários onde o atraso na realização de tarefas ou produção pode gerar multas ou penalidades. A estratégia de resolução aplicada faz uso de um método híbrido exato-heurístico, onde a execução de um Algoritmo Genético fortemente baseado em Busca Local, denominado GLS, fornece um conjunto de soluções de ótimos locais para ser incorporado em uma formulação de programação linear inteira tri-indexada, otimizando o processo de resolução enumerativo implícito. Sendo a parametrização um problema inerente aos algoritmos genéticos e meta-heurísticas em geral, foi utilizada a ferramenta iRace para a otimização e definição de parâmetros. O solver IBM ILog CPLEX e a biblioteca dinâmica UFFLP foram utilizados para avaliar o conjunto de soluções obtido através das heurísticas utilizando a formulação de programação inteira. Os experimentos computacionais foram realizados em instâncias criadas com base no benchmark disponível na OR-Library com 40, 50, 100, 150, 200, 300 e 500 tarefas, em ambientes com 2, 4, 10 e 20 máquinas paralelas, obtendo resultados competitivos frente às melhores estratégias disponibilizadas na literatura, e apresentando a robustez do método em instâncias maiores.
Abstract: This dissertation presents the results of the investigation carried out on parallel machine scheduling problems, with focus on minimizing the total weighted tardiness of the jobs, with arbitrary processing times and deadlines. This is a classic scheduling problem that is often found in industries, production environments, and scenarios where delayed completion of jobs can lead to penalties. The applied resolution strategy makes use of an exact-heuristic hybrid method, where the execution of a strongly Local Search-based Genetic Algorithm, called GLS, provides a set of optimal location solutions to be incorporated in a tri-indexed integer linear programming formulation, optimizing the implicit enumerative resolution process. How the parameterization is an inherent problem in genetic algorithms and meta-heuristics in general, the iRace tool was used for optimization and parameter definition. The IBM ILog CPLEX solver and UFFLP dynamic library was used to evaluate the solution set obtained through heuristics using the integer linear programming formulation. The computational experiments were performed for instances created similar of the OR-Library with 40, 50, 100, 150, 200, 300 and 500 tasks in 2, 4, 10 and 20 parallel machines, obtaining competitive results against the best strategies available in the literature, and presenting the robustness of the method in larger instances.
Keywords: Algorítmos genéticos
Heurística
Programação linear
???metadata.dc.subject.cnpq???: CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
???metadata.dc.subject.user???: Algoritmos genéticos
Busca local
Heurísticas
Programação linear inteira
Escalonamento de tarefas
Language: por
???metadata.dc.publisher.country???: Brasil
Publisher: Universidade Federal do Amazonas
???metadata.dc.publisher.initials???: UFAM
???metadata.dc.publisher.department???: Instituto de Computação
???metadata.dc.publisher.program???: Programa de Pós-graduação em Informática
Citation: SILVA, Marcos Thomaz da. Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas. 2018. 112 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2019.
???metadata.dc.rights???: Acesso Aberto
???metadata.dc.rights.uri???: http://creativecommons.org/licenses/by-sa/4.0/
URI: https://tede.ufam.edu.br/handle/tede/7593
Issue Date: 17-Dec-2018
Appears in Collections:Mestrado em Informática

Files in This Item:
File Description SizeFormat 
Dissertação_MarcosSilva_PPGI.pdf2.84 MBAdobe PDFThumbnail

Download/Open Preview


This item is licensed under a Creative Commons License Creative Commons