Cómo obtener la Ruta Crítica de un Proyecto (CPM) con OM Explorer en Excel

El el artículo Cómo obtener la Ruta Crítica de un Proyecto (Critical Path Method) describimos de forma detallada cómo las holguras de las actividades de un proyecto y la ruta o camino más largo (no necesariamente único) que determina la duración de un proyecto. Como complemento a lo anterior a continuación presentamos cómo desarrollar este procedimiento de forma sencilla haciendo uso de OM Explorer. Para este propósito utilizaremos como ejemplo un proyecto que considera un total de 12 actividades que se muestran a continuación junto al tiempo esperado para completar cada una de las actividades (en meses) y la relación de predecesores.

actividades-proyecto-ruta-c

En primer lugar y una vez instalado el complemento OM Explorer en Excel ingresamos a Solvers (como se aprecia en la esquina superior izquierda en la imagen a continuación) y luego seleccionamos Project Management y Single Time Estimate.

project-management-om-explo

Luego en la pestaña Inputs del archivo se ingresan las actividades, el tiempo requerido para completarlas y las relaciones de predecesores. La plantilla permite implementar hasta 4 predecesores por actividad lo que es claramente suficiente para nuestro ejemplo.

inputs-proyecto-om-explorer

Una vez incorporadas la totalidad de las actividades en Inputs podemos revisar los resultados obtenidos en la hoja Results. Se observa el tiempo para completar el proyecto (15,5 meses) y con color rojo se destacan las actividades críticas (con holgura igual a cero), a saber, A-B-D-G-H-I-K-L, las que en dicho orden determinan la ruta crítica del proyecto (en este ejemplo única). Adicionalmente tanto para las actividades pertenecientes a la ruta crítica como aquellas con holgura mayor a cero se detalla el inicio más cercano (Early Start), término más cercano (Early Finish), inicio más lejano (Late Start) y término más lejano (Late Finish).

ruta-critica-con-om-explore

OM Explorer entrega adicionalmente una Carta Gantt donde se observa las actividades críticas en color rojo (con holgura o slack igual a cero), el tiempo de las actividades no críticas en color amarillo y el tiempo holgura de las actividades no críticas en color celeste, lo cual permite interpretar de forma intuitiva los resultados obtenidos.

Cálculo de los Beneficios Esperados de un Proyecto utilizando PERT

Un aspecto usual en la Gestión de Proyectos es enfrentar incentivos económicos por entregas anticipadas o a tiempo en base a la planificación preliminar y adicionalmente multas o cargos por entregas atrasadas o tardías. En este contexto el método PERT (Program Evaluation and Review Technique) permite incorporar de forma explícita la incertidumbre asociada a los tiempos requeridos para completar cada una de las actividades de un proyecto.

Beneficios Esperados de un Proyecto utilizando PERT

En el siguiente ejemplo se presenta la situación de un proyecto que consta de 9 actividades, cuyas relaciones de precedencia y tiempos en días (pesimista, más probable y optimista) se resumen a continuación:

tabla-proyecto-pert

Donde N\sim (\mu ,\sigma ^{2}) y los tiempos están en días.

Se desea completar el proyecto al cabo de 40 días a contar del inicio de las actividades. En caso de terminar antes de dicho plazo se estima que se accederá a un incentivo monetario de $200.000, no obstante, en caso contrario se asumirá una pérdida de $15.000 por cada día de atraso con un tope máximo de $30.000 (sobre los beneficios estimados). ¿Cuál es la ruta crítica del proyecto?, ¿Cuáles son los beneficios esperados del proyecto?.

Sabemos que el tiempo esperado para cada actividad se obtiene de Te=\frac{(a+4m+b)}{6}, por ejemplo, Te_{A}=\frac{(6+4*7+8)}{6}=7. Adicionalmente la varianza se obtiene de \sigma ^{2}=\frac{(b-a)^{2}}{36}, por ejemplo, \sigma ^{2}_{A}=\frac{(8-6)^{2}}{36}=\frac{1}{9}\cong 0,111. Con la ayuda de Excel resulta sencillo replicar el procedimiento para el resto de las actividades como se muestra a continuación:

pert-con-tiempo-esperado-y-

