Este artículo propone una heurística híbrida simple pero efectiva basada en poblaciones, conocida como ruin-and-recreate (HyPRR), para minimizar el makespan en un problema de programación en una sola máquina con fechas de liberación y restricciones de inventario. Además de un procedimiento de ruin-and-recreate, el algoritmo incorpora un esquema de diversificación para la gestión de poblaciones y una fase de intensificación a través de búsqueda local. Un componente clave del enfoque propuesto es una estrategia de evaluación de movimientos novedosa y altamente eficiente que permite la computación del makespan y la verificación de la inviabilidad del inventario en tiempo constante amortizado. Los experimentos computacionales en 1044 instancias destacan la competitividad del algoritmo propuesto en comparación con el método de adivinar y comprobar (GC) de la literatura. Para las instancias de referencia existentes, el método desarrollado encontró la solución óptima en el 99% de los casos con óptimos conocidos y produjo nuevas mejores soluciones para 21 instancias. Además, introdujimos un nuevo conjunto de instancias de referencia más grandes diseñadas para ser más desafiantes que las de la literatura. Los resultados de los experimentos en estas instancias muestran que, aunque ambos métodos funcionan bien, HyPRR supera a GC en términos del número de soluciones óptimas encontradas y la calidad promedio de la solución. Más importante aún, para estas instancias, mientras que HyPRR siempre encuentra una solución factible, GC no pudo encontrar una en varias instancias.
Morais et al. (Fri,) estudiaron esta cuestión.