Job Shop - Scheduling

JOB SHOP

M máquinas N trabajos Diferente Secuencia

Los trabajos tienen operaciones realizadas en máquinas especificas. Los trabajos se procesan en el orden necesario para producir el producto, es decir, cada trabajo tiene una secuencia diferente,El tiempo de procesamiento depende del trabajo j en la maquina i: Pij

Representación Gráfica

Grafo Disyuntivo

Flujo de Trabajo

Gantt

Complejidad

Garey et al. (1976) demostró que la mayoría de los problemas y extensiones de Job shop son NP-Completos. Otros autores aseguran que resultan ser de la categoría de NP-Hard completamente.

Garey et al. (1976)

Complejidad frente a otros problemas

Formulación Disyuntiva - Jm||

Notación

Con esta notación se puede realizar la solución a un problema de Job Shop según la función objetivo que se quiera evaluar. Con las restricciones se verifica que se cumplan las restricciones de secuencia entre trabajos y garantizar que las maquinas procesen un trabajo a la vez.

www.loremipsum.com

Este problema permite evaluar varias reglas de despacho para la elección de los trabajos: SPT, LPT, MRW, Reglas lexicográficas., etc. En cuanto a su optimilidad recomiendo ver: Hutchison (1990).

Jm||Non Delay

Formulación Disyuntiva - Jm||

Un programación Non Delay esta basada en la premisa que en cuanto un trabajo puede ser procesado en una maquina y a su vez la maquina esta disponible, se programa. De esta forma se evitan retrasos.

Hutchison. (1990)

Algoritmo

Jm||CmaxMIP

J2||Cmax

Puede ser solucionado en tiempo ¡Polinomial! N trabajos 2 Maquinas.

Mediante optimización se puede solucionar el problema, tomando como base la fomulación disyuntiva mencionada anteriormente.

Algoritmo de Jackson

Formulación Completa

Ejemplo

Notación

Branch & Bound - Jm||CmaxMetodo Exacto

Mediante la generación de particiones al espacio de solución lo que se espera es ramificar en cuanto a como se van estableciendo el orden de los trabajos en las maquinas. Un hijo a diferencia de su padre en este algoritmo tiene una maquina más ya organizada.

Ejemplo del Arbol

Algoritmo

Heuristica cuello de botella móvil- Jm | | Cmax

•Es un Método aproximado. Toma las máquinas identificadas como cuellos de botella, una por una. Despues de secuenciar una máquina, las previamente secuenciadas son reoptimizadas. El articulo original es Adams et al (1988)

Adams et al. (1988)

Algoritmo