Considerando el Tiempo Esperado (Te) para cada una de las actividades generamos un diagrama de proyecto que nos permita identificar la Ruta Crítica y las holguras (en días) para cada una de las actividades. De esta forma se obtiene que A-D-F-H es la ruta crítica del proyecto con un tiempo esperado para completar éste de 39 días.

diagrama-proyecto-pert

Donde los valores con color rojo en la esquina superior izquierda de cada nodo representan el inicio más cercano; los valores con color azul de la esquina superior derecha el término más cercano; los valores de la esquina inferior izquierda con color naranjo el inicio más lejano y finalmente los números con color verde en la esquina inferior derecha representan el término más lejano.

A continuación se requiere estimar la probabilidad de completar el proyecto antes de 40 días, caso en el cual se accede a un beneficio de $200.000.

\mathbb{P}[T<40]=\mathbb{P}[Z_{\alpha }<\frac{40-39}{\sum {\sigma _{RC}}^{2}}]=\frac{40-39}{\sqrt{(\frac{1}{9})+(\frac{4}{9})+(\frac{16}{9})+4}}\cong0,6544

El beneficio esperado en este escenario sería $200.000*0,6544=$130.880.

Por otra parte la probabilidad de que el proyecto demore más de 41 días se obtiene de la siguiente forma:

\mathbb{P}[T>41]=\mathbb{P}[1-Z_{\alpha }<\frac{41-39}{\sum {\sigma _{RC}}^{2}}]=\frac{41-39}{\sqrt{(\frac{1}{9})+(\frac{4}{9})+(\frac{16}{9})+4}}\cong0,2134

Con un beneficio esperado de $170.000*0,2134=$36.278.

Finalmente evaluamos el caso donde el tiempo del proyecto se encuentra en el intervalo entre 40 y 41 días.

\mathbb{P}[T\geq40]+\mathbb{P}[T\leq 41]=0,1322

Siendo el beneficio esperado de este escenario $185.000*0,1322=$24.457.

En consecuencia el beneficio esperado asociado a completar el proyecto es de $191.615 ($130.880+$36.278+$24.457).

Cómo determinar la Duración Óptima de un Proyecto a través del Análisis de Crashing

La Programación Lineal como hemos analizado anteriormente provee una forma eficiente para enfrentar el problema de cómo reducir la duración de un proyecto de la forma más económica posible (Análisis de Crashing) en el contexto de la aplicación del Método de Ruta Crítica (CPM) para la gestión de proyectos. Adicionalmente en algunas situaciones se suele enfrentar costos de penalización en la medida que el proyecto se entregue más tarde de lo comprometido o estimado, como también incentivos por entregas anticipadas que no vayan en desmedro de la calidad del proyecto.

Consideremos el siguiente ejemplo para el cálculo de la Duración Óptima de un Proyecto (el tiempo está medido en días y el costo en dólares):

tabla-datos-proyecto-crashi

Por ejemplo la Actividad F tiene una duración normal de 4 días a un costo de 600 dólares y se puede comenzar una vez terminadas las Actividades B y E (predecesores). Si se desea apurar (hacer «crash») en la Actividad F, el menor tiempo que se puede adoptar es de 2 días (es decir, la reducción máxima es 2 días), donde por cada día que se reduce la duración de dicha actividad se incurre en un costo adicional de 175 dólares. De esta forma, por ejemplo, si se quisiera reducir la duración de la Actividad F de 4 a 3 días, el costo sería de 775 dólares (600+175).

Asuma que la fecha de entrega del proyecto es el día 10. La compañía debe pagar 170 dólares por cada día de atraso. Encuentre el número óptimo de días que debe durar el proyecto a través del análisis de crashing y el costo total del proyecto (incluyendo posibles multas por atraso).

Indique claramente las actividades donde realice crashing. Dibuje el diagrama del proyecto de la alternativa que se propone (el proyecto con el costo más bajo), representando el nombre de cada actividad al interior de los respectivos nodos. Para cada actividad calcule los siguientes indicadores: IC, TC, IL, TL. Luego obtenga explícitamente la holgura de cada actividad y la(s) ruta(s) crítica(s) del proyecto.

A continuación se define un modelo de optimización lineal propuesto para abordar el problema:

Variables de Decisión:

variables-crashing

Parámetros:

