Abordagens simheurísticas para o problema de sequenciamento em máquinas paralelas.

Abstract

O problema de sequenciamento em máquinas paralelas (PMSP) é um problema combinatório clássico que, desde suas publicações seminais, oferece grandes desafios para a pesquisa, dada a sua vasta aplicação em problemas teóricos e práticos. Neste trabalho, uma variante estocástica do PMSP será abordada, considerando a minimização do makespan. Para tornar o problema mais realístico, os parâmetros estocásticos serão a disponibilidade para iniciar o processamento das atividades e as paradas programadas das máquinas. Dois algoritmos do tipo simheurística são propostos, estes baseados na Busca local iterada (Iterated local search - ILS) e no método de Busca em vizinhança variável (Variable neighborhood search - VNS), que buscarão minimizar os valores esperados para o critério de otimização adotado. As soluções iniciais são geradas através da adoção da heurística LPT (Longest processing time - Maior tempo de processamento) e novas soluções são produzidas a partir de estruturas de vizinhança que funcionam ora como buscas locais ora como métodos de perturbação. Estas estruturas realizam alterações individualmente e entre diferentes pares de máquinas. Os resultados encontrados pelos métodos propostos, ILS e VNS, foram superiores, quando comparados com a resolução pelo solver comercial AMPL/CPLEX. Obtendo 47% dos melhores valores para a esperança do makespan para o ILS e 37% para o VNS. É necessário destacar que ambos métodos obtiveram baixos tempos computacionais, onde o ILS chegou a ser até 37 vezes mais rápido que o VNS.