The use of very large-scale neighbourhood search techniques for the parallel machine scheduling problem

Este trabalho trata do problema de sequenciamento de tarefas em maquinas paralelas e uniformes (parallel machines total weighted tardiness problem). O objetivo e sequenciar as tarefas tal que cada tarefa seja realizada em uma maquina, cada maquina realize uma tarefa por vez e seja minimizada a soma dos atrasos ponderados. O problema e resolvido em duas etapas: o particionamento das tarefas entre as maquinas e o sequenciamento das tarefas nas maquinas. A contribuicao deste trabalho consiste em resolver as duas etapas com diferentes heuristicas de busca de grande porte e comparar suas eficiencias. A tecnica Very Large-scale Neighborhood Search, que utiliza um grafo de melhoria com cancelamento de ciclos negativos, e empregada para realizar o particionamento das tarefas. Um algoritmo de Programacao Dinâmica, conhecido como Dynasearch, que tambem e uma tecnica de busca em vizinhanca de grande porte, realiza o sequenciamento das tarefas em cada maquina. Ambas as buscas sao combinadas na metaheuristica ILS. As duas versoes do ILS sao comparadas, resolvendo problemas benchmark da literatura.