Use este identificador para citar ou linkar para este item: http://www.repositorio.ufop.br/jspui/handle/123456789/14859
Título: Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente.
Autor(es): Figueiroa, Guilherme Baumgratz
Orientador(es): Toffolo, Túlio Ângelo Machado
Fonseca, George Henrique Godim da
Palavras-chave: Fix-and-optimize
Heurística matemática
Data do documento: 2021
Membros da banca: Toffolo, Túlio Ângelo Machado
Fonseca, George Henrique Godim da
Cota, Luciano Perdigão
Penna, Puca Huachi Vaz
Referência: FIGUEROA, 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.
Resumo: O 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.
Resumo em outra língua: The 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.
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.
URI: http://www.repositorio.ufop.br/jspui/handle/123456789/14859
Licença: Autorizaçã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.
Aparece nas coleções:PPGCC - Mestrado (Dissertações)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DISSERTAÇÃO_HeurísticaMatemáticasProblema.pdf1,56 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons