Simulación de proyectos

Consideraciones principales

Si bien es altamente conocida la historia del desarrollo de las dos técnicas de gestión de proyectos, clasicos de la Investigación de Operaciones y sus orígenes en el Desembarco del Dia D y la construccuíon del Submarino Nuclear Polaris, es poco lo que en térnimos de algoritmos se ha avanzado en este terreno.

El algoritmo que utiliza Microsoft Project (CPM) está basado en código escrito en Fortran que fue desarrollado por IBM entre 1959 a 1962. En rigor esta técnica no es en si una simulación. Por el contrario es una técnias en la que el problema del proyecto se modela en forma determinística. Vale decir cada tarea tiene una duracuíón fija.

Resulta dificil de ver pero PERT es en sí misma una técnica que al recurrir a entradas estocáticas (duraciones de tarea que tienen una media y un desvio estandard) no nos otorcan una fecha de finalización fija, sino que nos entregan un promedio y un desvío estandar, al que le podemos aplicar medición de riesgo.

En este caso de estudio analizaremos una biblioteca de R-Cran en la que nos limitaremos a conocer los aspectos relativos a la duración en tiempo del proyecto, prescindiendo de los costos y los recursos a efectos de entender como funciona la parte medular de esta simulación. Existen parámetros complementarios y bibliotecas anexas que realizan este trabajo que omitiremos y que además tienen poderosas herramientas de optimización multi-objetivo.

Técnicas Pert & CPM

Hay dos enfoques en la gestión de proyectos para presentar proyectos multifuncionales en un gráfico:

Notación de actividad en el arco (AoA), donde cada flecha (arista) significa una actividad. Los nodos determinan el inicio o el final de una o más actividades.
Notación de actividad en el nodo (AoN), en la que el nodo denota una actividad. Las flechas representan las relaciones entre la actividad dada y las actividades inmediatamente anteriores e inmediatamente posteriores.

La versión actual del paquete que mostramos utiliza la notación AoA.

El método del Camino Crítico CPM

En el CPM (Critical Path Method) asumimos que la duración de cada actividad es exactamente conocida (determinista). Tomemos la notación AoA. La actividad comienza en el nodo número i y termina en el nodo número j. Todo el proyecto comienza y termina en un nodo par de nodos. Veamos la figura de abajo. Los momentos de Comienzo y Fin difieren porque las actividades pueden ocurrir en paralelo y en serie dentro de un proyecto. Además, las actividades variarán en duración.

Momento de Inicio y Finalización

Nomenclatura

$t_i⁰$ - hora de inicio más temprana posible de la tarea i;

$t_i¹$ - hora de inicio más tardía posible de la tarea i;

$t_j⁰$ - el tiempo de finalización más temprano posible de la tarea j;

$t_j¹$ - última hora posible de finalización de la tarea j.

El momento de completar todo el proyecto se denomina término directivo. El análisis de CPM se puede dividir en las siguientes etapas:

Establecer los tiempos más tempranos para las tareas.
Establecer los últimos tiempos para las tareas.
Determinación de holguras para actividades.
Elaboración del cronograma del proyecto.
Determinación de la ruta crítica del proyecto.

Además, podemos hacer un diagrama de Gantt y gráficos ASAP (lo antes posible) y ALAP (lo más tarde posible).

La preparación de un cronograma del proyecto consiste en determinar todos los tiempos posibles de inicio y finalización de las actividades. Además, calculamos un tiempo flotante total (holgura total) para cada actividad. Durante este tiempo, la actividad se puede retrasar sin retrasar la finalización de todo el proyecto.

Abreviaturas

$ES_{ij}$ = $t_i⁰$ - momento de inicio más temprano posible de la actividad $(i, j)$;

$LF_{ij}$ = $t_i^1$ - último momento de finalización permitido para la actividad $(i, j)$;

$LS_{ij} = LF_{ij} − t_{ij}$ - último momento de inicio permitido para la actividad $(i, j)$;

$EF_{ij} = ES_{ij} + t_{ij}$ - el tiempo de terminación más temprano posible de la actividad $(i, j)$;