parametros-crashing-optimo

Función Objetivo: Consiste en minimizar el costo de terminar el proyecto en K días, donde 3.175 corresponde al costo en dólares de desarrollar el proyecto con las actividades en tiempo normal y la expresión en la sumatoria es el costo incremental de disminuir la duración del proyecto.

funcion-objetivo-crashing-o

Restricciones:

Cada actividad se puede reducir (de ser posible) dentro del límite máximo de reducción permisible:

xi-menor-o-igual-a-mi

Relaciones de predecesores entre las actividades y el tiempo de inicio y reducción:

relacion-predecesores-crash
Definición del tiempo objetivo para el proyecto:
tiempo-objetivo-crashing
No negatividad de las variables de decisión:
no-negatividad-crash

Una vez definido el modelo de Programación Lineal se implementa computacionalmente haciendo uso de Solver de Excel. Para ello será necesario sensibilizar los resultados del modelo para valores del parámetro K en el intervalo de [10,15] días (el lector puede corroborar que la duración del proyecto si cada actividad mantiene su duración normal es de 15 días). La solución óptima se resume a continuación:

solucion-crashing-solver

El tiempo óptimo para completar el proyecto corresponde a 12 días, con un costo total (incurriendo multas por atraso) de 3.890 dólares. El gráfico a continuación muestra el valor de la función objetivo (costo total) para distintos valores de duración del proyecto.

costo-proyecto-versus-tiemp

A continuación desarrollamos el diagrama del proyecto donde se observa que existen 2 rutas críticas: A-B-F y A-C-E-F, con una duración de 12 días. Notar que la única actividad que no es crítica con holgura positiva (de 1 día) es la Actividad D.

ruta-critica-crashing

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?

[sociallocker]Crashing Óptimo[/sociallocker]

Formulación y Resolución de un Modelo de Programación Lineal para reducir la duración de un Proyecto (Crashing)

En la Gestión de Proyectos uno de los aspectos claves es determinar los costos asociados a terminar el proyecto en un tiempo determinado. Del mismo modo, resulta de particular interés poder enfrentar de forma eficiente el problema de cómo reducir la duración del mismo de la forma más económica posible, partiendo de la premisa que ciertas actividades eventualmente se podrían desarrollar en un tiempo menor al estimado inicialmente luego de asignar una mayor cantidad de recursos. En este contexto el siguiente artículo aborda la problemática anterior a través de la formulación y resolución computacional de un modelo de optimización lineal.

Consideremos el siguiente proyecto que consta de 12 tareas estrictamente necesarias, donde la relación de predecesores, tiempos (en semanas) y costos se resume en la tabla a continuación:

tabla-proyecto-crashing

Por ejemplo la actividad I tiene puede comenzar una vez completadas las actividades F y H y su tiempo estimado es de 1,5 semanas con un costo normal de $75. Sin embargo la actividad I se puede apurar (lo que comúnmente se conoce como «crash» o «crashing») de modo que su duración pueda ser de 0,5 semanas pero con un costo mayor de $135. En consecuencia la máxima reducción permisible para dicha tarea es de 1 semana (1,5 – 0,5 semanas) con un costo adicional de $60. Asumiremos adicionalmente que existe proporcionalidad entre el tiempo de reducción y el costo adicional, por ejemplo, si quisiéramos reducir la actividad I en 0,5 semanas (es decir, pasar de 1,5 a 1,0 semanas) el costo de la actividad sería $105 ($75+0,5*$60) y el costo adicional (sobre el costo normal) es de $30.

A continuación determinamos la duración del proyecto utilizando el Método de Ruta Crítica (CPM), considerando los tiempos normales estimados para cada actividad.

diagrama-proyecto-crashing

El proyecto tiene una duración estimada de 15,5 semanas y existe una única ruta crítica: A-B-D-G-H-I-K-L (notar que todas las actividades en esta ruta tienen holgura igual a cero). El costo del proyecto es de $2.620 y se obtiene simplemente sumando los costos normales de cada una de las actividades. La notación que hemos utilizado es:

notacion-proyecto

