Algoritmos para o Problema de Sequenciamento de Máquinas Paralelas não Relacionadas com Recurso Escasso Adicional
Scheduling, Recurso escasso adicional, Máquinas Paralelas não Relacionadas, General Variable Neighborhood Search, Metaheuristica.
Este projeto de dissertação de mestrado apresenta o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas com recurso escasso adicional conhecido como UPMR (Unrelated Parallel Machine Scheduling problem with additional Resources). Para resolver este problema é preciso obter uma sequência de tarefas nas máquinas disponíveis sem ultrapassar o limite de um determinado recurso disponível para cada instante de tempo, assim obter um sequenciamento factível e com o menor tempo final possível (makespan). Inicialmente é proposto um procedimento guloso para a geração de soluções iniciais, uma busca local baseada no Variable Neigborhood Descent (VND) e um método guloso para o reparo de soluções infactíveis. Uma metaheurística GVNS (General Variable Neighborhood Search) também faz parte da proposta apresentada. O método de reparo proposto busca reparar soluções com o mínimo de piora do makespan possível. Um conjunto de instâncias disponíveis na literatura juntamente com seus resultados obtidos em trabalhos correlatos foram utilizados, melhoras significativas já em testes preliminares puderam ser observadas. Parte destes resultados encontram-se no final deste documento.