Meta-heurísticas para o sequenciamento de famílias de tarefas em máquinas paralelas uniformes de processamento em lote

• Ano de defesa: 2020
• Autor(a) principal: Tavares, Ricardo Gonçalves
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa; Ciência da Computação
• Palavras-chave em Português: Programação heurística; Processamento de dados - Processamento em lote; Otimização combinatória; Algoritmos paralelos; Programação paralela (Computação); Processamento paralelo (Computadores); Ciência da Computação
• Link de acesso: https://locus.ufv.br//handle/123456789/30983

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.