Mejora de algoritmos de búsqueda heurística mediante poda por dominancia. Aplicación a problemas de scheduling

Abstract

Los problemas de scheduling aparecen con profusión en la vida real en numerosos entornos productivos y de servicios. Se trata de problemas que requieren organizar en el tiempo la ejecución de tareas que compiten por el uso de un conjunto finito de recursos y que están sujetas a un conjunto de restricciones impuestas por factores como las características físicas del entorno, relaciones temporales o la normativa laboral. Además se trata de optimizar uno o varios criterios que se representan mediante funciones objetivo y que están relacionados normalmente con el coste, el beneficio o el tiempo de ejecución. Algunos ejemplos de problemas de esta naturaleza son los siguientes: -Fabricación de obleas para circuitos semiconductores, donde cada oblea precisa de una serie de tareas como limpieza, oxidación, metalización, etc. El objetivo puede maximizar la utilización de algunas máquinas que son cuello de botella o minimizar el tiempo de ejecución. -Planificar el aterrizaje de un conjunto de aviones sujetos a restricciones temporales que dependen de las características de los aviones. Los objetivos pueden ser minimizar la penalización por desvío con respecto al tiempo preferente de los aviones o maximizar las condiciones de seguridad. -Planificar las rutas de flotas de autobuses, donde se trata de optimizar la ocupación de los vehículos y de ajustar los turnos de los conductores de acuerdo con la normativa laboral. -Enrutamiento de paquetes de datos a través líneas de comunicación, donde se trata de maximizar el uso de la red y de minimizar los tiempos de llegada de los mensajes. Dado que estos problemas son de naturaleza combinatoria, es decir que hay que elegir una entre un conjunto exponencialmente grande de combinaciones posibles, los problemas de scheduling precisan de algoritmos de búsqueda inteligentes para encontrar soluciones aceptables en un tiempo razonable. Así, en la literatura se pueden encontrar aproximaciones a los problemas de scheduling basadas en prácticamente todas las metaheurísticas conocidas y en particular en los algoritmos de búsqueda heurística propios de áreas como la Investigación Operativa y la Inteligencia Artificial. En esta tesis nos centramos en el problema Job Shop Scheduling y en la técnica de búsqueda heurística en espacios de estados. Nuestro objetivo es diseñar estrategias que resulten eficaces y eficientes para diferentes funciones objetivo, tanto para encontrar soluciones exactas, cuando el tamaño del problema lo permita, como para obtener soluciones aproximadas para instancias mayores. La función objetivo a la que los investigadores han prestado mayor atención es sin duda el makespan, o tiempo de finalización de la última tarea. Las propiedades de esta versión del problema son muy bien conocidas y han permitido desarrollar métodos exactos y aproximados muy eficientes que se basan en el concepto de camino crítico. El inconveniente de estos métodos es que no se generalizan de forma eficiente para otras funciones objetivo como el tiempo de flujo total o el tardiness. La aportación principal de esta tesis es la formalización de un método de poda basado en relaciones de dominancia entre los estados del espacio de búsqueda que se puede aplicar en principio a todas las funciones objetivo convencionales. Aunque el método no resulta competitivo con los métodos basados en el camino crítico cuando se trata de minimizar el makespan, sí lo es con los métodos que no están basados en el camino crítico y que son generalizables a otras funciones objetivo. Para funciones objetivo como el tiempo de flujo total, los resultados experimentales que hemos realizado sobre bancos de ejemplos estándar demuestran que el método es competitivo con otros métodos del estado del arte tanto para obtener soluciones óptimas como sub-óptimas.