Sequenciamento de tarefas em máquinas paralelas com desgastes dependentes da sequência: resolução heurística - Santos, Vívian Ludmila Aguiar (2016)
Este trabalho aborda o problema de sequenciamento de tarefas em máquinas pa- ralelas não-relacionadas em que as tarefas causam desgastes nas máquinas. Este fator diminui o desempenho das máquinas levando ao aumento do tempo de pro- cessamento das tarefas ao longo do tempo. O objetivo do problema é encontrar as sequências de processamento de tarefas em cada máquina de tal maneira que os desgastes das máquinas sejam reduzidos e, consequentemente, minimizar o tempo máximo de conclusão de todas as tarefas, conhecido como makespan. Neste traba- lho, inicialmente, é proposto um novo modelo de Programação Inteira Mista baseado na geração de padrões (conjuntos de tarefas) para cada máquina, com objetivo de obter soluções ótimas para o problema. Dado que o problema é NP-Difícil para mais de uma máquina, dois algoritmos heurísticos são propostos para obter solu- ções de alta qualidade em baixo tempo computacional. Os algoritmos são baseados nas meta-heurísticas Iterated Local Search (ILS) e Iterated Greedy (IG), respecti- vamente. Também, as heurísticas ILS e IG são combinadas com uma variante do método Variable Neighborhood Descent (VND), que utiliza uma ordenação aleatória das vizinhanças (RVND) na fase da busca local, obtendo dois algoritmos híbridos denominados ILS-RVND e IG-RVND. O benchmark usado nos experimentos compu- tacionais usa 900 instâncias de médio porte disponíveis na literatura, e 900 instâncias de grande porte geradas neste trabalho. Os algoritmos são comparados entre si e também com um algoritmo Simulated Annealing (SA) proposto na literatura para o mesmo problema. Os testes realizados mostram que os desempenhos dos algoritmos propostos são significativamente superiores em relação ao algoritmo SA.