Este artigo propõe uma heurística híbrida baseada em população, simples, mas eficaz, chamada ruin-and-recreate (HyPRR), para minimizar o makespan em um problema de escalonamento em máquina única com datas de liberação e restrições de inventário. Além de um procedimento de ruína e recriação, o algoritmo incorpora um esquema de diversificação para gestão da população e uma fase de intensificação através de busca local. Um componente chave da abordagem proposta é uma estratégia de avaliação de movimento nova e altamente eficiente que permite a computação do makespan e a verificação da inviabilidade do inventário em tempo constante amortizado. Experimentos computacionais em 1044 instâncias destacam a competitividade do algoritmo proposto em comparação com o método de tentativa e erro (GC) da literatura. Para as instâncias de benchmark existentes, o método desenvolvido encontrou a solução ótima em 99% dos casos com ótimos conhecidos e produziu novas melhores soluções para 21 instâncias. Além disso, introduzimos um novo conjunto de instâncias de benchmark maiores, projetadas para serem mais desafiadoras do que aquelas apresentadas na literatura. Os resultados dos experimentos nessas instâncias mostram que, embora ambos os métodos tenham um bom desempenho, o HyPRR supera o GC em termos do número de soluções ótimas encontradas e da qualidade média das soluções. Mais importante ainda, para essas instâncias, enquanto o HyPRR sempre encontra uma solução viável, o GC falhou em encontrar uma para várias instâncias.
Morais et al. (Fri,) estudaram esta questão.