O uso de técnicas de busca em vizinhança de grande porte para o problema de programação de máquinas paralelas

Abstract

Este trabalho trata do problema de sequenciamento de tarefas em máquinas paralelas e uniformes (parallel machines total weighted tardiness problem). O objetivo é sequenciar as tarefas tal que cada tarefa seja realizada em uma máquina, cada máquina realize uma tarefa por vez e seja minimizada a soma dos atrasos ponderados. O problema é resolvido em duas etapas: o particionamento das tarefas entre as máquinas e o sequenciamento das tarefas nas máquinas. A contribuição deste trabalho consiste em resolver as duas etapas com diferentes heurísticas de busca de grande porte e comparar suas eficiências. A técnica Very Large-scale Neighborhood Search, que utiliza um grafo de melhoria com cancelamento de ciclos negativos, é empregada para realizar o particionamento das tarefas. Um algoritmo de Programação Dinâmica, conhecido como Dynasearch, que também é uma técnica de busca em vizinhança de grande porte, realiza o sequenciamento das tarefas em cada máquina. Ambas as buscas são combinadas na metaheurística ILS. As duas versões do ILS são comparadas, resolvendo problemas benchmark da literatura.