Meta-heurísticas para o sequenciamento de famílias de tarefas em máquinas paralelas uniformes de processamento em lote - Tavares, Ricardo Gonçalves (2020)
Este trabalho aborda o problema de sequenciar um conjunto de n tarefas com in- compatibilidade de famílias, com tamanhos arbitrários e tempos de processamento distintos, em um conjunto de m máquinas paralelas uniformes com capacidades di- ferentes. Neste problema, as máquinas têm uma característica especial, processar um lote de tarefas simultaneamente, desde que a capacidade da máquina não seja exce- dida. Apenas tarefas de mesma família podem ser agrupadas em um lote. O tempo de processamento do lote é igual ao maior tempo de processamento entre todas as tarefas do lote. O problema consiste em agrupar as tarefas em lotes e, em seguida, se- quenciar os lotes nas máquinas de tal maneira que o tempo de conclusão de todos os lotes seja minimizado (minimização do makespan). Como o problema pertence à classe NP-Difícil, neste trabalho, são propostos: i) um modelo de Programação Inteira-Mista para obter soluções ótimas para instâncias pequenas do problema; e ii) dois algorit- mos heurísticos baseados em meta-heurísticas para obter soluções de alta qualidade e em tempo computacional aceitável para instâncias de problemas de grande porte. Os algoritmos são baseados nas meta-heurísticas Iterated Greedy (IG) e Discrete Differential Evolution (DDE). Também estas meta-heurísticas são hibridizadas fazendo uma com- binação com métodos de busca local, utilizando uma seleção aleatória de vizinhan- ças. Os resultados dos experimentos mostram que os desempenhos dos algoritmos propostos são de alta qualidade, tendo o algoritmo DDE-Híbrido apresentado os me- lhores resultados em comparação aos algoritmos da literatura. Palavras-chave: Sequenciamento de tarefas. Máquinas paralelas de processamento em lote. Incompatibilidade de família de tarefas. Otimização combinatória. Heurísticas. Meta-heurísticas.