Uma heurística populacional híbrida para um problema de escalonamento em uma máquina com datas de liberação e restrições de inventário

Este trabalho aborda uma variante do problema de escalonamento em uma única máquina com o objetivo de minimizar o makespan, na qual as tarefas possuem datas de liberação e podem produzir ou consumir um único recurso, armazenado em um inventário de capacidade limitada.

Como método de resolução, foi proposta uma heurística populacional híbrida, denominada Hybrid Population-based Ruin-and-Recreate (HyPRR), que combina mecanismos de busca populacional com operadores de ruin-and-recreate.

O HyPRR encontrou soluções ótimas em 99% das instâncias para as quais o ótimo era conhecido, além de produzir 21 novas melhores soluções. Também foi desenvolvido um novo conjunto de instâncias de benchmark de maior porte, projetado para ser mais desafiador do que os conjuntos disponíveis na literatura.

Os resultados computacionais nessas novas instâncias mostram que, embora tanto o HyPRR quanto o método de referência apresentem bom desempenho, o HyPRR supera a literatura em termos do número de soluções ótimas encontradas e da qualidade média das soluções.

Autores: Rafael Morais, Frederico Guerra, Ana Carolina Moura, Bruno Bruck, Anand Subramanian