Programación de la Producción
Dado un conjunto de trabajos, una serie de máquinas y una serie de restricciones, ¿en qué orden hay que procesarlos para optimizar una medida de eficiencia? La programación de la producción (production scheduling) busca responder esta pregunta de forma sistemática.
1. Fundamentos
Parámetros del problema
Un problema de secuenciación se describe con tres elementos: la configuración de la planta, las restricciones y la medida de eficiencia (notación α | β | γ).
Configuraciones (α)
- 1 — Máquina única
- Pm — Máquinas paralelas idénticas (m = número de máquinas)
- Fm — Taller en flujo (flowshop): todos los trabajos siguen la misma ruta
- Jm — Taller de trabajo (jobshop): cada trabajo puede tener su propia ruta
- Om — Taller abierto (openshop)
Medidas de eficiencia (γ)
- Cmax — Makespan: tiempo de fin del último trabajo
- ∑Cj — Suma de tiempos de finalización
- Lmax — Máximo retraso (puede ser negativo si adelantado)
- Tmax — Máximo tardanza (tardiness, solo positivo)
- ∑Tj — Suma de tardanzas
- ∑Uj — Número de trabajos retrasados
Tipos de programas
Programas activos
Ningún trabajo puede empezar antes sin retrasar otro. Son necesariamente candidatos a óptimo.
Programas sin retraso
Subconjunto de los activos: ninguna máquina se deja ociosa pudiéndose poner a trabajar. Más fáciles de construir, pero pueden no contener el óptimo.
Vídeos: Fundamentos
Planificar y programar
Medidas de eficiencia en secuenciación
Características de las herramientas de programación de producción en la práctica
Las funciones de lanzamiento y control de producción
2. Máquina Única (1 | · | ·)
El caso de una sola máquina es la piedra angular de la programación de producción. Sus soluciones permiten entender la lógica de las reglas de prioridad y sirven de base para la reducción del problema en configuraciones complejas.
Shortest Operating Time: ordenar por tiempo de proceso creciente. Minimiza la suma de tiempos de finalización ∑Cj y reduce el tiempo de espera medio.
Óptimo para 1 || ∑Cj
Earliest Due Date: ordenar por fecha de entrega prometida creciente. Minimiza el máximo retraso Lmax.
Óptimo para 1 || Lmax (Teorema de Jackson)
Algoritmo de Moore: minimiza el número de trabajos con retraso ∑Uj. Construye la secuencia eliminando iterativamente el trabajo con mayor tiempo de proceso cuando hay retraso.
Óptimo para 1 || ∑Uj
Apparent Tardiness Cost with Setups: regla de prioridad compuesta que incorpora coste de tardanza, tiempo de proceso y tiempo de preparación (setup) dependiente de la secuencia.
Para 1 | sij | ∑wjTj
Vídeos: Máquina única
Secuenciación en problemas monomáquina con tiempos de preparación
Secuenciación en una máquina con la regla SOT
La regla EDD y MOORE
Uso de la heurística ATCS
Uso combinado de la regla ATCS y un algoritmo cuello de botella
Branch and Bound para secuenciación monomáquina con fechas de llegada
3. Taller en Flujo — Flowshop (Fm | · | Cmax)
En un taller en flujo todos los trabajos siguen la misma secuencia de máquinas (M1 → M2 → … → Mm). El objetivo más habitual es minimizar el makespan Cmax.
F2 — Algoritmo de Johnson
Para dos máquinas y minimización de Cmax, el algoritmo de Johnson obtiene la solución óptima en O(n log n): los trabajos con min(pj1, pj2) = pj1 van al frente, los demás al final.
Fm — Heurísticas para m máquinas
- Palmer: construye un índice de pendiente para cada trabajo y ordena descendentemente
- CDS (Campbell, Dudek & Smith): aplica Johnson m−1 veces con tiempos agregados
- NEH (Nawaz, Enscore & Ham): construye la secuencia insertando trabajos de mayor a menor suma de tiempos en la mejor posición — la más eficaz en la práctica
Cálculo de makespan mediante grafos
El makespan en flowshop puede calcularse con un grafo de precedencias o, de forma equivalente, con la fórmula recursiva:
donde C[j][i] es el tiempo de finalización del trabajo j en la máquina i.
Sistemas con bloqueo
En sistemas sin almacén intermedio entre máquinas (blocking), un trabajo terminado en una máquina no puede avanzar hasta que la siguiente quede libre. Esto modifica los tiempos de finalización y hace el problema considerablemente más difícil.
Vídeos: Taller en flujo
Cálculo de fechas de fin en talleres de flujo
Secuenciación en taller de flujo de dos máquinas (Johnson)
Algoritmo heurístico de Palmer para flowshop de m máquinas
Algoritmo heurístico CDS para flowshop de m máquinas
Secuenciación en taller de flujo con la regla NEH
Uso de grafos para calcular fechas en taller flowshop
Secuenciación en taller de flujo de tres máquinas
Resolución de un caso de secuenciación en taller de flujo
Diferencias entre sistemas con capacidad de almacenamiento limitada
Cálculo de fechas de fin con bloqueo (sistema sin almacenes intermedios)
4. Taller de Trabajo — Jobshop (Jm | · | Cmax)
En el taller de trabajo cada trabajo puede seguir una ruta diferente por las máquinas. Es uno de los problemas combinatorios más difíciles (NP-hard para m ≥ 2).
Representación mediante grafos
Un jobshop se modela como un grafo disyuntivo: arcos conjuntivos (fijos) representan la secuencia de operaciones de cada trabajo; arcos disyuntivos (a orientar) representan los recursos compartidos. La longitud del camino crítico es el makespan.
Shifting Bottleneck
Heurística muy efectiva: identifica iterativamente la máquina cuello de botella, resuelve el subproblema de una máquina para ella y fija su secuencia. Continúa con la siguiente máquina más saturada.
Programas activos vs sin retraso en jobshop
A diferencia del flowshop, en jobshop la búsqueda exhaustiva de programas activos ya es computacionalmente costosa. Se utilizan técnicas de lanzamiento (dispatching) para construir de forma eficiente secuencias activas o sin retraso como punto de partida para la búsqueda local.
Vídeos: Taller de trabajo
Secuenciación en taller de trabajo de dos máquinas
Representación de un problema de secuenciación mediante grafos
Algoritmo Shifting Bottleneck para jobshop
Secuenciación mediante reducción al problema del cuello de botella
Algoritmos de lanzamiento para generación de secuencias activas
Algoritmos de lanzamiento para secuencias sin retraso
5. Fabricación Contra Stock
Cuando se fabrica para reponer inventario (make-to-stock), el criterio ya no es solo el makespan o la tardanza sino la interacción entre el programa de producción y el nivel de inventario. Los trabajos (lotes de reposición) tienen prioridad dinámica que depende del stock actual y del ritmo de consumo.
Ratio de agotamiento
El ratio de agotamiento de un artículo es el cociente entre su nivel de inventario y su tasa de demanda. Indica cuánto tiempo queda antes de quedar sin stock. Las reglas de prioridad en fabricación contra stock suelen usar este ratio para secuenciar.
Temporización
La temporización temprana (producir antes de que se agote) y tardía (esperar al máximo) son dos estrategias con impactos distintos sobre el inventario medio y las roturas de stock. La tardía minimiza el inventario pero aumenta el riesgo.
Vídeos: Fabricación contra stock
Ratio de agotamiento y tiempo de preparación en sistemas de fabricación contra stock
Cálculo del tamaño de lote en sistemas de fabricación contra stock
Secuenciación y temporización temprana en sistemas de fabricación contra stock
Secuenciación y temporización tardía en sistemas de fabricación contra stock
Roturas de stock en secuenciación contra inventario
Relación entre inventario y flujo en un problema de secuenciación
6. Reprogramación
En la práctica, los programas calculados se alteran continuamente por perturbaciones: averías, trabajos urgentes, cambios de prioridad, falta de material. La reprogramación estudia cómo actualizar el programa de forma eficiente sin desechar el trabajo de planificación.
Reprogramación total
Se vuelve a calcular el programa desde cero con el estado actual de la planta. Obtiene la mejor solución posible pero es costosa computacionalmente.
Reprogramación parcial
Se modifica lo mínimo del programa vigente para absorber la perturbación. Minimiza el nerviosismo del sistema (cambios de secuencia) y es más rápida.