Demo del Cálculo de la Ruta Crítica por el Método CPM, Aplicado al problema de un Taller de Manufactura
(CPM in The Job Shop Scheduling Problem)
Para calcular la Ruta Crítica de un JSSP, se requiere partir de una solución (schedule) del problema. En la Figura 1 se representa una solución al problema de 3x3 mediante un digrafo. Se sabe que el problema de calcular la Ruta Crítica en un digrafo es de complejidad polinomial [1] y la implementación del algoritmo CPM también es de complejidad polinomial [2]. El demo presenta el procedimiento CPM [3] en un digrafo de JSSP para el cálculo de la Ruta Crítica partiendo de una solución.
La Figura 1. Presenta una solución para el problema de 3x3. El grafo representa un conjunto de tres máquinas que tienen que ejecutar tres trabajos. El trabajo uno requiere de la ejecución de las operaciones 1 , 2 y 3 en ese orden de precedencia. El trabajo dos requiere de la ejecución de las operaciones 4 , 5 y 6 en ese orden de precedencia. El trabajo tres requiere de la ejecución de las operaciones 7 , 8 y 9 en ese orden de precedencia. El digrafo presenta tres subgrafo los cuales cada uno tiene una ruta de tipo Hamilton [1], cada uno de estos subgrafos representan una máquina. La máquina 1, realiza las operaciones 1, 7 y 5. La máquina 2, realiza las operaciones 2, 6 y 8. La máquina 3 realiza las operaciones 3, 4 y 9.
Figura 1. Un schedule para un JSSP de 3x3
La Figura 2. Acomoda el JSSP para la aplicación del método CPM. Se toman a las operaciones como los eventos y las actividades como el intervalo entre un par de eventos (i, j). En cada evento i se define su tiempo de actividad para cada actividad (i, j).
Figura 2. Preparación del JSSP para aplicar CPM. Eventos y Actividades
La Tabla 1, presenta el cálculo del máximo tiempo más próximo (Earliest Time) y la Tabla 2, presenta el cálculo del mínimo tiempo más lejano (Latest time)
Tabla 1. Cálculo del máximo tiempo más próximo (Earliest Time)
La Figura 3, presenta los resultados obtenidos en cada evento del cálculo del máximo tiempo más próximo (Earliest time)
Figura 3. Representación del máximo tiempo más próximo (Earliest time)
Tabla 2. Cálculo del mínimo tiempo más lejano (Latest Time)
La Figura 4, presenta los resultados obtenidos en cada evento del cálculo del mínimo tiempo más lejano (Latest time).
Figura 4. Representación del mínimo tiempo más lejano (Latest time)
La Tabla 3, presenta los cálculos de las holguras de cada evento y actividad. De esta manera se encuentra el camino de la ruta crítica y las operaciones que pertenecen a ella. El color amarillo marca en la tabla los eventos (operaciones) y actividades que son parte de la ruta critica. La Figura 5. Muestra en el digrafo de JSSP en color verde el camino de la ruta crítica.
Tabla 3. Holguras (slack time) por cada evento y cada actividad
Figura 5. Ruta crítica obtenida por CPM para JSSP
Referencias
1.- Michael R. Garey, David S. Jonson, Computers and intractability a guide to the theory of NP- completeness . W.H. Freeman and Company.
2.- Chanas, S. and Zielinski, P., The Computational Complexity of the Critical Problems in a Network with Interval Activity Times, European Journal of Operational Research 136, 541-550, 2002.
3.- Hiller, F. S. and Lieberman, G. J., Introduction to Operations Research, ISBN: 0-07-113989-3, International Editions, 1995.