Donde IC: Inicio más Cercano; TC: Término más Cercano; IL: Inicio más Lejano; TL: Término más Lejano; TN: Tiempo Normal, HOLG: Holgura. De esta forma, por ejemplo, la actividad I tiene un tiempo normal de 1,5 semanas y holgura igual a cero, es decir, si se retrasa esta actividad el proyecto también se retrasará.

En este contexto, el siguiente modelo de Programación Lineal permite abordar de forma óptima el problema de cómo reducir la duración del proyecto de la forma más económica posible, mediante la reducción del tiempo de las actividades (en particular de las actividades pertenecientes a la(s) ruta(s) crítica(s)). Cabe destacar que en la actualidad existen softwares que facilita este tipo de procedimientos (Crashing) como por ejemplo WINQSB.

Variables de Decisión:

variables-de-decision-crash

Parámetros:

parametros-crashing

Función Objetivo: Se buscar minimizar el costo adicional asociado al proyecto luego de hacer el «crashing» necesario para completar el proyecto en un tiempo determinado. Notar que podríamos agregar en la función objetivo como constante el costo normal del proyecto ($2.620) en donde en dicho caso la interpretación del valor óptimo sería el costo total del proyecto que tiene duración de K semanas.

funcion-objetivo-crashing

Restricciones:

Cada actividad se puede reducir (de ser posible) dentro del límite máximo de reducción permisible:

restriccion-reduccion-activ

Relaciones de predecesores entre las actividades y el tiempo de inicio y reducción:

restricciones-predecesores-

Por ejemplo en conjunto las inecuaciones (3) y (4) representan que la semana de inicio para la actividad D será mayor o igual a la semana de término (luego de una eventual reducción) de la que termine más tarde entre sus actividades predecesoras (B y C). Adicionalmente hemos definido una actividad «ficticia» o de término llamada «M» la cual tiene como predecesoras a aquellas actividades que terminan una ruta para el proyecto (no necesariamente crítica) y nos permitirá estimar la duración del proyecto.

Definición del tiempo objetivo para el proyecto:

restriccion-tiempo-objetivo

En la resolución computacional con Solver de Excel se puede simular para distintos valores del parámetro K de modo de ver cómo cambian los resultados. La mínima duración del proyecto estará dada por el menor valor de K que permite generar una instancia factible para el modelo de optimización.

No negatividad de las variables de decisión:

no-negatividad-crashing

Los resultados se muestran en la tabla a continuación donde la mínima duración del proyecto corresponde a 8,5 semanas con un costo total de $3.295 ($675 adicional al costo normal del proyecto). En las celdas color amarillo (variables de decisión) se puede apreciar la solución óptima donde queda explícito cuándo comienza la actividad y cuánto se reduce respecto a su tiempo normal. Por ejemplo la actividad G comienza al cabo de 2,5 semanas (a contar del inicio del proyecto) y su duración normal se reduce en 1,5 semanas (es decir pasamos de un tiempo normal de 3 a 1,5 semanas).

crashing-solver-proyecto

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?

[sociallocker]Muchas Gracias!. Descarga aquí el Archivo Excel con la resolución de este problema[/sociallocker]

Cómo obtener la Ruta Crítica de un Proyecto (Critical Path Method)

El método de la Ruta Crítica conocida también por CPM por sus siglas en inglés (Critical Path Method) es una metodología de la Gestión de Proyectos que nos permite entre otros aspectos estimar la duración de un Proyecto. Para este propósito es necesario conocer las actividades que contempla el proyecto, su duración en una unidad de tiempo y el orden en el cuál deben ser realizadas (por ejemplo, algunas actividades se pueden desarrollar sólo cuando una o varias actividades previas o predecesoras han sido completadas).

Cómo obtener la Ruta Crítica de un Proyecto

El ejemplo a continuación muestra en detalle la aplicación del Método de Ruta Crítica a un proyecto que consta de 9 actividades cuyos tiempos estimados se encuentran en semanas. Adicionalmente en la columna «Predecesor» se establece el orden en el cual se deben realizar las distintas actividades, por ejemplo, la Actividad G se puede realizar una vez completada las Actividades D y F.

tabla-proyecto-ruta-critica

En este contexto resulta de utilidad desarrollar un Diagrama o Representación Gráfica del Proyecto donde cada nodo representa una actividad, el número al interior del paréntesis la duración de dicha actividad, y las flechas un camino o ruta consistente con las relaciones de precedencia.

