Búsqueda Heurística para Problemas de Scheduling*

Resumen

En este artículo presentamos una aplicación del algoritmo A* al problema Job Shop Scheduling (JSS). Explotamos el espacio de búsqueda de las planificaciones activas y un heurístico basado en relajaciones del problema. Estudiamos experimentalmente el límite hasta el cual se pueden obtener soluciones óptimas de esta forma y también algunas extensiones para obtener soluciones semi-óptimas. Y comparamos los resultados con los obtenidos por otros sistemas similares bien conocidos. Finalmente proponemos algunas mejoras para realizar en un trabajo futuro. Palabras clave: Scheduling, búsqueda heurística, optimización, satisfacción de restricciones