Cálculo de reglas de prioridad para problemas de scheduling con hiperheurísticos

Résumé

Los problemas de planificación o scheduling aparecen con profusión en numerosos campos de la industria y la gestión, destacando por su alta complejidad computacional (generalmente son NP-duros). Por este motivo, suelen requerir del uso de algoritmos y técnicas avanzadas de Inteligencia Artificial. En particular, los problemas de scheduling de una máquina han incrementado su popularidad durante las últimas décadas, debido a su propio interés y dificultad, así como por aparecer frecuentemente al descomponer otros problemas de scheduling más complejos. Esta tesis se centra en un problema de esta clase, en el que se deben planificar una serie de trabajos en una sola máquina, con el objetivo de minimizar la función de retardo total, denominada total tardiness. La característica particular de este problema es que la máquina puede procesar más de un trabajo a la vez, pero esta capacidad varía a lo largo del tiempo. Este problema se introdujo en HernandezArauzo2015, en el contexto de la planificación de los tiempos de carga de una gran flota de vehículos eléctricos, y se denota con OMSVCP. Resolver el problema de planificación de carga de vehículos eléctricos (EVCSP) requiere resolver, a lo largo del tiempo, varias instancias del problema OMSVCP . Debido a la intratabilidad computacional, y a los estrictos requisitos de tiempo real del EVCSP, la planificación en línea representa el único enfoque adecuado para abordar el problema. El problema OMSVCP puede resolverse empleando la regla de prioridad Apparent Tardiness Cost (ATC), comúnmente utilizada en el contexto de scheduling con objetivos de retardo o tardiness. Debido a su bajo coste computacional, este enfoque es muy adecuado para la planificación en línea: el trabajo con mayor prioridad, entre los disponibles en un momento dado, es el siguiente a planificar. Como en el caso de la regla ATC, las reglas de prioridad pueden ser definidas manualmente por expertos en el dominio del problema. Sin embargo, nuestra hipótesis es que los métodos automáticos pueden capturar algunas características del problema de scheduling que no son evidentes para los expertos humanos. El objetivo de esta tesis es el desarrollo automatizado de reglas de prioridad, adaptadas específicamente al problema OMSVCP . Una forma natural de abordar esta tarea es mediante el uso de hiperheurísticos, ya que la búsqueda debe realizarse en un espacio de heurísticos, y no en un espacio de soluciones al problema de scheduling. Por lo tanto, dado que las reglas de prioridad son expresiones aritméticas, que pueden ser representadas naturalmente por árboles, comenzamos a investigar el uso de la Programación Genética (GP), para luego considerar otras técnicas. Esta tesis se presenta como un compendio de publicaciones en revistas y congresos, que recogen los principales hallazgos alcanzados, los cuales se resumen en los siguientes puntos: 1- Definimos un procedimiento de generación (gramática) que permite construir o enumerar reglas de prioridad en un espacio de expresiones dimensionalmente correctas. La definición de este procedimiento de generación, tras un detallado estudio y análisis del problema OMSVCP, nos permitió conocer su estructura e identificar los atributos más relevantes de las reglas de prioridad. 2- El procedimiento de generación se explotó en una serie de algoritmos, a saber, un programa genético, una búsqueda local, una búsqueda enumerativa en profundidad, así como en algunas combinaciones y variantes de los mismos. Estos algoritmos fueron evaluados sobre conjuntos de instancias de OMSVCP, que se asemejan a las instancias que, se espera, se generarán al resolver el EVCSP. Los resultados de los estudios experimentales muestran que es posible obtener reglas de prioridad que funcionen mejor que las construidas por expertos humanos, y que las reglas pueden adaptarse a la estructura de las instancias en un conjunto concreto. 3- Desarrollamos un marco de trabajo común para explotar los algoritmos anteriores, que puede ser empleado en otros estudios experimentales adicionales, y ampliado para resolver otros problemas de scheduling. La tesis deja abiertas algunas líneas de investigación. Por ejemplo, la gramática podría mejorarse para aprovechar mejor algunos atributos del problema, como la capacidad variable de la máquina, y también podría explotarse con otros algoritmos de búsqueda. Otra línea interesante sería aplicar las técnicas desarrolladas en otros problemas de scheduling.