diagrama-proyecto

Por ejemplo, la Actividad G tiene una duración estimada de 14 semanas y dicha actividad se puede iniciar una vez que hayan concluido sus predecesores, es decir, las Actividades D y F.

Se puede observar adicionalmente que las actividades iniciales son A y B y la actividad final es I.

  1. Una actividad inicial es aquella que se puede comenzar inmediatamente y no existe ninguna otra actividad que le precede.
  2. Una actividad final es una actividad que termina una ruta o camino del proyecto y en consecuencia no es predecesora de ninguna otra actividad del proyecto.

Por tanto la duración del proyecto estará determinado por aquella ruta o camino más largo que comenzando en una actividad inicial concluya en una actividad final. En nuestro ejemplo, un camino que comenzando en A (o en B) termine en I.

Luego, dado el tamaño reducido de este ejemplo es posible enumerar todas las posibilidades rutas o caminos que satisfacen la condición anterior:

  • Ruta: A-C-I: 5[sem]+4[sem]+2[sem]=11[sem]
  • Ruta: A-D-G-I: 5[sem]+3[sem]+14[sem]+2[sem]=24[sem]
  • Ruta: A-E-F-G-I: 5[sem]+1[sem]+4[sem]+14[sem]+2[sem]=26[sem]
  • Ruta: B-H-I: 6[sem]+12[sem]+2[sem]=20[sem]

La Ruta Crítica por tanto es A-E-F-G-I lo que determina que la duración del proyecto es de 26[sem].

Adicionalmente podemos estimar cuándo es lo más pronto que se puede comenzar cada actividad (inicio más cercano o IC – color rojo) y cuándo es lo más pronto que se puede terminar una actividad (término más cercano o TC – color azul).

Por ejemplo, para obtener el inicio más cercano y el término más cercano, en el caso de la Actividad A, éste será la semana 0 y 5, respectivamente. De la misma forma, lo más pronto que puede comenzar la Actividad C será en la semana 5 (tan pronto concluyo su predecesor que es la Actividad A) y lo más pronto que puede terminar es en la semana 9 (dado que la duración de la Actividad C es de 4 semanas) y así se continua el procedimiento desde el inicio hasta el final del proyecto.

ruta-critica-proyecto-cpm

En forma complementaria se puede obtener el tiempo más lejano en el cual se puede terminar una actividad sin atrasar el proyecto (término más lejano o TL – verde) y cuándo es lo más tarde que se puede comenzar una actividad sin retrasar el proyecto (inicio más lejano o IL – naranjo). Para obtener dichos tiempos retrocedemos desde la actividad final (I) hacia las actividades iniciales (A y B).

ruta-critica-proyecto-cpm-f

Por ejemplo, lo más tarde que puede terminar la Actividad H sin retrasar el proyecto es en la semana 24 (si termina más tarde de ello, entonces la Actividad I no se podrá iniciar en la semana 24 y por tanto el proyecto terminará más tarde que la semana 26). Naturalmente dado lo anterior, la Actividad H no podrá comenzar más tarde que la semana 12 si es que se desea terminar el proyecto en 26 semanas.

En este contexto se define el término Holgura (H) o Slack como el tiempo máximo que una actividad se puede retrasar en su inicio sin que esto afecte el tiempo estimado para terminar el proyecto como un todo:

Holgura = IL – IC = TL – TC

El siguiente diagrama muestra la ruta del proyecto con el cálculo de las holguras de cada una de las actividades. Se puede apreciar por ejemplo que la actividad B se puede retrasar un máximo de 6[sem] (su holgura) y aun así estar en condiciones de terminar el proyecto en 26[sem].

Adicionalmente las actividades que pertenecen a la ruta crítica tienen holgura igual a cero, lo que en este ejemplo en particular permite identificar una ruta única: A-E-F-G-I (notar que en general un proyecto puede tener más de una ruta o camino crítico).

ruta-critica-con-holguras

Actualización: De forma de corroborar los resultados anteriores, a continuación se presenta una Carta Gantt del Proyecto obtenido a través del Método de Ruta Crítica (CPM). Con color rojo se destacan aquellas actividades que forman parte de la ruta crítica con holgura igual a cero.

tabla proyecto ruta crítica