Programación Job-Shop (GA)

¿Qué es la programación Job-Shop y cómo la resuelve un GA?

Asigna operaciones de múltiples trabajos a máquinas para minimizar makespan o tardanza. Cada trabajo tiene una secuencia ordenada de operaciones en máquinas específicas.

JSSP es NP-difícil. Un GA evoluciona una población de programas candidatos. Cruce POX preserva el orden; mutación swap intercambia posiciones.

JSSP es crítico en manufactura. 10-15% de reducción en makespan aumenta directamente la capacidad sin inversión de capital.

Formula: Makespan = max(tiempos de finalización) Tardanza = Σ max(0, Fin_j − Fecha límite_j) GA: Inicialización → Evaluación → Selección → POX → Mutación → Iteración

Ejemplo de cálculo

3 trabajos, 3 máquinas. Trabajo 1: M1(3)→M2(2)→M3(4). Makespan óptimo = 12. GA (población 100, 200 generaciones) típicamente lo encuentra o dentro del 5%.

Cuándo usar esta calculadora

• Un planificador de producción programando múltiples trabajos en un taller mecánico con equipo compartido para minimizar el tiempo de finalización
• Un ingeniero de manufactura evaluando el impacto de agregar una nueva máquina o cambiar secuencias de operación en el rendimiento general
• Un programador en una imprenta o fábrica de semiconductores determinando prioridades de trabajos para cumplir fechas de entrega del cliente con mínima tardanza
• Un investigador de operaciones comparando la programación basada en GA contra los métodos actuales de programación manual o por reglas de prioridad

Errores comunes a evitar

• Establecer un tamaño de población demasiado pequeño para problemas complejos — con 10+ trabajos y 5+ máquinas, use al menos 100-200 individuos para mantener la diversidad genética y evitar convergencia prematura
• Ejecutar muy pocas generaciones y aceptar una solución subóptima — monitoree si el fitness sigue mejorando; si se estabiliza, la solución ha convergido; si aún mejora, aumente las generaciones
• Ignorar tiempos de liberación y fechas de entrega cuando existen — sin estas restricciones, el GA optimiza solo el makespan, lo que puede producir programas que violan requisitos de tiempo del mundo real
• No ejecutar el GA múltiples veces con diferentes semillas aleatorias — el GA es estocástico; una sola ejecución puede quedar atrapada en un óptimo local; ejecute 3-5 veces y tome el mejor resultado

Cómo interpretar los resultados

• Si la tardanza total es cero, todos los trabajos se completan antes de sus fechas de entrega — el programa es factible y el enfoque debería cambiar a reducir aún más el makespan
• Si el makespan está cercano a la suma de tiempos de procesamiento en la máquina cuello de botella, el programa está cerca del óptimo — queda poco margen de mejora
• El diagrama de Gantt revela tiempo ocioso en las máquinas: grandes brechas indican ineficiencia de programación o restricciones de secuenciación inevitables

Normas y referencias relacionadas

• Garey, Johnson & Sethi (1976) — establecieron la NP-dureza de la minimización del makespan en el job-shop
• Makespan (C_max) y tardanza total — las funciones objetivo estándar en la programación de la producción
• Algoritmos genéticos (Holland, 1975) — la clase de metaheurística aplicada aquí para explorar el espacio de programaciones

Preguntas frecuentes

¿Cómo configurar parámetros del GA?

Población 50-200, tasa de mutación 0,05-0,15, 200-500 generaciones. Para 10+ trabajos use población ≥100, generaciones ≥300.

¿Diferencia entre optimizar makespan y tardanza?

Makespan minimiza el tiempo total — ideal para maximizar capacidad. Tardanza prioriza cumplir fechas límite. Pueden entrar en conflicto; optimización multi-objetivo puede equilibrar ambos.