$TS_{ij} = LF_{ij} − ES{ij} − t_{ij}$ - holgura total de tiempo (total float) para la actividad $(i, j)$ . Una reserva de tiempo que se puede utilizar para realizar una actividad determinada sin afectar el tiempo de finalización del proyecto. $FS_{ij} = t_j⁰ - t_i⁰ - t{ij}$ - holgura libre de tiempo (free float) para la actividad $(i, j)$ . Cantidad máxima de tiempo por que una actividad se puede retrasar sin retrasar la hora de inicio más temprana posible de cualquier siguiente actividad.

$CS_{ij} = t_j¹- t_i¹-t_{ij} - holgura condicional de tiempo para la actividad $(i, j)$ . Cantidad máxima de tiempo por que una actividad se puede retrasar sin retrasar y sin afectar las holguras de tiempo de las actividades que preceden la actividad (incluida en el mismo camino). Suponemos que el término directivo ($DT$) es igual al tiempo más temprano del evento final ($DT = t_n^0$) entonces, las holguras para actividades críticas igual a cero. Extensión de la duración de cualquier actividad crítica por tiempo $\tau$ unidades pospondrá el tiempo de finalización de todo el proyecto por $\tau$ unidades.

Si asumimos que $DT > t_n^0$ entonces la extensión de la duración de cualquier actividad crítica por $\tau$ unidades de tiempo será posponer el tiempo de finalización de todo el proyecto en $\tau − (DT − t_0^n )$ unidades para $\tau > (DT − t_0^n)$.

Los retrasos más pequeños no afectan la duración de todo el proyecto.

Ejemplo de análisis CPM con biblioteca critpath

Nota:

Debes cargar la biblioteca con el comando correspondoente antes de poder invocara

install.packages("cripath")

Esta biblioteca depende de otras tres, llamadas DiagrameR, rshape2 , y ggplot2

library(critpath)

Esta bibbilioteca tiene varios datasets de prueba (proyectos)

data(package="critpath")

Usemos el proyecto cpmexample1 para ver como es la red

cpmexample1

##   from to label time
## 1    1  2     A    3
## 2    1  3     B    2
## 3    1  4     C    5
## 4    2  4     D    1
## 5    3  4     E    1
## 6    4  5     F    3

Podemos realizar el siguiente análisis del proyecto

grafo de conexiones entre actividades
encontrar momento de inicio y fin de todas las actividades
encontrar los cuellos de botella (actividades críticas)
poner actividades criticas en el grafo
hacer un gráfico de Gantt
hacer los gráficos ASAP y ALAP

Por lo general, sabemos cómo se ve el gráfico antes de resolver el problema de gestión de proyectos, pero supongamos que por el momento no lo hacemos. Con la ayuda de la función plot_graphAOA() crearemos un gráfico basado en los datos de la Tabla 1. La función toma dos argumentos: marco de datos con… bueno, datos y si las duraciones son deterministas. El marco de datos debe tener la misma estructura que en la Tabla 1. El orden de las columnas es importante, no sus nombres. Las dos primeras columnas contienen los números de los nodos inicial y final. El la siguiente columna contiene los nombres de las actividades y la última hora de su duración. todo el paquete Las funciones que usan el marco de datos como argumento deben mantener esta estructura.

Grafo del proyecto

plot_graphAOA(cpmexample1)

## Warning: The `x` argument of `as_tibble.matrix()` must have unique column names if
## `.name_repair` is omitted as of tibble 2.0.0.
## ℹ Using compatibility `.name_repair`.
## ℹ The deprecated feature was likely used in the DiagrammeR package.
##   Please report the issue at
##   <https://github.com/rich-iannone/DiagrammeR/issues>.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

Resolución del grafo

Los siguientes dos elementos de la lista anterior son realizados por la función solve_pathAOA(). Crea el cronograma del proyecto y requiere dos argumentos: marco de datos preparado de acuerdo con el esquema descrito anteriormente y un argumento lógico que indica qué tipo de duración (determinista o estocástica) Estamos tratando con.

x <- solve_pathAOA(cpmexample1, deterministic = TRUE)

## Completion time:  8

