DETERMINACION Y CÁLCULO DE LA RUTA CRÍTICA
Para ilustrar los conceptos básicos del método de la ruta crítica (CPM), considere el ejemplo de la siguiente ilustración de la red AON de un proyecto, donde los nodos en forma de rombo representan eventos, los nodos en forma de círculo (con una letra o nombre como identificador) representan tareas y los arcos indican las relaciones de precedencia. Observe también que cada tarea (nodo) indica su duración esperada; en este ejemplo, las duraciones esperadas están dadas en meses. Es importante recordar que el cálculo de la ruta crítica supone que estas duraciones son determinísticas (es decir, conocidas y constantes).
Para ilustrar los conceptos básicos del método de la ruta crítica (CPM), considere el ejemplo de la siguiente ilustración de la red AON de un proyecto, donde los nodos en forma de rombo representan eventos, los nodos en forma de círculo (con una letra o nombre como identificador) representan tareas y los arcos indican las relaciones de precedencia. Observe también que cada tarea (nodo) indica su duración esperada; en este ejemplo, las duraciones esperadas están dadas en meses. Es importante recordar que el cálculo de la ruta crítica supone que estas duraciones son determinísticas (es decir, conocidas y constantes).
Este pequeño ejemplo, es claro que existen dos rutas en la red desde el nodo INICIO hasta el nodo FIN: INICIO-A-B-FIN e INICIO-C-FIN. Dado que para terminar todo el proyecto deben estar terminadas todas las tareas, es claro que se necesitan once meses para completarlo, suponiendo que los eventos INICIO y FIN no requieran tiempo y que la duración de las tareas sea justo la indicada. Así, el tiempo mínimo necesario para terminar un proyecto es igual a la longitud de la ruta más larga a través de la red. Esta ruta se conoce como ruta crítica y se indica con flechas más gruesas. La duración del proyecto, 11 meses, definida por la ruta crítica, se conoce también como el tiempo de ejecución del proyecto.
El pequeño ejemplo mostrado en la figura anterior ilustra también el concepto de tiempo holgura total o tiempo flotante. Como las tareas en la ruta INICIO-A-B-FIN solo requieren diez meses, para las tareas A y B pueden retrasarse hasta un mes sin demorar el tiempo de ejecución del proyecto. Así, la holgura asociada con las tareas A y B es un mes (a este tipo de holgura se le conoce como holgura total o flotante total). Debe notarse que esta holgura es una medida dependiente de la ruta; es decir, si la duración de la tarea A aumenta un mes (a ocho meses), la holgura total de la tarea B, así como la holgura total de la tarea A, se reducirá de un mes a cero.
La figura anterior también ilustra otros conceptos. De cada tarea y evento, el administrador del programa suele interesarse en conocer el tiempo más próximo en que cada tarea puede iniciar/terminar, así como el tiempo más lejano en el que cada tarea puede iniciar/terminar sin retrasar el tiempo de ejecución del proyecto. Suponiendo que el inicio del proyecto ocurre en el tiempo 0, las tareas A y C pueden iniciar en el tiempo 0 ya que el evento INICIO requiere un tiempo de 0.El tiempo de inicio es más próximo para el evento INICIO y el proyecto, denotado por ICINICIO, es cero. La tarea B puede iniciar tan pronto haya terminado la tarea A, por lo que ICB=7. De la misma manera, la tarea C puede iniciar en el tiempo 0, por lo que ICC=0. Por lo contrario, las tareas B y C pueden terminar hasta el tiempo 11 (ya que requieren 11 meses para terminar todo el proyecto, suponiendo que el evento FIN también requiere un tiempo de 0). Si TLj es el tiempo de terminación más lejano para alguna tarea j, TLB=11, mientras que TLA=8; esto indica que la tarea A, que precede en la tarea B, puede terminar hasta el tiempo 8. Estos cálculos se presentan en la siguiente figura.
El pequeño ejemplo mostrado en la figura anterior ilustra también el concepto de tiempo holgura total o tiempo flotante. Como las tareas en la ruta INICIO-A-B-FIN solo requieren diez meses, para las tareas A y B pueden retrasarse hasta un mes sin demorar el tiempo de ejecución del proyecto. Así, la holgura asociada con las tareas A y B es un mes (a este tipo de holgura se le conoce como holgura total o flotante total). Debe notarse que esta holgura es una medida dependiente de la ruta; es decir, si la duración de la tarea A aumenta un mes (a ocho meses), la holgura total de la tarea B, así como la holgura total de la tarea A, se reducirá de un mes a cero.
La figura anterior también ilustra otros conceptos. De cada tarea y evento, el administrador del programa suele interesarse en conocer el tiempo más próximo en que cada tarea puede iniciar/terminar, así como el tiempo más lejano en el que cada tarea puede iniciar/terminar sin retrasar el tiempo de ejecución del proyecto. Suponiendo que el inicio del proyecto ocurre en el tiempo 0, las tareas A y C pueden iniciar en el tiempo 0 ya que el evento INICIO requiere un tiempo de 0.El tiempo de inicio es más próximo para el evento INICIO y el proyecto, denotado por ICINICIO, es cero. La tarea B puede iniciar tan pronto haya terminado la tarea A, por lo que ICB=7. De la misma manera, la tarea C puede iniciar en el tiempo 0, por lo que ICC=0. Por lo contrario, las tareas B y C pueden terminar hasta el tiempo 11 (ya que requieren 11 meses para terminar todo el proyecto, suponiendo que el evento FIN también requiere un tiempo de 0). Si TLj es el tiempo de terminación más lejano para alguna tarea j, TLB=11, mientras que TLA=8; esto indica que la tarea A, que precede en la tarea B, puede terminar hasta el tiempo 8. Estos cálculos se presentan en la siguiente figura.
Como se indicó, los eventos se representan con rombos y siempre tienen duración cero. Los dos eventos INICIO y FIN indican los puntos inicial y final únicos de la red y del proyecto.
En este caso, existen cinco rutas de INICIO a FIN en la red. Estas cinco rutas y sus respectivas duraciones (o sea, la suma de las duraciones de las tareas en cada ruta) se dan en la siguiente tabla.
En este caso, existen cinco rutas de INICIO a FIN en la red. Estas cinco rutas y sus respectivas duraciones (o sea, la suma de las duraciones de las tareas en cada ruta) se dan en la siguiente tabla.
La ruta más larga (crítica) a través de la red (y por lo tanto el tiempo mínimo necesario para completar el proyecto) es la ruta 1, que necesita 35 semanas. Las flechas gruesas y los nodos en blanco señalan esta ruta crítica en la siguiente figura. Observe que puede haber más de una ruta crítica en un proyecto, pero por definición debe haber por lo menos una.
Como los proyecto de tamaño real tienen demasiados nodos para enumerar todas las rutas posibles, los creadores del método de la ruta crítica (CPM) desarrollaron una metodología que puede encontrar la ruta más larga en cualquier proyecto, sin importar su tamaño. De hecho, este es un problema relativamente sencillo que se basa en el proceso de programación dinámica.
Los cálculos para el CPM necesitan dos etapas para encontrar la ruta más larga atravesó de una red de precedencias.
ICi= tiempo de inicio más cercano para el nodo i
Al empezar, ICINICIO=0 por definición. El administrador avanza a las tareas A, B y C que salen del nodo INICIO; es claro que
ICA=ICB=ICC=0
Ya que el evento INICIO requiere un tiempo de 0. El administrador sigue a la tarea D. de la red sabe que la tarea D no puede iniciar hasta que la tareas A y B hayan terminado. Recuerde que la tarea A puede iniciar en el tiempo 0 y necesita 14 semanas, y que la tarea B puede empezar en el tiempo 0 y necesita 9 semanas. Entonces como la tarea D no puede iniciar hasta que ambas tareas, A y B, hayan terminado, el tiempo de inicio más cercano para la tarea D es igual al máximo entre el tiempo de terminación más cercano de las tareas A y B; esto es:
ICD=máx(ICA+14,ICB+9)
=máx(0+14,0+9)
=14
De manera similar, el tiempo de inicio más cercano para la tarea F es 26(ICD+12)=26 semanas, mientras que el tiempo de inicio más cercano para la tarea E es:
ICE=máx(ICD+12,ICC+20)
=máx(14+12,0+20)
=26
El tiempo de inicio más cercano para el evento final, FIN, es entonces:
ICFIN=máx(ICF+9,ICE+6)
=máx(26+9,26+6)
=35
En general, el tiempo de inicio más cercano para la i-esima tarea, inmediatamente precedida por las tareas j del conjunto Pi se calcula con la siguiente formula:
ICi=máx{ICj+tj para todas las tareas j en Pi}
Donde tj=duración de la tarea j.
Con base en el valor de ICFIN, el administrador del programa sabe que el proyecto no puede terminar en menos de 35 semanas (el tiempo de ejecución del proyecto) dada la duración estimada de las tareas del proyecto. Los resultados de los cálculos se dan en la figura pasada. Sin embargo, el administrador no sabe que tareas definen la o las rutas críticas hasta no realizar la segunda etapa (hacia atrás) de los cálculos del CPM.
En esta segunda etapa de los cálculos (hacia atrás), el administrador desea encontrar los tiempos por más lejanos en los que cada tarea o evento puede terminar; denota estos valores por:
TLi=tiempo más lejano de terminación para el nodo i
Casi siempre se establece TLFIN=ICFIN ya que el evento FIN no requiere tiempo ni costo; por lo tanto, TLFIN=35. Después el proceso se mueve hacia atrás a través de la red.
Como las tareas A y F son precedentes inmediatos del nodo FIN, primero se mueve a estos nodos. En ambos casos es claro que estas tareas pueden terminar hasta el tiempo 35 sin retrasar el tiempo de terminación más lejano del nodo FIN (y del proyecto). Así TLF=ICE=35, como se indicó en la figura anterior.
El administrador considera después de la tarea D y se pregunta ¿Cuál es el tiempo más lejano en que esta tarea pueda terminar sin que se retrase el tiempo más lejano de terminación de las tareas que siguen (tareas E y F)? esto es equivalente a calcular los tiempos de inicio más lejanos de las tarea E y F. como la tarea F puede terminar a más tardar en el tiempo 35, no puede iniciar después del tiempo 35-9=26. De manera similar, la tarea E no puede iniciar después del tiempo 35-6=29. Como la tarea D no puede ocasionar que las tareas F o E se retrasen, el tiempo de terminación más lejano de la tarea D deberá ser el menor de los valores 29 y 26; es decir:
TLD=mín(TLF-9,TLE-6)
=mín(35-9,35-6)
=26
El administrador continúa, de esta forma, calculando los tiempos de terminación más lejanos de las tareas A, B y C como sigue:
TLA=TLD-12=26-12=14
TLB=TLD-12=26-12=14
TLC=TLE-9=35-6=29
Por ultimo calcula el tiempo de terminación más lejano para el nodo INICIO del proyecto:
TLINICIO=mín(TLA-14, TLB-9, TLC-20)
=mín(14-14,14-9,29-20)
=mín(0,5,9)
=0
Es claro que el tiempo de terminación más lejano del nodo INICIO siempre debe ser igual a cero, ya que los nodos INICIO y FIN deben estar en la ruta crítica (más larga). En general, si la tarea j del conjunto Si sucede inmediatamente en la tarea i, entonces los cálculos del tiempo de terminación más lejano se encuentran usando la formula siguiente:
TLi=mín{TLj-tj para todas las tareas j del conjunto Si}
Donde tj=duración de la tarea j.
Cálculos con una hoja de cálculo
Los cálculos del CPM con los datos del ejemplo dado en la figura anterior se muestran en la siguiente figura.
Los cálculos para el CPM necesitan dos etapas para encontrar la ruta más larga atravesó de una red de precedencias.
- En la primera etapa se empieza en el modo de INICIO y se avanza hacia adelante por la red, determinando en cada nodo el tiempo más próximo en que la tarea o evento puede iniciar.
- En la segunda etapa de los cálculos se empieza en el nodo FIN y se retrocede por red determinando el tiempo más lejano en que una tarea o evento pueda terminar.
ICi= tiempo de inicio más cercano para el nodo i
Al empezar, ICINICIO=0 por definición. El administrador avanza a las tareas A, B y C que salen del nodo INICIO; es claro que
ICA=ICB=ICC=0
Ya que el evento INICIO requiere un tiempo de 0. El administrador sigue a la tarea D. de la red sabe que la tarea D no puede iniciar hasta que la tareas A y B hayan terminado. Recuerde que la tarea A puede iniciar en el tiempo 0 y necesita 14 semanas, y que la tarea B puede empezar en el tiempo 0 y necesita 9 semanas. Entonces como la tarea D no puede iniciar hasta que ambas tareas, A y B, hayan terminado, el tiempo de inicio más cercano para la tarea D es igual al máximo entre el tiempo de terminación más cercano de las tareas A y B; esto es:
ICD=máx(ICA+14,ICB+9)
=máx(0+14,0+9)
=14
De manera similar, el tiempo de inicio más cercano para la tarea F es 26(ICD+12)=26 semanas, mientras que el tiempo de inicio más cercano para la tarea E es:
ICE=máx(ICD+12,ICC+20)
=máx(14+12,0+20)
=26
El tiempo de inicio más cercano para el evento final, FIN, es entonces:
ICFIN=máx(ICF+9,ICE+6)
=máx(26+9,26+6)
=35
En general, el tiempo de inicio más cercano para la i-esima tarea, inmediatamente precedida por las tareas j del conjunto Pi se calcula con la siguiente formula:
ICi=máx{ICj+tj para todas las tareas j en Pi}
Donde tj=duración de la tarea j.
Con base en el valor de ICFIN, el administrador del programa sabe que el proyecto no puede terminar en menos de 35 semanas (el tiempo de ejecución del proyecto) dada la duración estimada de las tareas del proyecto. Los resultados de los cálculos se dan en la figura pasada. Sin embargo, el administrador no sabe que tareas definen la o las rutas críticas hasta no realizar la segunda etapa (hacia atrás) de los cálculos del CPM.
En esta segunda etapa de los cálculos (hacia atrás), el administrador desea encontrar los tiempos por más lejanos en los que cada tarea o evento puede terminar; denota estos valores por:
TLi=tiempo más lejano de terminación para el nodo i
Casi siempre se establece TLFIN=ICFIN ya que el evento FIN no requiere tiempo ni costo; por lo tanto, TLFIN=35. Después el proceso se mueve hacia atrás a través de la red.
Como las tareas A y F son precedentes inmediatos del nodo FIN, primero se mueve a estos nodos. En ambos casos es claro que estas tareas pueden terminar hasta el tiempo 35 sin retrasar el tiempo de terminación más lejano del nodo FIN (y del proyecto). Así TLF=ICE=35, como se indicó en la figura anterior.
El administrador considera después de la tarea D y se pregunta ¿Cuál es el tiempo más lejano en que esta tarea pueda terminar sin que se retrase el tiempo más lejano de terminación de las tareas que siguen (tareas E y F)? esto es equivalente a calcular los tiempos de inicio más lejanos de las tarea E y F. como la tarea F puede terminar a más tardar en el tiempo 35, no puede iniciar después del tiempo 35-9=26. De manera similar, la tarea E no puede iniciar después del tiempo 35-6=29. Como la tarea D no puede ocasionar que las tareas F o E se retrasen, el tiempo de terminación más lejano de la tarea D deberá ser el menor de los valores 29 y 26; es decir:
TLD=mín(TLF-9,TLE-6)
=mín(35-9,35-6)
=26
El administrador continúa, de esta forma, calculando los tiempos de terminación más lejanos de las tareas A, B y C como sigue:
TLA=TLD-12=26-12=14
TLB=TLD-12=26-12=14
TLC=TLE-9=35-6=29
Por ultimo calcula el tiempo de terminación más lejano para el nodo INICIO del proyecto:
TLINICIO=mín(TLA-14, TLB-9, TLC-20)
=mín(14-14,14-9,29-20)
=mín(0,5,9)
=0
Es claro que el tiempo de terminación más lejano del nodo INICIO siempre debe ser igual a cero, ya que los nodos INICIO y FIN deben estar en la ruta crítica (más larga). En general, si la tarea j del conjunto Si sucede inmediatamente en la tarea i, entonces los cálculos del tiempo de terminación más lejano se encuentran usando la formula siguiente:
TLi=mín{TLj-tj para todas las tareas j del conjunto Si}
Donde tj=duración de la tarea j.
Cálculos con una hoja de cálculo
Los cálculos del CPM con los datos del ejemplo dado en la figura anterior se muestran en la siguiente figura.
Para cada tarea y evento en el proyecto, el administrador de los predecesores y sucesores inmediatos que contribuyen a la base de los cálculos. Observe que los valores de los tiempos de inicio más cercanos (ICi) y de terminación más lejanos (TLi) corresponden a los valores dados en la figura anterior del diagrama.
Una vez que encuentra el tiempo de inicio más cercano (ICi) y de terminación más lejanos (TLi) para cada tarea, el administrador calcula el tiempo de terminación más cercano (TCi) y el tiempo de inicio más lejano (ILi) para todas las tareas. Si ICi representa el dinero más cercano en el que la tarea i puede iniciar, entonces ICi+ti representa el tiempo más cercano en el que la tarea i puede terminar (dado que ti representa la duración de la tarea). De la misma manera, si TLi denota el tiempo de terminación más lejano de la tarea i, entonces TLi-tidebe ser igual al tiempo más lejano en el que la tarea i puede iniciar.
Bibliografía
LIBRO: Administración de Proyectos
AUTOR: Ted Klastorin
EDITORIAL: Alfaomega
LIBRO: Método de la Ruta Crítica y su Aplicación a la Construcción
AUTOR: James M. Antill,
Ronald W. Woodhead
Fernando L. Echegaray Moreno
EDITORIAL: Limusa - Wiley, 1967
Una vez que encuentra el tiempo de inicio más cercano (ICi) y de terminación más lejanos (TLi) para cada tarea, el administrador calcula el tiempo de terminación más cercano (TCi) y el tiempo de inicio más lejano (ILi) para todas las tareas. Si ICi representa el dinero más cercano en el que la tarea i puede iniciar, entonces ICi+ti representa el tiempo más cercano en el que la tarea i puede terminar (dado que ti representa la duración de la tarea). De la misma manera, si TLi denota el tiempo de terminación más lejano de la tarea i, entonces TLi-tidebe ser igual al tiempo más lejano en el que la tarea i puede iniciar.
Bibliografía
LIBRO: Administración de Proyectos
AUTOR: Ted Klastorin
EDITORIAL: Alfaomega
LIBRO: Método de la Ruta Crítica y su Aplicación a la Construcción
AUTOR: James M. Antill,
Ronald W. Woodhead
Fernando L. Echegaray Moreno
EDITORIAL: Limusa - Wiley, 1967