Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente.

Simple item page
dc.contributor.advisorToffolo, Túlio Ângelo Machadopt_BR
dc.contributor.advisorFonseca, George Henrique Godim dapt_BR
dc.contributor.authorFigueiroa, Guilherme Baumgratz
dc.contributor.refereeToffolo, Túlio Ângelo Machadopt_BR
dc.contributor.refereeFonseca, George Henrique Godim dapt_BR
dc.contributor.refereeCota, Luciano Perdigãopt_BR
dc.contributor.refereePenna, Puca Huachi Vazpt_BR
dc.date.accessioned2022-04-11T17:13:12Z
dc.date.available2022-04-11T17:13:12Z
dc.date.issued2021pt_BR
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 Sequenciamento em Máquinas Paralelas Não Relacionadas considera um conjunto de tarefas e um conjunto de máquinas homogêneas ou heterogêneas que trabalham em paralelo. Todas as tarefas do conjunto devem ser processadas, sendo necessário escolher em qual máquina cada tarefa será executada. O objetivo é escalonar as tarefas nas máquinas de forma a minimizar o tempo total necessário para executar todas as tarefas, conhecido como makespan, dado pela máquina com maior tempo de processamento. Este trabalho estuda um caso do problema em que as tarefas são independentes, as máquinas heterogêneas e existe um tempo de preparo para execução de cada tarefa, que pode variar dependendo da sequência das tarefas e da máquina. Os principais modelos matemáticos propostos para o problema foram avaliados utilizando o conjunto de instâncias apresentado por Vallada e Ruiz (2011). Dentre os modelos e métodos analisados, o modelo proposto por Avalos-Rosales et al. (2015) e o algoritmo exato proposto por Fanjul-Peyro et al. (2019) obtiveram os melhores resultados tanto em termos de qualidade de solução quanto em termos de tempo de processamento. Assim, com o intuito de abordar instâncias maiores do problema, este trabalho propõe o uso de heurísticas matemáticas Fix-And-Optimize que utilizando os principais modelos disponíveis na literatura. As metodologias propostas consistem em decompor de forma heurística o problema por meio da fixação de um conjunto de tarefas e máquinas. Cada fixação resulta em um subproblema que pode ser resolvido por um modelo matemático ou método exato. Duas variações do algoritmos foram avaliadas, usando os modelos de Avalos-Rosales et al. (2015) e Fanjul-Peyro et al. (2019). Os resultados computacionais mostram que ambos algoritmos propostos obtêm valores próximos do melhor conhecido na literatura. Foram obtidas, ainda, diversas soluções melhores do que a melhor conhecida até então. Dentre as duas abordagens propostas, o algoritmo que utiliza o método de Fanjul-Peyro et al. (2019) para resolver subproblemas obteve os melhores resultados, sendo capaz de obter soluções melhores do que a melhor da literatura para 338 das 1000 instâncias de grande porte consideradas.pt_BR
dc.description.abstractenThe Unrelated Parallel Machines Scheduling Problem considers a set of tasks and a set of homogeneous or heterogeneous machines that work in parallel. All tasks in the set must be processed, and it is necessary to choose on which machine each task will be executed. The objective is to schedule the tasks on the machines in order to minimize the total time needed to execute all the tasks, known as makespan, given by the machine with the most processing time. This work studies a case of the problem in which the tasks are independent, the machines are heterogeneous and there is a preparation time for the execution of each task, which can vary depending on the sequence of tasks and the machine. The main mathematical models proposed for the problem were evaluated using the set of instances presented by Vallada e Ruiz (2011). Among the models and methods analyzed, the model proposed by Avalos-Rosales et al. (2015) and the exact algorithm proposed by Fanjul-Peyro et al. (2019) obtained the best results both in terms of solution quality and in terms of processing time. Thus, in order to address larger instances of the problem, this work proposes the use of Fix-And-Optimize mathematical heuristics using the main models available in the literature. The proposed methodologies consist of heuristically decomposing the problem by setting a set of tasks and machines. Each fixation results in a sub-problem that can be solved by a mathematical model or exact method. Two variations of the algorithms were evaluated, using the models of Avalos-Rosales et al. (2015) and Fanjul-Peyro et al. (2019). The computational results show that both proposed algorithms obtain values close to the best known in the literature. In addition, several better solutions were obtained than the best known until then. Among the two proposed approaches, the algorithm that uses the Fanjul-Peyro et al. (2019) method to solve subproblems obtained the best results, being able to obtain better solutions than the best in the literature for 338 of the 1000 large instances considered.pt_BR
dc.identifier.citationFIGUEROA, Guilherme Baumgratz. Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente. 2021. 55 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, 2021.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/jspui/handle/123456789/14859
dc.language.isopt_BRpt_BR
dc.rightsabertopt_BR
dc.rights.licenseAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 06/04/2022 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.pt_BR
dc.rights.urihttp://creativecommons.org/licenses/by-sa/3.0/us/*
dc.subjectFix-and-optimizept_BR
dc.subjectHeurística matemáticapt_BR
dc.titleHeurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente.pt_BR
dc.typeDissertacaopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DISSERTAÇÃO_HeurísticaMatemáticasProblema.pdf
Size:
1.52 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PPGCC - Mestrado (Dissertações)