## $graphAOA
## DiagrammeR Graph // 5 nodes / 6 edges
##   -- directed / connected / DAG / simple
## 
##   NODES / type: 5 vals - complete / label: 5 vals - complete & unique
##     -- 2 additional node attributes (ES, LF)
##   EDGES / rel: <unused>                                    info: `get_edge_df()`
##     -- 3 additional edge attributes (label, time, TS)
##   SELECTION / <none>
##   CACHE / <none>
##   GLOBAL ATTRS / 17 are set                 info: `get_global_graph_attr_info()`
##   GRAPH ACTIONS / <none>
##   GRAPH LOG / <49 actions> -> () -> () -> set_edge_attrs()
## 
## $schedule
##   Name Time ESij LSij EFij LFij TSij Crit
## 1    A    3    0    1    3    4    1     
## 2    B    2    0    2    2    4    2     
## 3    C    5    0    0    5    5    0    *
## 4    D    1    3    4    4    5    1     
## 5    E    1    2    4    3    5    2     
## 6    F    3    5    5    8    8    0    *
## 
## $ComplTi
## [1] 8
## 
## $CritAct
## [1] "C" "F"
## 
## $AddSlacks
##   Name FST CST
## 1    A   0   1
## 2    B   0   2
## 3    C   0   0
## 4    D   1   0
## 5    E   2   0
## 6    F   0   0

Una vez que se completan los cálculos, se muestra un mensaje con el término de la directiva. el resultado de la La función solve_pathAOA() se guarda en la lista x . Sus elementos individuales varían ligeramente dependiendo del tipo de método utilizado. Para el CPM, estos serán:

Un gráfico guardado creado con un paquete DiagrammeR.
El cronograma del proyecto.
Tiempo de finalización del proyecto.
Lista de actividades críticas.
Una tabla con valores flotantes libres y flotantes condicionales.

