Defesa de Mestrado de Luciano Perdigão Cota; 14/07/2014, as 10:00, Sala de Seminários.

Defesa de Mestrado de Luciano Perdigão Cota; 14/07/2014, as 10:00, Sala de Seminários do DECOM, ICEB III.

Banca: Prof. Dr. Marcone Jamilson Freitas Souza; Prof. Dr. Alexandre Xavier Martins; Prof. Dr. Frederico Gadelha Guimarães; Prof. Dr. José Elias Cláudio Arroyo.

Título: NOVOS ALGORITMOS PARA O PROBLEMA DE SEQUENCIAMENTO EM MÁQUINAS PARALELAS NÃO-RELACIONADAS COM TEMPOS DE PREPARAÇÃO DEPENDENTES DA SEQUÊNCIA

Resumo: Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas Não-
Relacionadas com Tempos de Preparação Dependentes da Sequência  UPMSPST, objetivando minimizar o makespan. Para resolvê-lo foram desenvolvidos três algoritmos heurísticos e um algoritmo híbrido. O primeiro algoritmo heurístico, denominado HIVP, tem uma solução inicial gerada por um procedimento construtivo parcialmente guloso baseado no Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time  ASPT. Essa solução é, posteriormente, re-
nada pelo procedimento Iterated Local Search  ILS, tendo o Random Variable Neighborhood Descent como método de busca local. Além disso, periodicamente a busca é intensicada e diversicada por meio de um procedimento Path Relinking PR. No segundo algoritmo heurístico, denominado GIAP, a solução inicial é criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solução é renada por um procedimento ILS que utiliza como método de busca local o procedimento Adaptive Local Search  ALS. A busca é também intensicada e diversicada por meio de um procedimento PR. O terceiro e último algoritmo heurístico, denominado AIRP, tem sua solução inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solução é renada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma análoga aos algoritmos anteriores, a busca
também passa por uma intensicação e diversicação periodicamente por meio de um procedimento PR. O algoritmo híbrido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heurístico AIRP, diferindo deste por acrescentar um módulo de programação linear inteira mista. Para a aplicação desse módulo são selecionados um par de máquinas e subconjuntos de tarefas nessas máquinas. Esses subconjuntos são combinados e passam por uma busca local que consiste em acionar um resolvedor de programação matemática aplicado à melhor das formula-
ções de programação matemática dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi possível concluir que o AIRP obteve os melhores resultados dentre os algoritmos heurísticos propostos, conseguindo superar vários outros algoritmos da literatura. Também foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRM necessita de um tempo maior para acionar o módulo de programação matemática, esses experimentos utilizaram um tempo maior de execução. Observou-se, no entanto, que a adição do módulo de
programação matemática não melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes também mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo é capaz de encontrar melhores soluções.