Banca de DEFESA: Rodney Oliveira Marinho Diana

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
DISCENTE : Rodney Oliveira Marinho Diana
DATA : 27/08/2021
HORA: 14:00
LOCAL: Videoconferência
TÍTULO:

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

PALAVRAS-CHAVES:

Sequenciamento de tarefas, Máquinas paralelas não relacionadas, Metaheurísticas, Sequenciamento Just-in-Time, Métodos de busca local.

PÁGINAS: 203
RESUMO:

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

MEMBROS DA BANCA:
Interna - ELISANGELA MARTINS DE SA
Interna - ELIZABETH FIALHO WANNER
Externo à Instituição - JOSE ELIAS CLAUDIO ARROYO
Externo à Instituição - LUIZ SATORU OCHI - UFF
Interno - MARCONE JAMILSON FREITAS SOUZA - UFOP
Externo ao Programa - MOACIR FELIZARDO DE FRANCA FILHO
Presidente - SERGIO RICARDO DE SOUZA