Los operadores “[ devuelven los objetos tipo lista. En cambio el operador “[[” permite el acceso a un ítem específico.

Listado de tareas críticas

Scehduling

x[2]

## $schedule
##   Name Time ESij LSij EFij LFij TSij Crit
## 1    A    3    0    1    3    4    1     
## 2    B    2    0    2    2    4    2     
## 3    C    5    0    0    5    5    0    *
## 4    D    1    3    4    4    5    1     
## 5    E    1    2    4    3    5    2     
## 6    F    3    5    5    8    8    0    *

Término directivo

x[3]

## $ComplTi
## [1] 8

Actividades críticas

x[4]

## $CritAct
## [1] "C" "F"

Tiempo libre flotante y valor flotante

x[5]

## $AddSlacks
##   Name FST CST
## 1    A   0   1
## 2    B   0   2
## 3    C   0   0
## 4    D   1   0
## 5    E   2   0
## 6    F   0   0

El primer elemento de la lista $x$ es utilizado por otras funciones del paquete. Los Asteriscos en la última columna de el cronograma indica qué actividades son críticas. Ahora, dibujemos un gráfico con las actividades críticas marcadas. Usaremos la función plot_graphAOA() otra vez pero con otro argumento. Será una lista creada después de resolver el problema. Esto requiere la uso del argumento pasado sea “solved”*.

plot_graphAOA(solved = x)

## Warning: The `x` argument of `as_tibble.matrix()` must have unique column names if
## `.name_repair` is omitted as of tibble 2.0.0.
## ℹ Using compatibility `.name_repair`.
## ℹ The deprecated feature was likely used in the DiagrammeR package.
##   Please report the issue at
##   <https://github.com/rich-iannone/DiagrammeR/issues>.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

Gráfica de Gantt

El siguiente elemento del análisis de CPM será el diagrama de Gantt. La función plot_gantt() requiere la Los paquetes ggplot2 y reshape2 se instalarán primero. También toma la lista elaborada por el solve_pathAOA() como argumento obligatorio. El argumento opcional bar_size determina el espesor de la barra de la actividad dibujada. El valor predeterminado es 10 y, si corresponde, este argumento debe no ser proporcionado.

plot_gantt(x)

Gráfica ASAP

Las actividades se muestran en el orden en que fueron ingresadas. Los críticos están marcados con CR y los no críticos con NC. Además, se han agregado holguras mayores que cero para no críticos actividades. Según el gráfico de Gantt, podemos trazar dos gráficos más. El primero es el gráfico ASAP que muestra efectos de iniciar la actividad lo antes posible y terminarla lo antes posible. Se puede lograr con la función plot_asap().

plot_asap(x)

Gráfica ALAP

Por otro lado, la gráfica ALAP muestra los efectos de iniciar la actividad lo más tarde posible y terminarla lo más tarde posible QUE sea posible. Se puede lograr con la función plot_alap().

plot_alap(x)

El método PERT

La abreviatura PERT significa Técnica de Evaluación y Revisión de Programas. Este método se basa en los siguientes supuestos:

Se supone que las duraciones de las actividades tienen distribución Beta con valores esperados $E(t_{ij} )$ y desviaciones estándar $D(t_{ij} )$ .

Las siguientes restricciones se aplican a la distribución de la duración de la actividad, es decir, sobre la densidad función $\mathscr{F}(t_{ij} )$ :

La duración de la actividad está dentro del rango $\langle t_{ij}â , t_{ij}^b \rangle$.Suponemos que la probabilidad de la realización de la actividad $(a)$ en tiempos menores que t_{ij}â o mayores de t_{ij}b unidades es cero;
Los parámetros de la función Beta aseguran que la distribución de probabilidad de la la duración de la actividad es asimétrica a la derecha.

Los expertos estiman la duración de las actividades individuales. Como resultado, obtenemos:

$t_{ij}â$ duración optimista de la actividad $(a)$;
$t_{ij}^b$ duración pesimista de la actividad $(a)$;
$t_{ij}^m$ la duración más probable de la actividad (a).

El análisis de tiempo PERT comienza con la fase introductoria, que consiste en estimar el tiempo esperado Variación de valor y duración para cada actividad.

Duración prevista de la actividad (a):

\[ m_{ij}= \frac{t_{ij}â + 4*t_{ij}^m + t_{ij}^b }{6} \]

Varianza de la duración de la actividad (a)

\[ S_{ij}² = \left( \frac{t_{ij}^b - t_{ij}^a }{6} \right) \]

Los cálculos en el problema estocástico son análogos al determinista (CPM) excepto que ahora use las duraciones esperadas en lugar de las duraciones fijas. El enfoque PERT clásico utiliza el teorema del límite central. Este teorema establece que la suma (diferencia) de un gran número de variables aleatorias independientes con la misma distribución tiene un distribución asintóticamente normal. La probabilidad de cumplir con el término de directiva esperado () igual a la fecha más temprana en que ocurrió el última actividad $(t_n⁰ )$ es 50%. En el método PERT, se supone que debe seleccionarse de tal manera que su probabilidad sea estar entre 30% y 60%:

\[ 0.3 \le P(t_n < DT) \le 0.6 \]

Un cronograma con menos del 30% de posibilidades de realización se denomina cronograma del tomador de riesgos, y el que con más del 60 % de probabilidad se llama cronograma conservador .

Ejemplo de análisis con la biblioteca critpath

Usaremos un dato diferente que en CPM. Estos datos están disponibles en un conjunto denominado pertexample1 que vimos antes. Nos deja que supongamos que la duración de las actividades es aleatoria y se describe con tres valores numéricos como en Tabla 2.

y <- pertexample1
y

##   from to label opt_time likely_time pes_time
## 1    1  2     A        3           5        7
## 2    2  3     B        5           7        9
## 3    3  4     C        5           5        8
## 4    3  5     D        1           6        8
## 5    3  6     E        6           8       10
## 6    4  7     F        2           6        7
## 7    5  7     G        5           6        7
## 8    6  7     H        3           5        7
## 9    7  8     I        4           6        8

Estamos interesados en los siguientes tipos de análisis:

determinar las horas de inicio y finalización de cada actividad,
identificar los cuellos de botella del proyecto (actividades críticas),
colocando actividades críticas en el gráfico,
hacer un diagrama de Gantt,
elaboración de gráficos ASAP y ALAP,
indicación de los términos de las directivas para los horarios del tomador de riesgos y del conservador.

La duración es una variable aleatoria, por lo que cambiaremos el argumento determinista a FALSO.

y <- solve_pathAOA(pertexample1, deterministic = FALSE)

## Expected compl. time distribution: N( 31 , 1.490712 )

El resultado nos indica 31 días +/- 1.5 dias

Después de resolver el problema, aparece un mensaje que da los parámetros de la distribución normal de un variable aleatoria que describe la duración del proyecto. A continuación mostramos los elementos de la lista que almacenan la solución. Contiene un elemento más que el lista creada para el método CPM. La columna Tiempo contiene la duración esperada de la actividad.

Scheduling 2

y[2]

## $schedule
##   Name Time       Var ESij LSij EFij LFij TSij Crit
## 1    A  5.0 0.4444444  0.0  0.0  5.0  5.0  0.0    *
## 2    B  7.0 0.4444444  5.0  5.0 12.0 12.0  0.0    *
## 3    C  5.5 0.2500000 12.0 14.0 17.5 19.5  2.0     
## 4    D  5.5 1.3611111 12.0 13.5 17.5 19.0  1.5     
## 5    E  8.0 0.4444444 12.0 12.0 20.0 20.0  0.0    *
## 6    F  5.5 0.6944444 17.5 19.5 23.0 25.0  2.0     
## 7    G  6.0 0.1111111 17.5 19.0 23.5 25.0  1.5     
## 8    H  5.0 0.4444444 20.0 20.0 25.0 25.0  0.0    *
## 9    I  6.0 0.4444444 25.0 25.0 31.0 31.0  0.0    *

Términación directiva esperada.

y[3]

## $ComplTi
## [1] 31

Devios estandard de la finalización

y[4]

## $SDevTi
## [1] 1.490712

Actividades críticas

y[5]

## $CritAct
## [1] "A" "B" "E" "H" "I"

tiempo flotante condicional y valores flotantes

y[6]

## $AddSlacks
##   Name FST CST
## 1    A 0.0 0.0
## 2    B 0.0 0.0
## 3    C 0.0 2.0
## 4    D 0.0 1.5
## 5    E 0.0 0.0
## 6    F 2.0 0.0
## 7    G 1.5 0.0
## 8    H 0.0 0.0
## 9    I 0.0 0.0

Gráficos ASAP y ALAP

plot_graphAOA(solved = y)

## Warning: The `x` argument of `as_tibble.matrix()` must have unique column names if
## `.name_repair` is omitted as of tibble 2.0.0.
## ℹ Using compatibility `.name_repair`.
## ℹ The deprecated feature was likely used in the DiagrammeR package.
##   Please report the issue at
##   <https://github.com/rich-iannone/DiagrammeR/issues>.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

Gant

plot_gantt(y)

Gantt ASAP

plot_asap(y)

Gantt ALAP

plot_alap(y)

Para fijar plazos correspondientes a los horarios del arriesgado y del asegurador, utilizaremos el Función PERT_newtime().

PERT_newtime(new_prob = 0.3, y)

## New expected compl. time:  30.21827

## $probDT
## [1] 0.3
## 
## $newDT
## [1] 30.21827

PERT_newtime(new_prob = 0.6, y)

## New expected compl. time:  31.37767

## $probDT
## [1] 0.6
## 
## $newDT
## [1] 31.37767

La función PERT_newprob() responde a la pregunta sobre la probabilidad de completar el proyecto para un término directivo dado. Por ejemplo, la probabilidad de que el proyecto termine después de 30 días

PERT_newprob(new_DT = 30, y)

## Prob. of completion:  0.2511675

## $newDT
## [1] 30
## 
## $prob_compl
## [1] 0.2511675

Además, la función plot_norm() dibuja un gráfico de la distribución normal de una variable aleatoria describiendo el tiempo de término directivo esperado.

plot_norm(y)

Las líneas verticales adicionales indican los horarios del tomador de riesgos y el conservador.

##Notas adicionales finales

La versión actual del paquete (0.1.1) admite problemas con actividades en arcos.
Los gráficos son dibujados por la función render_graph() del paquete DiagrammeR usando el Algoritmo de Fruchterman-Reingold. Es garantizar, entre otros, que no se crucen los bordes.

Pero esto no siempre es posible. Además, ejecuciones posteriores de esta función para el mismo problema puede producir (y a menudo lo hace) un gráfico que se coloca en el plano de una manera ligeramente diferente cada uno tiempo.

El primer objeto de la lista pertenece a la clase dgr_graph compatible con DiagrammeR paquete. Es posible realizar las operaciones descritas en el manual de este paquete.