Formula 05

instancia pat1 de Patterson (14 actividades)

Enunciado

El fichero pat1.rcp del conjunto de instancias de Patterson (formato RCP: primera línea, número de actividades y de recursos; segunda, disponibilidad de cada recurso; después, una línea por actividad con su duración, sus necesidades de recursos, el número de sucesoras y sus sucesoras) describe un proyecto con actividades ficticias de inicio y fin de duración cero:

Tabla 1: Contenido del fichero 
14      3
2       1       2
0       0       0       0       3       2       3       4
6       1       0       0       2       9       10
4       0       0       0       3       5       6       7
3       0       0       0       2       8       11
1       0       0       0       1       10
6       1       0       1       1       12
2       1       0       0       2       8       11
1       0       0       0       1       13
4       0       1       1       1       14
3       0       0       1       1       12
2       0       0       1       1       12
3       0       1       0       1       13
5       0       0       0       1       14
0       0       0       0       0
  1. Lea el fichero con read_rcp (escribiéndolo antes en disco), construya el cuadro de prelaciones y el proyecto. ¿Cuántas actividades reales, ficticias, nodos y rutas tiene?
  1. Calcule τ = ‖R·t‖∞ y compárelo con la duración obtenida por el cálculo de tiempos (CPM). Indique las actividades críticas.
  1. Calcule la SVD de R y el cociente σ₁/σ₂. Ordene las actividades por |v₁| y mida la precisión del ranking: fracción de las k primeras (k = número de críticas) que son críticas.
  1. Compare el tamaño de R con el del grafo. ¿Cómo crece el número de rutas con el tamaño del proyecto y qué implica para proyectos de cientos de actividades?

Resolución

Apartado 1

  1. Lea el fichero con read_rcp (escribiéndolo antes en disco), construya el cuadro de prelaciones y el proyecto. ¿Cuántas actividades reales, ficticias, nodos y rutas tiene?
activity A01 A02 A03 A04 A05 A06 A07 A08 A09 A10 A11 A12 A13 A14
predecessor --- A01 A01 A01 A03 A03 A03 A04,A07 A02 A02,A05 A04,A07 A06,A10,A11 A08,A12 A09,A13
duration 0 6 4 3 1 6 2 1 4 3 2 3 5 0

14 actividades (incluidas las dos ficticias del formato, de duración 0), 1 ficticias añadidas por el grafo, 10 nodos y 8 rutas.

Cálculo de los tiempos tempranos y tardíos de los sucesos y de las holguras totales paso a paso. El primer paso muestra el grafo resuelto; a partir del siguiente se calcula desde el principio (avance con los botones):

paso 0 de 37
Figura 1: Grafo PERT de la instancia

Apartado 2

  1. Calcule τ = ‖R·t‖∞ y compárelo con la duración obtenida por el cálculo de tiempos (CPM). Indique las actividades críticas.

τ = ‖R·t‖∞ = 18; CPM = 18; coinciden: True. Actividades críticas: A01, A03, A06, A12, A13, A14.

Apartado 3

  1. Calcule la SVD de R y el cociente σ₁/σ₂. Ordene las actividades por |v₁| y mida la precisión del ranking: fracción de las k primeras (k = número de críticas) que son críticas.
A14 A01 A13 A12 A03 A11 A07 A10 A04 A08 A02 A05 A06 A09
v₁ 0.495 0.495 0.459 0.343 0.277 0.139 0.137 0.136 0.118 0.116 0.1 0.072 0.068 0.036
crítica True True True True True False False False False False False False True False

σ₁/σ₂ = 2.78. La mejor clasificada, A14, es crítica; precisión en las 6 primeras: 0.83.

En el conjunto de Patterson (110 instancias) la actividad mejor clasificada por \(v_1\) es crítica en el 77 % de los casos, y la identificación falla sobre todo cuando σ₁/σ₂ está cerca de 1 (dos direcciones dominantes). El ranking es informativo, no determinista.

Apartado 4

  1. Compare el tamaño de R con el del grafo. ¿Cómo crece el número de rutas con el tamaño del proyecto y qué implica para proyectos de cientos de actividades?

El grafo tiene 10 nodos y 15 arcos, pero R tiene 8 filas: el número de rutas crece de forma combinatoria con la anchura del grafo (en las instancias de 51 actividades de Patterson hay hasta varios miles). Por eso la fórmula es útil como herramienta analítica (sensibilidad, estructura, simulación vectorizada), mientras que para calcular τ en proyectos grandes basta el cálculo de tiempos hacia delante, que es lineal en el número de arcos.