Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas

Silva, Marcos Thomaz da; http://lattes.cnpq.br/1710397494828508; https://orcid.org/0000-0001-7621-2411

Dissertação

Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas

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...

ver descrição completa

Autor principal:	Silva, Marcos Thomaz da
Outros Autores:	http://lattes.cnpq.br/1710397494828508, https://orcid.org/0000-0001-7621-2411
Grau:	Dissertação
Idioma:	por
Publicado em:	Universidade Federal do Amazonas 2020
Assuntos:	Algorítmos genéticos Heurística Programação linear CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Algoritmos genéticos Busca local Heurísticas Programação linear inteira Escalonamento de tarefas
Acesso em linha:	https://tede.ufam.edu.br/handle/tede/7593

id	oai:https:--tede.ufam.edu.br-handle-:tede-7593
recordtype	dspace
spelling	oai:https:--tede.ufam.edu.br-handle-:tede-75932020-01-07T05:03:43Z Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas Hybridization exact and heuristic methods for minimizing weighted tardiness scheduling in parallel machines Silva, Marcos Thomaz da Rodrigues, Rosiane de Freitas http://lattes.cnpq.br/1710397494828508 http://lattes.cnpq.br/8358219976594707 Amorim, Rainer Xavier de http://lattes.cnpq.br/6851610498599368 Carvalho, José Reginaldo Hughes http://lattes.cnpq.br/3161958119304780 Barreto, Raimundo da Silva http://lattes.cnpq.br/1132672107627968 https://orcid.org/0000-0001-7621-2411 Algorítmos genéticos Heurística Programação linear CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Algoritmos genéticos Busca local Heurísticas Programação linear inteira Escalonamento de tarefas 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. 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. . Sistema apresentou erros em 2 ou 3 ocasiões, mas retomando o processo voltou a funcionar normalmente. Foram utilizados nos experimentos instâncias disponibilizadas no site http://algox.icomp.ufam.edu.br/ 2020-01-06T18:34:03Z 2018-12-17 Dissertação 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. https://tede.ufam.edu.br/handle/tede/7593 por Acesso Aberto http://creativecommons.org/licenses/by-sa/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática
institution	TEDE - Universidade Federal do Amazonas
collection	TEDE-UFAM
language	por
topic	Algorítmos genéticos Heurística Programação linear CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Algoritmos genéticos Busca local Heurísticas Programação linear inteira Escalonamento de tarefas
spellingShingle	Algorítmos genéticos Heurística Programação linear CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Algoritmos genéticos Busca local Heurísticas Programação linear inteira Escalonamento de tarefas 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
topic_facet	Algorítmos genéticos Heurística Programação linear CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Algoritmos genéticos Busca local Heurísticas Programação linear inteira Escalonamento de tarefas
description	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.
author_additional	Rodrigues, Rosiane de Freitas
author_additionalStr	Rodrigues, Rosiane de Freitas
format	Dissertação
author	Silva, Marcos Thomaz da
author2	http://lattes.cnpq.br/1710397494828508 https://orcid.org/0000-0001-7621-2411
author2Str	http://lattes.cnpq.br/1710397494828508 https://orcid.org/0000-0001-7621-2411
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
title_short	Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
title_full	Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
title_fullStr	Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
title_full_unstemmed	Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
title_sort	hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
publisher	Universidade Federal do Amazonas
publishDate	2020
url	https://tede.ufam.edu.br/handle/tede/7593
_version_	1831969835002626048
score	11.753735

Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas

Registros relacionados