O uso de técnicas de busca em vizinhança de grande porte para resolver o problema de sequenciamento de tarefas em máquinas paralelas e uniformes.

Abstract

Este trabalho trata do problema de otimização do sequenciamento em máquinas uniformes e paralelas com atraso total ponderado, conhecido como Parallel Machines Total Weighted Tardiness Problem. Para cada tarefa é conhecido o seu tempo de processamento, sua data de entrega e o peso por dia de atraso da conclusão da tarefa em relação à sua data de entrega. Deve-se sequenciar as tarefas entre as máquinas de forma que cada tarefa seja realizada em uma única máquina e cada máquina realize uma única tarefa por vez e sem preempção, com o objetivo de minimizar os atrasos ponderados. Este sequenciamento é obtido em duas etapas: o particionamento das tarefas entre as máquinas e o sequenciamento das tarefas em cada máquina. A contribuição deste trabalho é resolver as duas etapas com heurísticas de busca em vizinhança de grande porte. A técnica Very Large-scale Neighborhood Search é empregada de formas distintas daquelas encontradas na literatura para realizar o particionamento das tarefas, e um algoritmo de Programação Dinâmica Dynasearch realiza o sequenciamento das tarefas em cada máquina. Ambas as buscas são combinadas na metaheurística Iterated Local Search (ILS). Foram realizados testes com problemas benchmark da literatura mostrando a competitividade das versões propostas.