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

Cómo reducir la duración de un Proyecto (Crashing) con WINQSB

Un aspecto relevante en todo Proyecto es lograr estimar el tiempo necesario para completar las distintas actividades que lo conforman. En artículos anteriores hemos analizado el Método de Ruta Crítica (CPM) y la Metodología PERT, asumiendo tiempos de actividades deterministas (fijos) y aleatorios (probabilísticos), respectivamente.

En esta oportunidad consideraremos un Proyecto que consta de 7 actividades y que en condiciones de tiempo normal tiene por Ruta Crítica a las actividades A-D-G con una duración total de 12 semanas:

Tabla Crashing

La tabla anterior incluye adicionalmente información sobre el costo normal de desarrollar las actividades en condiciones de tiempo normal y el tiempo crash que consiste el menor tiempo en el que se podría llevar a cabo la actividad en caso que se «apure».

En muchos proyectos existen actividades que podrían demorar menos si se invirtiera más recursos en ellas (costo crash), sin embargo, hay actividades que no son factibles de acortar (por ejemplo, podría ser el tiempo requerido para obtener un permiso por parte de una oficina del gobierno central, asunto que esta fuera del alcance del gerente del proyecto).

Por ejemplo, si quisiéramos reducir el tiempo de la actividad A de 3 a 2 semanas el costo incremental es de $100. Análogamente el costo de reducir el tiempo de la actividad B en 1 semana sería de $250 (se asume proporcionalidad).

El costo actual del proyecto es de $3.700 (suma de los valores de la columna «Costo Normal») para un tiempo estimado de 12 semanas (A-D-G Ruta Crítica).

Si queremos que el proyecto se demore menos de 12 semanas debemos estar dispuestos a asumir un costo monetario mayor. En este contexto el Análisis de Crashing (reducir la duración de un proyecto a un costo eficiente) resulta vital.

El siguiente tutorial muestra cómo reducir la duración de un proyecto utilizando el software WINQSB:

El menor tiempo en el cual se puede desarrollar el proyecto es 9 semanas con un costo total de $4.450. Para ello se reduce el tiempo de las actividades A y B en 1 semana y D en 2 semanas. Las Rutas Críticas ahora son: A-F ; A-D-G; B-G todas con 9 semanas según se muestra en el siguiente informe de WINQSB:

Resultados Crashing

Es importante destacar que NO se puede seguir reduciendo la duración del proyecto aún cuando algunas actividades aún son factibles de apurar. Esto se justifica en general porque al menos una Ruta Crítica no se puede reducir y en dicho caso no tiene sentido destinar más recursos si esto no se verá reflejado en la duración total del proyecto. Por ejemplo, aún podemos reducir la duración de B de 5 a 4 semanas, sin embargo, la duración de la ruta A-D-G no se puede seguir reduciendo.

Importante: Recomendamos revisar el artículo Formulación y Resolución de un Modelo de Programación Lineal para reducir la duración de un Proyecto (Crashing) que detalla cómo a través de un modelo de optimización encontrar aquellas actividades que deben reducir su duración de modo de desarrollar el proyecto en el menor costo posible (dado un tiempo objetivo). En este contexto un artículo complementario es Cómo determinar la Duración Óptima de un Proyecto a través del Análisis de Crashing.

Probabilidad de terminar un Proyecto en un tiempo determinado con PERT

Cuando se utiliza el método PERT (Program Evaluation and Review Technique) uno de los principales objetivos es considerar la incertidumbre en el tiempo de duración de cada una de las actividades de modo de poder estimar la probabilidad de completar el proyecto en un tiempo determinado. Este tipo de análisis resulta de bastante utilidad en aplicaciones prácticas dado que se entiende que en todo Proyecto existen imprevistos o circunstancias que pueden afectar la duración de una actividad y su impacto se puede traspasar al inicio o termino de otras actividades.

Probabilidad de completar un Proyecto en un tiempo determinado utilizando PERT

Para introducir este concepto consideraremos nuevamente nuestro ejemplo de un proyecto que consta de 9 actividades y que contempla las siguientes secuencias y tiempos estimados para cada uno de sus 3 escenarios:

Tiempo esperado PERT

Luego de obtener la duración del proyecto utilizando la Metodología de PERT y el software WINQSB, se determina que el tiempo estimado para completar el proyecto es de 21,5 semanas y las actividades de la ruta crítica son D-F-G. El paso siguiente es determinar la sumatoria de las varianzas de las actividades que pertenecen a la ruta crítica. La varianza se obtiene como:

Varianza Actividades

Donde b es el tiempo pesimista y a es el tiempo optimista. La siguiente tabla muestra el cálculo de la varianza redondeando a 5 decimales (decisión arbitraria para efectos de desarrollar el ejemplo). Se ha marcado con verde las actividades de la ruta crítica para las cuales en la celda H13 se ha calculado la suma de sus varianzas.

Varianza para PERT

Consideremos ahora que para este proyecto nos interesa calcular la probabilidad de poder terminarlo en 23 semanas o menos. Para ello desarrollamos el siguiente procedimiento que nos indica que dicha probabilidad es un 86,86%:

Probabilidad PERT

Esta probabilidad también se puede obtener con la función de Excel: =DISTR.NORM.ESTAND(1,12)

El siguiente tutorial muestra cómo calcular la probabilidad de terminar el proyecto en 23 semanas o menos utilizando WINQSB. Notar que el resultado es levemente diferente sólo por efecto de aproximación:

Cómo obtener la duración de un Proyecto con PERT y WINQSB

A diferencia del Método de Ruta Crítica o CPM la metodología de PERT (Program Evaluation and Review Technique) considera que el tiempo de duración de las actividades que comprenden un proyecto es estocástico.

Este supuesto implica que para cada actividad tendremos distintos escenarios de ocurrencia sobre el tiempo requerido para llevarla a cabo. Estos escenarios se denominan usualmente como Optimista (a) (el menor tiempo posible), Más Probable (m) y Pesimista (b) (el mayor tiempo en el peor de los casos).

Cada uno de estos escenarios descritos se pondera en 1/6, 2/3 y 1/6, respectivamente para obtener el Tiempo Esperado t_{e} de cada actividad: t_{e}=(1/6*a+2/3*m+1/6*b) y luego obtener el tiempo de duración del proyecto (notar que la suma de las probabilidades de ocurrencia de cada escenario es igual a 1 o un 100%).

Duración de un Proyecto con PERT

En la siguiente tabla se muestra cómo calcular el tiempo esperado para cada actividad de un Proyecto, por ejemplo, el tiempo esperado de la actividad A es de 6 semanas ((1/6)*5+(2/3)*6+(1/6)*7) según se aprecia en la fórmula:

Tiempo esperado PERT

Para poder determinar la duración de un proyecto utilizando PERT consideramos los tiempos esperados para cada actividad y seguimos un procedimiento similar al del Método de la Ruta Crítica o CPM. Otra alternativa equivalente es utilizar un software especializado como WINQSB para obtener la duración del proyecto según se muestra en el siguiente tutorial:

El tiempo estimado para completar el proyecto es de 21,5 semanas y la ruta crítica esta determinada por la secuencia D-F-G. Se puede comprobar que si aplicamos el método de la ruta crítica con los tiempos esperados de cada actividad como tiempo determinista, se obtienen los mismos resultados.

PERT en WINQSB