CPM y PERT
Los modelos de redes se pueden usar para ayudar
a la planificación de proyectos complejos los que
involucran muchas actividades. Si la
duración de cada actividad se conoce con certeza, se puede usar
el método del camino crítico
(CPM) para determinar el tiempo requerido para realizar el proyecto. CPM
se
puede usar también para determinar en
cuánto se puede atrasar una actividad sin que esto retrase el
término del proyecto. CPM fue desarrollado
en los años ´50 por du Pont y Sperry Rand.
Si la duración de las actividades no
se conoce con certeza, se puede usar la técnica PERT (Program
Evaluation
and Review Technique) para estimar la
probabilidad que el proyecto se termine en una fecha determinada.
CPM y PERT han sido exitosamente utilizado
en muchas aplicaciones como:
-
Planificación de proyectos de construcción
como carreteras, edificios, piscinas.
-
Planificación del traslado de un hospital
que atiende 400 pacientes hospitalizados desde Portland a Oregon
-
Desarrollo de la planificación aérea
en diferentes aerolíneas norteamericanas
-
Instalación de un nuevo sistema computacional
-
Diseño y marketing de nuevos productos
-
Construcción de barcos
Para aplicar PERT y CPM se requiere de un conjunto
de actividades que se deben realizar para completar el proyecto.
El proyecto se considera terminado una vez
que todas las actividades hayan finalizado. Para cada actividad hay un
conjunto de actividades denominadas predecesoras
que deben haber finalizado antes que la actividad pueda comenzar.
Una red de proyecto se usa para representar
la relación de precedencia entre actividades. Las actividades serán
representadas por arcos y los nodos representarán
el término de un conjunto de actividades (por esta razón
los
nodos se llamarán eventos). Este tipo
de red de proyecto se llama una red AOA (actividad dobre arcos).
Dada una lista de actividades y predecesores
una AOA llamada también red del proyecto se puede construir
siguiendo las siguientes reglas:
-
Nodo 1 representa el inicio del proyecto. Un nodo
comenzando en el nodo 1 simbolizará una actividad que no tiene predecesores.
-
Un nodo (llamado nodo final) representará
el término del proyecto, el cuál debe ser incluído
en el diagrama de red.
-
Numerar los nodos en la red tal que el nodo
representando el término de una actividad siempre tenga un valor
mayor que el nodo representando el comienzo de la actividad (hay muchas
posibles enumeraciones que respetan esta regla)
-
Una actividad sólo puede estar representada
una vez en la red.
-
Dos nodos pueden estar conectados por a lo más
un arco.
Para impedir violar las reglas 4 y 5, algunas veces
será necesario utilizar actividades artificiales (dummy).
Ejemplos:
1. Widgetco desea introducir un nuevo producto
al mercado (producto 3). Una unidad del producto 3 se produce ensamblando
una unidad del producto 1 con una unidad del producto 2. Antes que la producción
comience ya sea esta del producto 1 ó 2, se debe comprar materia
prima y se debe capacitar a los trabjadores. Antes que los productos 1
y 2 sean ensamblados para formar el producto 3, se debe inspeccionar el
producto 2. Analizando la siguiente lista de actividades y sus predecesores
construya la malla o diagrama del proyecto:
Actividad
|
Predecesores
|
duración (días)
|
A = capacitación
|
-
|
6
|
B = compra materia prima
|
-
|
9
|
C = producir producto 1
|
A, B
|
8
|
D = producir producto 2
|
A, B
|
7
|
E = test producto 2
|
D
|
10
|
F = ensamble producto 1+2
|
C, E
|
12
|
Los conceptos más importantes en CPM
para cada evento son:
-
El tiempo del evento más temprano para el
nodo i (ET(i)) es el instante de tiempo más temprano en el cuál
el evento correspondiente al nodo i puede ocurrir
-
El tiempo del evento más tarde para el nodo
i (LT(i)) es el instante de tiempo más tarde en el cuál el
evento correspondiente al nodo i puede ocurrir sin retrasar el término
del proyecto.
Calculando los tiempos más tempranos:
-
Encontar cada evento anterior al nodo i que esté
conectado por un arco al nodo i. Estos eventos se denominan predecesores
inmediatos del nodo i.
-
Para cada predecesor inmediato del nodo i agregue
la duración de la actividad conectando el predecesor inmediato del
nodo i.
-
ET(i) es igual al máximo de las sumas calculando
en el punto anterior.
Calculando los tiempos más tarde:
-
Encontrar cada nodo que está después
del nodo i y está conectado al nodo i por un arco. Estos eventos
son los sucesores inmediatos del nodo i.
-
Desde el LT para cada inmediato sucesor para el
nodo i reduzca la duración de la actividad uniendo el sucesor del
nodo i.
-
LT(i) es el más pequeño de las diferencias
determinadas por el paso anterior.
Camino Crítico:
-
Cualquier actividad con [LT(i) - ET(i)] = 0 será
actividad crítica.
-
Una trayectoria desde nodo i al nodo final que
involucra todas las actividades críticas se llama camino crítico.
En muchas situaciones el administrador del proyecto
debe terminar el proyecto en una fecha
que es menor que el largo del camino crítico.
Por ejemplo, suponga que Widgetco piensa que para tener exito en su inclusión
del producto 3 al mercado éste debe estar disponible a la venta
antes que la competencia. Widgetco sabe que el producto de su competidor
está planificado para salir a la venta dentro de 26 días
(a contar de hoy), por lo cual Widgetco debe introducir al mercado su producto
dentro de 25 días. Recordemos que el camino crítico calculado
era de 38 días. Widgetco tendrá que gastar recursos adicionales
para modificar la fecha de término del proyecto. En tal situación
un modelo de programación lineal es una buena alternativa para determinar
la distribución de los recursos por actividad que minimice los costos
adicionales incurridos.
Suponga que se desea agregar recursos adicionales
a una actividad dada. Widgetco puede reducir la duración de cualquier
actividad hasta a lo más 5 días. Los costos por día
para reducir la duración de una actividad son:
A
|
B
|
C
|
D
|
E
|
F
|
10
|
20
|
3
|
30
|
40
|
50
|
Plantearlo por Programación Lineal.
PERT: Program Evaluation
and Review Technique
CPM supone que la duración de cada actividad
es conocida con certeza. Para muchos proyectos, esto es evidentemente no
aplicable. El objetivo de PERT es corregir una mala estimación realizada
con un CPM "puro", modelando la duración de cada actividad como
una variable aleatoria. Para cada actividad PERT requiere que el administrador
de proyecto estime las siguientes cantidades:
-
a = duración de la actividad
bajo las condiciones más favorables
-
b = duración de la actividad
bajo las condiciones más desfavorables
-
m = el valor más probable
de la duración de la actividad.
PERT asume que Tij la variable aleatoria
de la duración de la actividad que va desde el nodo i al nodo j
sigue una distribución Beta. Si Tij es una distribución Beta
entonces se sabe que su esperanza es:
E(Tij) = (a + 4m + b) / 6 y
que su varianza es
V(Tij) = (1/36)*(b-a)2
PERT requiere además de la suposición
que las duraciones de todas las variables son independientes. Luego para
cualquier trayectoria en la red la media y la varianza de los tiempos requeridos
para terminar las actividades sobre la trayectoria estará dada por
la suma de las esperanzas sobre la trayectoria, al igual que la suma de
las varianzas.
PERT supone que el camino crítico encontrado
por CPM contiene sufientes actividades que nos permiten usar el Teorema
del límite central y concluye entonces que:
CP = Suma de los Tij sobre la trayectoria
crítica
y CP se distribuye normal
Aplicando la suposición que CP se distribuye
normal se pueden responder preguntas como:
¿Cuál es la probabilidad que
el proyecto será terminado dentro de 35 días?
Dificultades de PERT
-
La suposición que las duraciones de las
actividades son independientes es dificil de justificar
-
Las duraciones de las actividades pueden no seguir
una distribución beta
-
La suposición que el camino crítico
encontrado por CPM será siempre el camino crítico para el
proyecto puede no estar justificada.
Una alternativa para el método PERT es usar
la simulación de Monte Carlo para determinar la esperanza y la varianza
de la trayectoria crítica y la probabilidad que una actividad dada
es una actividad relamente crítica.
Ejemplo: Para Widgetco suponga la siguiente
tabla de estimación de los tiempos
Actividad
|
a
|
b
|
m
|
(1,2)
|
5
|
13
|
9
|
(1,3)
|
2
|
10
|
6
|
(3,5)
|
3
|
13
|
8
|
(3,4)
|
1
|
13
|
7
|
(4,5)
|
8
|
12
|
10
|
(5,6)
|
9
|
15
|
12
|