Métodos heurísticos avanzados para problemas de scheduling

Abstract

Los problemas de scheduling están presentes en numerosos ámbitos reales. En general, consisten en organizar la ejecución de un conjunto de operaciones en diferentes recursos, satisfaciendo diversas restricciones con el fin de optimizar alguna métrica o función objetivo. Muchos de ellos, como el paradigmático problema Job Shop Scheduling, pertenecen a la clase de complejidad NP-hard, lo que significa que pueden ser realmente difíciles de resolver. En las últimas décadas ha habido un estudio intensivo de los problemas de scheduling por parte de campos científicos como la Inteligencia Artificial o la Investigación Operativa, dando lugar a un notorio número de técnicas de resolución, tanto exactas como aproximadas. Esta tesis doctoral tiene como objetivo el diseño de algoritmos exactos eficientes para problemas de scheduling, capaces de resolver de forma óptima instancias del problema de hasta cierto tamaño y de calcular tanto cotas inferiores no triviales como buenas soluciones para instancias más difíciles en un tiempo corto y empleado recursos de memoria escasos. Concretamente, la investigación se ha centrado en el problema Job Shop Scheduling y en el problema Job Shop Scheduling con Operarios, una generalización del primero que considera restricciones complejas derivadas de la presencia de trabajadores humanos en entornos productivos. Por medio de técnicas de búsqueda heurística y de razonamiento basado en restricciones, hemos contribuido a este campo en varios modos. En primer lugar, evaluamos dos variantes de algoritmos de búsqueda primero en profundidad en el contexto del problema Job Shop Scheduling, y proponemos un algoritmo de búsqueda en profundidad parcialmente informada que explota eficazmente el conocimiento del domino del problema para guiar la búsqueda hacia zonas prometedoras del espacio de búsqueda. Este algoritmo saca partido de un heurístico original que explota un método de propagación de restricciones. En segundo lugar, proponemos una nueva estrategia de búsqueda, que extiende la técnica Iterative Deepening A* para resolver problemas de scheduling y de optimización con restricciones. La nueva estrategia, denominada Intensified Iterative Deepening A*, emplea la propagación de restricciones de un modo no conservativo, actualiza el umbral de coste de forma liberal entre iteraciones consecutivas y lanza búsquedas en profundidad limitadas desde algunos estados para muestrear distintas regiones del espacio de búsqueda. Esta técnica se ha mostrado muy efectiva en el problema Job Shop Scheduling. Por último, diseñamos varias componentes de algoritmos de búsqueda heurística para el problema Job Shop Scheduling con Operarios: una definición de un espacio de búsqueda basado en un nuevo esquema de generación de planificaciones denominado OG&T, dos heurísticos y una relación de dominancia empleada para podar estados. Asimismo, proponemos una nueva estrategia de búsqueda heurística, denominada A*DFS, que combina de un modo original los algoritmos A* y búsqueda primero en profundidad, obteniendo muy buenos resultados.