Evolving priority rules for scheduling problems by means of hyper-heuristics

Abstract

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 [Computers & Industrial Engineering 85, 306-315, 2015], 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 (1;Cap(t)||Ti). 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 (1;Cap(t)||Ti). 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 (1;Cap(t)||Ti) 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 (1;Cap(t)||Ti). 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