Um algoritmo Iterated Local Search com busca local baseada em Very Large-Scale Neighborhood Search para a programação de máquinas paralelas.

Abstract

Este trabalho trata o problema de programação de máquinas paralelas com minimização do atraso. Neste problema, para cada tarefa é conhecido o tempo de processo, a data de entrega e o peso por dias de atraso. O objetivo é alocar as tarefas às máquinas minimizando a soma dos atrasos ponderados. Para resolvê-lo, foram desenvolvidas duas versões de um algoritmo baseado na metaheurística Iterated Local Search (ILS). Esse algoritmo explora o espaço de soluções usando movimentos de realocação e troca entre tarefas de máquinas diferentes, assim como movimentos de troca e inversão de subsequências de tarefas de uma mesma máquina. A versão denominada ILS-Clássica usa nas buscas locais somente os movimentos clássicos definidos acima, enquanto a versão denominada ILS-VLNS utiliza a técnica Very Large-scale Neighborhood Search (VLNS) como método de busca local do ILS que realiza operações do tipo n-optimal. Foram realizados testes computacionais com instâncias da literatura nas quais as soluções ótimas são conhecidas e também com instâncias maiores, nas quais as soluções ótimas não são conhecidas. Foi possível verificar que a versão ILS-VLNS produziu resultados melhores do que a versão ILS-Clássica; porém seus resultados não superaram os da literatura.