Optimización metaheurística para Job Shop Scheduling (NP-hard)

Este proyecto aborda un problema clásico de programación de la producción, donde múltiples trabajos deben procesarse en distintas máquinas bajo plazos de entrega estrictos. Es investigación del Magíster: los métodos se evaluaron sobre nueve instancias estándar del benchmark de Taillard, no sobre datos de una planta.

El objetivo del sistema era minimizar la tardanza total en un Job Shop Scheduling Problem (JSP), un problema de optimización combinatoria clasificado como fuertemente NP-hard. Por su complejidad computacional, los métodos exactos tradicionales resultan impracticables en escenarios reales, lo que hace necesarios los enfoques heurísticos y metaheurísticos.

La solución se desarrolló como parte de una colaboración de investigación académica y se implementó como un motor de optimización capaz de generar programas de producción eficientes en tiempos de cómputo razonables.

La metodología propuesta integra varias estrategias metaheurísticas:

- GRASP (Greedy Randomized Adaptive Search Procedure)
- Variable Neighborhood Search (VNS)
- Iterated Local Search (ILS)
- Modelos metaheurísticos híbridos que combinan fases de construcción y de búsqueda local

El sistema evalúa los programas candidatos con métricas de desempeño como:

- Reducción de la tardanza total
- Tiempo de convergencia
- Capacidad de exploración
- Significancia estadística de los resultados

Se implementó un marco de validación estadística con la prueba de Tukey para determinar si las diferencias entre enfoques metaheurísticos eran estadísticamente significativas, asegurando rigor metodológico en la evaluación.

Los resultados experimentales mostraron que los enfoques híbridos que combinan GRASP y VNS superaron de forma consistente a los métodos aislados, en particular en las instancias de mayor tamaño.

El sistema se implementó en Python y se ejecutó en un entorno computacional controlado para garantizar reproducibilidad y evaluación de rendimiento.

Este proyecto es un trabajo aplicado de optimización y diseño de algoritmos que integra investigación de operaciones, ingeniería de algoritmos y sistemas de apoyo a la decisión industrial.

Lenguaje de programación

Python 3.x
Lenguaje principal para implementar los algoritmos metaheurísticos y las simulaciones experimentales en entornos de Job Shop Scheduling.

Bibliotecas principales

pandas — manipulación de datos, almacenamiento de resultados experimentales, representación de programas, exportación a CSV, seguimiento de rendimiento.
NumPy — cálculo numérico, inicialización de matrices, simulación de programas, operaciones vectorizadas.
sqlite3 — almacenamiento persistente de instancias de benchmark, recuperación estructurada de datos, experimentación sobre base de datos.
random — generación estocástica de soluciones, selección de candidatos en GRASP, exploración de vecindarios en VNS.
time — control de tiempos de ejecución, medición de convergencia, criterios de parada.
math — cálculos matemáticos y evaluación numérica.
Matplotlib — generación de diagramas de Gantt, visualización de makespan, análisis de rendimiento de la programación.

Estilo de arquitectura: aplicación de cómputo científico

Características:
- Experimentación algorítmica
- Optimización metaheurística
- Simulación iterativa
- Benchmarking de rendimiento

Algoritmos y áreas:
- GRASP
- Variable Neighborhood Search (VNS)
- Iterated Local Search (ILS)
- Optimización combinatoria
- Investigación de operaciones
- Análisis estadístico
- Algoritmos de scheduling

El código fuente no es público. El proyecto se presenta como un caso de estudio técnico que describe el diseño del sistema, la metodología y los resultados de rendimiento.

Stack tecnológico:

Python | Pandas | pip | Sqlite3 | Numpy | time | math | matplotlib | Seaborn | Scipy | Statmodels

Equipo