15/02 - 10h - Defesa de Mestrado - Matheus Nohra Haddad

Defesa de Dissertação

Título: "Algoritmos Heurísticos Híbridos para o Problema de Sequenciamento em Máquinas Não-Relacionadas com Tempos de Preparação Dependentes da Sequência"

Aluno: Matheus Nohra Haddad

Orientador: Marcone Jamilson Freitas Souza

Co-orientador: Haroldo Gambini Santos

Resumo: Este trabalho aborda o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência, do inglês Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, ou apenas UPMSP. Neste problema há um conjunto de tarefas e máquinas e a cada tarefa está associado um tempo de processamento, que é diferente para cada máquina. Dadas duas tarefas, também existe um tempo de preparação dependente da sequência delas e da máquina utilizada. O objetivo considerado neste problema foi o de minimizar o tempo máximo de conclusão do sequenciamento, o chamado makespan. O UPMSP é muito encontrado no âmbito industrial e pertence à classe NP-difícil. Visando a sua resolução, são propostos três algoritmos heurísticos híbridos. O primeiro, nomeado IVP, combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND) e Path Relinking (PR). O segundo, nomeado GIVP, difere do primeiro pelo fato de gerar a solução inicial pela fase de construção Greedy Randomized Adaptive Search Procedure (GRASP), e não por um procedimento guloso. O terceiro algoritmo, nomeado GIVMP, difere dos outros em três estratégias: a fase PR utiliza a estratégia mixed relinking ao invés de backward relinking, as vizinhanças que formam o VND são usadas em ordem aleatória a cada chamada e não em ordem previamente definida; por fim, o GIVMP inclui um módulo de busca local feita por um resolvedor de programação matemática. Este resolvedor é aplicado apenas à máquina gargalo do problema e utiliza um modelo de programação inteira mista baseado no problema do Caixeiro Viajante Assimétrico. Para explorar o espaço de soluções são utilizados movimentos de inserção e troca de tarefas entre máquinas. Para testar os algoritmos foram utilizados dois conjuntos de problemas-teste da literatura. Inicialmente eles foram comparados entre si em um conjunto reduzido de instâncias, tendo-se verificado a superioridade do algoritmo GIVMP. Em seguida, este algoritmo foi comparado com outros seis da literatura, sendo dois no primeiro conjunto de problemas-teste e outros quatro no segundo. No primeiro conjunto verificou-se a superioridade absoluta do GIVMP sobre os dois algoritmos genéticos da literatura, tendo-se encontrado desvios percentuais relativos médios menores e novas melhores soluções. No segundo conjunto de problemas-teste verificou-se que o GIVMP tem desempenho inferior a um dos algoritmos, mas superior em relação aos outros três. Observa-se, no entanto, que neste segundo conjunto de problemas, não foram disponibilizados os desvios percentuais relativos médios dos algoritmos, mas apenas os desvios dos melhores valores encontrados, impedindo uma comparação de robustez dos algoritmos.