Problemas numéricos y de optimización de grafos

2.4 Problemas numéricos y de optimización de grafos

Una vez construido el grafo que representa un proceso de fabricación, surge la necesidad de resolver problemas matemáticos específicos sobre su estructura. Estos problemas numéricos van desde cálculos determinísticos sobre tiempos y holguras, hasta problemas de optimización donde se busca encontrar la solución mejor entre múltiples alternativas viables. El dominio de estos problemas es esencial para transformar el grafo de un diagrama teórico en una herramienta de decisión operativa en la programación de la producción.

El problema del cálculo de la ruta crítica

El problema de identificar la ruta crítica es el análisis fundamental en cualquier proyecto de fabricación. Se resuelve mediante dos algoritmos iterativos: el algoritmo hacia adelante (forward pass) que calcula tiempos tempranos, y el algoritmo hacia atrás (backward pass) que calcula tiempos tardíos. En el algoritmo hacia adelante, comenzando desde el nodo inicial, cada nodo recibe el máximo tiempo de finalización de sus predecesores: T_temprano(i) = máx(T_temprano(j) + duración(j,i)) para todos los predecesores j. En el algoritmo hacia atrás, partiendo del nodo final, cada nodo se asigna el mínimo tiempo de comienzo de sus sucesores: T_tardío(i) = mín(T_tardío(j) - duración(i,j)) para todos los sucesores j.

Una actividad es crítica si su holgura es cero, es decir, si T_tardío(i) - T_temprano(i) = 0. La ruta crítica es el camino uniendo todas las actividades críticas desde inicio hasta final. Su longitud es la duración mínima del proyecto. En una empresa que fabrica conjuntos mecánicos complejos, la ruta crítica podría incluir operaciones como: obtención de acero especial (4 semanas) → forja inicial (2 semanas) → tratamiento térmico (3 semanas) → mecanizado final (2 semanas) = 11 semanas totales. Cualquier retraso en estas operaciones retrasa la entrega final.

El problema de optimización de recursos

En muchos escenarios reales de fabricación, los recursos disponibles (máquinas, operarios, herramientas) son limitados. Cuando múltiples actividades requieren el mismo recurso, surge el problema de optimización de recursos o levelling de carga de trabajo. El objetivo es redistribuir actividades no críticas (que tienen holgura disponible) para equilibrar la utilización de recursos y minimizar picos de demanda que son costosos de atender.

Este es un problema combinatorio complejo. Formalmente, se trata de minimizar la máxima carga de cualquier recurso en cualquier período, o alternativamente minimizar el número de recursos necesarios manteniendo la fecha de entrega. Las restricciones incluyen: las dependencias de precedencia entre actividades no pueden violarse, la capacidad de cada recurso no puede excederse, solo actividades con holgura disponible pueden retrasarse. Algoritmos como el de Burgess y Killebrew, o algoritmos genéticos, encuentran soluciones aproximadas buenas aunque no siempre óptimas.

El problema del camino más corto y más largo

El problema del camino más largo (que es el cálculo de la ruta crítica en grafos acíclicos) puede generalizarse. Dado un grafo con pesos en las aristas, encontrar el camino de máxima longitud desde un nodo origen a un nodo destino. Para grafos acíclicos dirigidos, el algoritmo de Bellman-Ford adaptado resuelve eficientemente este problema. Para grafos con ciclos, la resolución es más compleja.

Inversamente, el problema del camino más corto (distancia mínima entre dos puntos) se resuelve con algoritmos como Dijkstra, Floyd-Warshall, o Bellman-Ford según las características del grafo. En contextos de producción, el camino más corto podría representar la ruta de mínimo costo para transportar materiales desde almacén hasta puesto de trabajo, o el secuenciamiento de máquinas que minimiza tiempo muerto.

Problemas de flujo de red

Los problemas de flujo de red modelan el movimiento de recursos (materiales, información, capacidad de producción) a través de un sistema. Un problema clásico es el de flujo máximo: dada una red donde cada arista tiene una capacidad máxima, encontrar el máximo flujo que puede circular desde un nodo origen a un nodo sumidero sin exceder las capacidades. El algoritmo de Ford-Fulkerson resuelve este problema mediante identificación iterativa de caminos aumentantes.

En fabricación mecánica, los problemas de flujo máximo aparecen al dimensionar líneas de producción: si cada máquina tiene una capacidad máxima de producción (unidades por hora), cuál es la producción máxima que puede alcanzarse manteniendo el balance en toda la línea. El problema de flujo de costo mínimo combina capacidades con costos, buscando enviar una cantidad específica de flujo al menor costo total.

Problemas de asignación y transporte

El problema de asignación resuelve cómo distribuir n trabajadores entre n trabajos de modo que el costo total sea mínimo, o la eficiencia total sea máxima. El algoritmo húngaro resuelve óptimamente problemas cuadrados de asignación. En fabricación, podría aplicarse para asignar cinco operarios especializados a cinco máquinas distintas maximizando compatibilidad y eficiencia.

El problema del transporte busca distribuir bienes desde múltiples orígenes (almacenes con suministros limitados) a múltiples destinos (plantas de producción con demandas específicas) minimizando costo de transporte. Se formula como programa lineal y se resuelve mediante el método del simplex o algoritmos de red especializados.

Sensibilidad y análisis de escenarios

Los problemas de optimización reales requieren análisis de sensibilidad: cómo cambia la solución óptima si se modifican parámetros. Si la duración de una actividad crítica aumenta en una semana, cuánto se retrasa el proyecto? Si aumentamos la capacidad de un cuello de botella en 10%, cuánto mejora el flujo total? Estos análisis identifican parámetros críticos y guían las decisiones de inversión en aumento de capacidad o mejora de procesos.

Ideas clave

• El cálculo de la ruta crítica mediante algoritmos hacia adelante y atrás es el análisis fundamental para determinar la duración mínima del proyecto.
• La optimización de recursos resuelve cómo distribuir recursos limitados entre actividades para equilibrar carga y minimizar costos.
• Los problemas de camino óptimo, flujo máximo, y asignación tienen soluciones algorítmicas bien establecidas aplicables a contextos de producción.
• El análisis de sensibilidad identifica parámetros críticos y guía decisiones sobre dónde invertir recursos para mejorar el rendimiento.
• La solución de estos problemas requiere frecuentemente herramientas computacionales y algoritmos especializados, no es práctica la resolución manual en proyectos complejos.