Por Andrés Polanco, Data Scientist en Notus.
En el blog anterior, revisamos los tipos de problemas de scheduling y varios enfoques operativos que las organizaciones utilizan para gestionar estos desafíos. Estas técnicas son útiles, sin embargo, no siempre garantizan una buena solución. El problema del job shop, por ejemplo, es un problema NP-completo, lo que implica que a medida que el número de variables aumenta, el tiempo requerido para encontrar una solución óptima crece exponencialmente y que no existen algoritmos que puedan resolver estos problemas en tiempo polinómico. Además, si las secuencias no están definidas de antemano y la programación de los trabajos puede cambiar en cualquier momento, este problema se transforma en un dynamic job shop, agregando aún más complejidad.
Dada la complejidad de estos problemas, es crucial explorar los métodos que se utilizan en la práctica para buscar soluciones eficientes.
Métodos exactos
En primer lugar, se consideran los métodos exactos, los cuales permiten llegar a una solución óptima. Estos métodos incluyen la programación entera y la programación entera mixta, así como el método conocido como Branch & Bound. En este último, el espacio de soluciones se divide en ramas; cada rama se evalúa y solo se continúa investigando aquellas susceptibles de encontrar una solución óptima, mientras que las ramas no prometedoras se podan. Esto permite descartar grandes porciones del espacio de búsqueda, acelerando el proceso de encontrar la solución óptima. Estos métodos se utilizan cuando la dimensión del problema es reducida, ya que, tal y como se mencionó, el tiempo de cómputo aumenta exponencialmente con el número de variables.
Heurísticas
Luego, están las heurísticas, que son reglas generales utilizadas para simplificar la toma de decisiones y resolver problemas de manera más rápida. En el caso del job shop, es común el uso de reglas de prioridad o de despacho, las cuales permiten definir prioridades entre los trabajos. Ejemplos incluyen:
- FIFO (First In, First Out): Los trabajos se procesan en el orden en que llegan.
- LIFO (Last In, First Out): Los trabajos más recientes se procesan primero.
- SPT (Shortest Processing Time): Los trabajos con tiempos de procesamiento más cortos tienen prioridad.
- LPT (Longest Processing Time): Los trabajos con tiempos de procesamiento más largos tienen prioridad.
Metaheurísticas
Después, están las metaheurísticas, que son técnicas de optimización que exploran el espacio de soluciones de manera inteligente y adaptativa, proporcionando soluciones aceptables en un tiempo razonable, pero no necesariamente óptimas. En el caso del job shop, es común la utilización de metaheurísticas poblacionales. Estos métodos mantienen una población de soluciones candidatas y aplican operadores de búsqueda para explorar y explotar el espacio de búsqueda. Los algoritmos más utilizados son los siguientes:
- Algoritmo Genético: Método estocástico de búsqueda y optimización basado en el Principio de Selección Natural de Darwin. El proceso funciona de manera iterativa donde transcurren las generaciones de individuos van quedando las mejores soluciones. La idea principalmente es «seleccionar a los mejores, descartar al resto».
- Algoritmo de Recocido Simulado: Técnica que utiliza un proceso de búsqueda aleatoria con una probabilidad decreciente de aceptar soluciones peores a medida que avanza la búsqueda, escapando así de mínimos locales. Similar al enfriamiento lento de metales en el proceso de recocido para reducir tensiones internas y mejorar la estructura cristalina.
- Algoritmo de Colonia de Hormigas: Técnica de búsqueda estocástica inspirada en el comportamiento de las hormigas para encontrar soluciones óptimas, donde las hormigas encuentran caminos óptimos entre la comida y el hormiguero mediante la deposición de feromonas.
Un ejemplo es este último algoritmo se observa en la Figura 2. Aquí, una hormiga exploradora sale del hormiguero H en busca del recurso R. Si la hormiga encuentra algo en el camino, entonces marca la ruta de regreso con vapor de feromona. La siguiente hormiga puede seguir esta señal o tomar una ruta diferente. Cuanto más fuerte sea la señal de feromona, más hormigas la seguirán. Esto ocurre principalmente cuando el recurso es grande o se encuentra cerca. Si un camino se usa con menos frecuencia, entonces la señal de feromona se evapora. La esencia del método radica en el cambio de feromona que indica qué tan adecuado es el camino.
Modelos de inteligencia artificial para Scheduling
Por último, se consideran los modelos de inteligencia artificial. Comúnmente se utilizan modelos predictivos de Machine Learning para estimar los tiempos de procesamiento y la demanda futura, mejorando así la planificación. También se identifican patrones y tendencias que informan decisiones de planificación de tareas.
En particular, se utiliza Reinforcement Learning, mediante el cual un agente aprende a tomar decisiones secuenciales para maximizar una recompensa a largo plazo, ajustando sus acciones basándose en el feedback recibido del entorno. Estos algoritmos se combinan con reglas de despacho, permitiendo al agente aprender a priorizar (FIFO, LIFO, etc) según el estado actual en el que se encuentre el sistema.
Otros modelos de machine learning, como Case-Based Reasoning (CBR) y Support Vector Machines (SVM), también han sido utilizados para este tipo de problemas. En el caso de Deep Learning, es común el uso de redes neuronales. En particular, las Redes Neuronales Recurrentes (RNN) son útiles para modelar la secuencia temporal de tareas en un proyecto, proporcionando soluciones avanzadas para problemas complejos de scheduling.
Hemos revisado los distintos métodos utilizados para obtener soluciones eficientes a problemas de scheduling. Estos métodos corresponden a los modelos exactos, las heurísticas, metaheurísticas y los modelos de inteligencia artificial. En Notus, contamos con amplia experiencia en la confección de estos modelos y, específicamente, en su aplicación a problemas de scheduling. Estamos listos para abordar diversos problemas de este tipo, como la optimización de la programación de vuelos en aerolíneas, la gestión de recursos en hospitales, la planificación de la producción en fábricas y la distribución eficiente de bienes en cadenas de suministro. Nuestro equipo está preparado para enfrentar estos desafíos y ofrecer soluciones personalizadas que maximicen la eficiencia operativa y la satisfacción del cliente. Si tienes problemas de scheduling en tu organización, no dudes en contactarnos. En Notus, estamos comprometidos a ayudarte a encontrar la mejor solución para tus necesidades.
