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

Meta-heuristics for scheduling job families on identical parallel batch processing machines

Abstract

Este artigo aborda um problema de sequenciamento de tarefas em máquinas paralelas idênticas de processamento em lote. Neste problema uma máquina pode executar um lote de tarefas simultaneamente. Além disso, as tarefas são classificadas em famílias, onde uma família agrupa tarefas que possuam alguma característica em comum. Assim, os lotes devem conter somente tarefas de uma mesma família. O problema também considera tarefas com diferentes tempos de chegada (release times). As tarefas possuem ainda uma data de entrega e um peso. O objetivo do problema é determinar os lotes de tarefas para serem sequenciados nas máquinas de tal maneira que o atraso total ponderado das tarefas seja minimizado. O problema envolvendo sequenciamento de lotes é uma extensão do sequenciamento de tarefas clássico (onde uma máquina processa apenas uma tarefa por vez) e possui muitas aplicações reais.  Para resolver o problema abordado, três algoritmos baseados em meta-heurísticas foram desenvolvidos: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) e Simulated Annealing (SA). Todos estes algoritmos utilizam técnicas de busca em vizinhança para melhorar a qualidade de uma solução. Experimentos computacionais, utilizando dados da literatura, foram realizados a fim de avaliar o desempenho dos algoritmos. Para instâncias de grande porte, os algoritmos propostos são comparados com dois algoritmos da literatura (Memetic Algorithm e Variable Neighborhood Search). Os experimentos e testes realizados demonstram que os algoritmos desenvolvidos neste trabalho geram soluções válidas de excelente qualidade superando as melhores soluções encontradas na literatura.