Lección 03 — El grafo Roy (método de los potenciales)

Actividades en los nodos, cálculo hacia delante y hacia atrás, esperas y solapes

Qué se aprende

A representar el proyecto con el grafo Roy (actividades en los nodos, prelaciones en los arcos), a calcular sobre él las fechas más tempranas y más tardías actividad a actividad, a compararlo con el PERT y a modelar relaciones que no son «fin-comienzo» (esperas y solapes).

Conceptos

Representación AoN (activity on node). Cada actividad es un nodo, rectangular, en el que se anotan sus fechas; cada prelación inmediata \(P \to A\) es un arco. Se añaden dos nodos auxiliares, inicio y fin, de duración cero, conectados a las actividades iniciales y finales. No hay ficticias: una prelación es un arco y nada más.

Equivalencia con el PERT. Los dos grafos describen el mismo orden parcial y dan el mismo calendario. El PERT tiene menos nodos y necesita ficticias; el Roy tiene tantos nodos como actividades y ningún arco artificial. En el Roy las fechas se escriben en la actividad; en el PERT, en los sucesos.

Fechas de una actividad. Con \(d_A\) la duración:

• Inicio más temprano: \(ES_A = \max_{P \in \text{pred}(A)} EF_P\) (0 si es inicial).
• Fin más temprano: \(EF_A = ES_A + d_A\).
• Duración del proyecto: \(T = \max_{A \text{ final}} EF_A\).
• Fin más tardío: \(LF_A = \min_{S \in \text{suc}(A)} LS_S\) (\(T\) si es final).
• Inicio más tardío: \(LS_A = LF_A - d_A\).
• Holgura total: \(H_A = LS_A - ES_A\) (lección 05).

Esperas y solapes. El Roy admite arcos con valor: un arco \(P \to A\) de valor \(\ell\) significa \(ES_A \ge ES_P + \ell\). Con \(\ell = d_P\) es la prelación ordinaria; con \(\ell > d_P\) hay una espera (secado, curado) y con \(\ell < d_P\) un solape (A puede empezar cuando P lleva \(\ell\) unidades). De ahí el nombre «método de los potenciales»: las fechas son los potenciales que satisfacen todas las desigualdades de los arcos. Con prelaciones ordinarias, una espera se modela también añadiendo una actividad «espera» de duración \(\ell - d_P\) entre P y A, y un solape dividiendo P en dos tramos.

Algoritmo

Paso hacia delante (en orden topológico): \(ES\) de las iniciales es 0; para cada actividad, \(ES = \max\) de los \(EF\) de sus predecesoras y \(EF = ES + d\). Al terminar, \(T\) es el mayor \(EF\).

Paso hacia atrás (orden topológico inverso): \(LF\) de las finales es \(T\); para cada actividad, \(LF = \min\) de los \(LS\) de sus sucesoras y \(LS = LF - d\).

El orden topológico es imprescindible: no se puede calcular \(ES_A\) hasta tener el \(EF\) de todas sus predecesoras.

Ejemplo guía

Act.	d	pred.	ES = máx EF pred.	EF	suc.	LF = mín LS suc.	LS	H
A	3	—	0	3	C, D	mín(3, 6) = 3	0	0
B	2	—	0	2	D, E	mín(6, 6) = 6	4	4
C	4	A	3	7	F	7	3	0
D	1	A, B	máx(3, 2) = 3	4	F	7	6	3
E	2	B	2	4	G	8	6	4
F	3	C, D	máx(7, 4) = 7	10	—	10	7	0
G	2	E	4	6	—	10	8	4

\(T = 10\); críticas (holgura 0): A, C, F. Son exactamente los mismos números que da el PERT con los tiempos de los nodos (lección 04): \(ES_A\) es el tiempo temprano del nodo del que sale A y \(LF_A\) el tiempo tardío del nodo al que llega.

Grafo Roy del proyecto guía: en cada nodo, inicio más temprano, duración e inicio más tardío; en rojo el camino crítico

Predecesora dominante. En D, la predecesora que fija su inicio es A (\(EF_A = 3 > EF_B = 2\)): un retraso de B de hasta 1 unidad no mueve a D. Saber qué predecesora domina en cada máximo es lo que permite predecir, sin recalcular, qué retrasos importan.

Con pmULE

proyecto.roy(durations=datos['duration'])   # dibujo con fechas y camino crítico
proyecto.calendar(datos['duration'])        # ES, EF, LS, LF y las tres holguras
proyecto.pert(durations=datos['duration'])  # el PERT equivalente, con los mismos tiempos

Preguntas de comprobación

• ¿Puede una actividad tener \(LS < ES\)? Sólo si se impone un plazo menor que \(T\) (holguras negativas, lección 04).
• Si B se retrasa 1 unidad, ¿cambia algo? D sigue empezando en 3 (A domina) y E empieza en 3 en vez de 2, pero tiene holgura 4: nada cambia en el plazo.
• ¿Cómo se ve en el Roy una espera de 2 unidades entre C y F? Un arco C → F de valor \(d_C + 2 = 6\), o una actividad «espera» de duración 2 entre ambas.

Qué practica cada variante

roy-vs-pert: dibujar los dos grafos, contar nodos y arcos, calendario y camino crítico. esperas-y-solapes: modelar una espera y un solape con actividades auxiliares y ver su efecto. predecesora-dominante: calcular a mano hacia delante y atrás anotando qué predecesora fija cada máximo, y predecir el efecto de retrasos. desde-sucesoras: el cuadro viene como sucesoras; invertirlo y dibujar.