Soluciones metaheurísticas al "job-shop scheduling problem with sequence-dependent setup times"

Resumen

Los problemas de scheduling requieren organizar en el tiempo la ejecución de tareas que comparten un conjunto finito de recursos, y que están sujetas a un conjunto de restricciones impuestas por diversos factores, como por ejemplo las características físicas del entorno, relaciones temporales o la normativa laboral. Este tipo de problemas aparecen con frecuencia en la vida real en numerosos entornos productivos y de servicios. El problema consiste en optimizar uno o varios criterios que se representan mediante funciones objetivo y que suelen estar relacionados con el coste o el tiempo total de ejecución. Algunos ejemplos de problemas de scheduling 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. Los objetivos pueden ser 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 horario planeado para los aviones o maximizar las condiciones de seguridad. Enrutamiento de paquetes de datos a través de 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. Todos estos problemas son de naturaleza combinatoria, es decir que hay que elegir una entre un conjunto exponencialmente grande de combinaciones posibles, y por lo tanto los problemas de scheduling precisan de algoritmos de búsqueda inteligentes para encontrar soluciones aceptables en un tiempo razonable. En la literatura se pueden encontrar aproximaciones a los problemas de scheduling basadas en todas las metaheurísticas conocidas. En esta tesis nos centramos en el problema Job Shop Scheduling with Sequence Dependent Setup Times. Este problema es una generalización del problema Job Shop clásico que tiene más interés en muchas aplicaciones reales. Además, es un problema mucho menos estudiado y su resolución es más compleja, ya que los tiempos de setup cambian la naturaleza del problema y muchas de las propiedades formales demostradas para el Job Shop, dejan de cumplirse en presencia de tiempos de setup. Por este motivo, la adaptación de las técnicas utilizadas para resolver el Job Shop muchas veces no será trivial. Como técnicas de búsqueda utilizaremos los algoritmos genéticos y la búsqueda local. Es bien sabido que estos métodos no necesariamente producen la solución óptima del problema, pero hay que tener en cuenta que cuando el espacio de búsqueda del problema es enorme, como ocurre en este caso, los métodos exactos de resolución suelen ser demasiado costosos, ya sea en tiempo de ejecución o en recursos computacionales. El objetivo, por lo tanto, será diseñar estrategias eficaces para obtener buenas soluciones en un tiempo razonable. Para ello se deberán estudiar aspectos como heurísticos, estructuras de vecindad, propiedades del camino crítico, algoritmos de estimación de vecinos, grafos disyuntivos, constructores de planificaciones, y en general encontrar la mejor configuración para los métodos utilizados. En esta tesis estudiaremos diversas funciones objetivo. 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. Pero otras funciones objetivo pueden tener mayor interés en problemas reales, en donde es posible que cada uno de los trabajos tenga un tiempo deseable de fin diferente, e incluso que algunos trabajos tengan una mayor prioridad que otros. Por este motivo, además de la minimización del makespan trataremos la minimización de otras tres funciones objetivo: maximum lateness, weighted tardiness y total flow time. Las aportaciones principales de esta tesis serán el estudio de las diferencias entre las propiedades del job shop clásico y el job shop con tiempos de setup, la definición de un modelo de grafo disyuntivo para cada función objetivo estudiada, el diseño de una serie de estructuras de vecindad con sus respectivas condiciones de factibilidad y de no mejora, algoritmos de estimación de vecinos para diferentes funciones objetivo y otras consideraciones sobre cómo realizar una búsqueda local de la forma lo más eficiente posible, y por último, unos resultados experimentales que mostrarán que la correcta combinación de los métodos propuestos es capaz de mejorar en muchos casos a los mejores resultados conocidos en la literatura.