Projeto e análise de métodos computacionais para problemas de sequenciamento de tarefas em ambientes de máquinas paralelas não relacionadas

Página do item simplificado
dc.contributor.advisorSouza, Sérgio Ricardo de
dc.contributor.advisor-coWanner, Elizabeth Fialho
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/2243256075052322
dc.contributor.advisorLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.authorDiana, Rodney Oliveira Marinho
dc.contributor.authorLatteshttp://lattes.cnpq.br/5802108825109375
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeWanner, Elizabeth Fialho
dc.contributor.refereeOchi, Luiz Satoru
dc.contributor.refereeArroyo, José Elias Claudio
dc.contributor.refereeFrança Filho, Moacir Felizardo de
dc.contributor.refereeSá, Elisângela Martins de
dc.contributor.refereeSouza, Marcone Jmailson Freitas
dc.date.accessioned2025-04-16T13:13:09Z
dc.date.available2025-04-16T13:13:09Z
dc.date.issued2022-08-27
dc.description.abstractEsta tese estuda uma importante classe de problemas de scheduling, denominada sequenciamento de tarefas em máquinas paralelas não relacionadas com tempos de preparação dependentes da sequência e das máquinas. Para isto, é realizada uma minuciosa revisão bibliográfica, que identifica três lacunas na literatura: (i) pouca importância é dada à construção e, principalmente, à validação de componentes utilizados em métodos de busca local e, assim, não há informações suficientes para se determinar padrões que podem potencializar a construção de operadores de busca local; (ii) as metaheurísticas construídas para resolução dos problemas incorporam muitas características dos critérios de otimização no processo de busca, dificultando a adaptação destas a critérios de otimização com pouca visibilidade teórica; (iii) não são encontrados estudos para problemas que envolvam o sequenciamento guiado por uma política Just-in-Time (JIT), considerando janelas de tempo. Esta tese tem como principal objetivo apresentar três estudos a respeito dessas lacunas. No primeiro estudo é proposta uma metodologia para o projeto de operadores de busca local de metaheurísticas. Esta metodologia é avaliada em três metaheurísticas propostas previamente na literatura. O estudo mostra que a utilização da metodologia leva a um incremento significativo nas três metaheurísticas avaliadas, inclusive encontrando resultados superiores às abordagens de estado da arte para o problema avaliado. Além disto, através das análises dos componentes de busca local, foram encontrados padrões que podem ser usados para construção de operadores de busca local em outros cenários. Já o segundo estudo é destinado à construção de uma abordagem metaheurística híbrida para a classe de problemas de sequenciamentos avaliada nesta tese. A abordagem reduz o uso de características do critério de otimização no processo de busca. Ao mesmo tempo, a abordagem não reduz a qualidade dos resultados encontrados, quando comparada a abordagens projetadas especificamente para um critério de otimização. Neste estudo é mostrado, através de quatro estudos de caso, que a abordagem proposta encontra, na maior parte dos cenários avaliados, resultados superiores ou similares às abordagens de estado da arte. Por fim, realizamos um estudo a respeito da importância e dificuldade do projeto de metaheurísticas para a classe de problemas estudados, quando guiados por uma política JIT, permitindo a inserção de tempos ociosos em conjunto com janelas de tempo. Neste estudo é proposto adaptar, para máquinas paralelas não relacionadas, um método de inserção ótima de tempos ociosos para ambientes de máquina única. Este método acarreta em incremento significativo da ordem de complexidade das abordagens. Devido a isto, é proposto um método de busca local com estruturas de vizinhança reduzidas. Os métodos propostos são integrados a quatro metaheurísticas previamente propostas na literatura e à metaheurística híbrida proposta nesta tese. É avaliado como as metaheurísticas se comportam para resolução do problema. Os resultados mostram que a metaheurística híbrida apresenta resultados superiores às demais abordagens na maior parte dos cenários avaliados. Além disto, é avaliado qual a influência do tamanho das janelas de tempo nos resultados advindos do sequenciamento. Os resultados indicam a existência de uma correlação linear entre o tamanho da janela de tempo com os custo advindos dos atrasos e avanços das tarefas.
dc.description.abstractotherThis thesis addresses an important class of scheduling problems named unrelated parallel machines with sequence and machine-dependent setup times scheduling problems. Firstly, a literature review is performed, which raises three gaps: (i) the contribution of components used in local search has received little attention in the metaheuristics convergence validation. Consequently, there is little qualitative information to determine patterns that can enhance the construction of local search operators; (ii) the implemented metaheuristics for solving the scheduling problems incorporate many features of the own optimization criteria in the search process. As a result, these implemented metaheuristics are hard to adapt to the optimization criteria with little theoretical visibility; (iii) the literature review did not found studies for the class of scheduling problems under study guided by a Just-in-Time (JIT) policy considering time windows. This thesis has as main objective to present three contributions regarding these gaps. In the first study, a methodology for the local search operators design for metaheuristics is proposed. This methodology is evaluated in three metaheuristics previously proposed in the literature. The study shows that the use of the proposed methodology leads to a significant increase in the performance of the metaheuristics. The redesigned metaheuristics even outperform the state-of-theart approaches for the evaluated problem. Furthermore, through the analysis of the local search components, some patterns were found that can be used to build localsearch operators in other scenarios. The second study is aimed at building a hybrid metaheuristic approach to the evaluated scheduling problem. This approach must reduce the use of optimization criteria features in the search process. At the same time, the approach must found results with the same quality of the state-of-the-art approaches designed for a specific optimization criterion. It is shown, using four case studies, that the proposed approach finds superior or similar results to the state-of the-art approaches in most of the evaluated scenarios. Finally, we conducted a study about the importance and difficulty of the design of metaheuristics for the studied problems class, when guided by a Just-in-Time policy, allowing the insertion of idle times together with time windows. In this study, it is proposed to adapt, for unrelated parallel machines, a method of optimal insertion of idle times in single-machine environments. This method entails a significant increase in the order of complexity of the metaheuristics approaches. For this reason, a local search method is proposed with reduced neighborhood structures. The proposed methods are integrated into four metaheuristics previously proposed in the literature and to the hybrid metaheuristic proposed in this thesis. The metaheuristics behaviors are evaluated to the problem solution. The results show that the hybrid metaheuristic outperforms the four other approaches in most of the evaluated scenarios. Furthermore, the influence of the size of the time windows on the scheduling results is evaluated. The results indicate the existence of a linear correlation between the size of the time window and the costs arising from jobs earliness and tardiness.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1226
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectProgramação heurística
dc.subjectControle de qualidade
dc.subjectPesquisa operacional
dc.subjectModelos matemáticos
dc.titleProjeto e análise de métodos computacionais para problemas de sequenciamento de tarefas em ambientes de máquinas paralelas não relacionadas
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Projeto e análise de métodos computacionais para problemas de sequenciamento de tarefas em ambientes de máquinas paralelas não relacionadas.pdf
Tamanho:
7.32 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional