Reduccion 14

9 actividades; CUR por tramos, reducir 3 semanas

Enunciado

Considere el proyecto cuyo cuadro de prelaciones y duraciones normal y tope (semanas) se adjunta. Las actividades reducibles pueden acortarse hasta dos semanas, pero el coste no es lineal: la primera semana cuesta ucr_1 k€ y la segunda ucr_2 k€ (más cara: horas extra, turno de noche…). Las actividades con CUR infinito no pueden acelerarse.

  1. Calcule la duración normal del proyecto y sus rutas críticas.
  1. Reduzca el proyecto 3 semanas con mínimo coste aplicando Ackoff-Sasieni paso a paso con el coste marginal: el de la semana que toca acortar a cada actividad. Muestre en cada paso las rutas críticas, las opciones y su coste.
  1. ¿Qué habría resultado de aplicar el algoritmo con un CUR único por actividad igual a la media \((ucr_1 + ucr_2)/2\)? Compare el coste real de esa solución con el del apartado anterior.
  1. ¿Por qué con costes crecientes por tramos el procedimiento semana a semana sigue siendo válido, y qué fallaría si la segunda semana fuera más barata que la primera?
Tabla 1: Cuadro de datos del enunciado
predecessor duration cap_duration ucr_1 ucr_2
activity
A --- 6 4 4.0 7.0
B --- 8 8 inf inf
C A,B 4 4 inf inf
D C 6 4 1.0 5.0
E A 5 3 7.0 11.0
F D 5 5 inf inf
G D 5 3 5.0 11.0
H G 3 3 inf inf
I E,F,H 8 6 1.0 5.0

El proyecto corresponde a la organización de un congreso científico; las actividades son las siguientes (las duraciones del cuadro están en semanas).

Tabla 2: Descripción de las actividades
Descripción
A Definición del programa y fechas
B Reserva de la sede
C Convocatoria de comunicaciones
D Página web e inscripciones
E Contratación de ponentes invitados
F Revisión de los trabajos recibidos
G Elaboración del programa definitivo
H Contratación de catering y viajes
I Edición del libro de actas

Resolución

Apartado 1

  1. Calcule la duración normal del proyecto y sus rutas críticas.

Cálculo de los tiempos mínimos y máximos de los nodos del grafo Roy 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 24
Figura 1: Grafo Roy con las duraciones normales 
Route_5: B - C - D - G - H - I

Duración normal: 34 semanas.

Tabla 3: Duración de cada ruta con las duraciones normales
actividades duración = suma duración
Route_1 A - C - D - F - I A(6) + C(4) + D(6) + F(5) + I(8) = 29 29.0
Route_2 A - C - D - G - H - I A(6) + C(4) + D(6) + G(5) + H(3) + I(8) = 32 32.0
Route_3 A - E - I A(6) + E(5) + I(8) = 19 19.0
Route_4 B - C - D - F - I B(8) + C(4) + D(6) + F(5) + I(8) = 31 31.0
Route_5 B - C - D - G - H - I B(8) + C(4) + D(6) + G(5) + H(3) + I(8) = 34 34.0

Apartado 2

  1. Reduzca el proyecto 3 semanas con mínimo coste aplicando Ackoff-Sasieni paso a paso con el coste marginal: el de la semana que toca acortar a cada actividad. Muestre en cada paso las rutas críticas, las opciones y su coste.

En cada paso el coste marginal de una actividad es ucr_1 si aún no se ha acortado y ucr_2 si ya se acortó una semana (infinito si no le queda margen). Las opciones son las actividades comunes a todas las rutas críticas y las parejas que cubren todas ellas; se elige la de menor coste marginal.

duración rutas críticas opciones (coste marginal) elegida coste
paso
1 34 Route_5 I (1); D (1); D+I (2); G (5); D+G (6); G+I (6) I 1.0
2 33 Route_5 D (1); I (5); G (5); D+G (6); D+I (6); G+I (10) D 1.0
3 32 Route_5 I (5); D (5); G (5); D+G (10); D+I (10); G+I (10) I 5.0

Se acortan D (1), I (2); duración 31 semanas; sobrecoste 7 k€.

Apartado 3

  1. ¿Qué habría resultado de aplicar el algoritmo con un CUR único por actividad igual a la media \((ucr_1 + ucr_2)/2\)? Compare el coste real de esa solución con el del apartado anterior.
con coste marginal con CUR medio
actividades acortadas D (1), I (2) D (2), I (1)
coste real (k€) 7.0 7.0

Con el CUR medio el algoritmo puede preferir acortar dos semanas una actividad que parece barata «de media» cuando en realidad su segunda semana es cara, o evitar una cuya primera semana era la más barata de todas. El coste real se obtiene valorando cada semana con su tramo.

Apartado 4

  1. ¿Por qué con costes crecientes por tramos el procedimiento semana a semana sigue siendo válido, y qué fallaría si la segunda semana fuera más barata que la primera?

Con costes marginales crecientes la función de coste de cada actividad es convexa, y en ese caso acortar semana a semana eligiendo siempre la opción marginal más barata es óptimo (es la misma razón por la que el CUR constante funciona). Si la segunda semana fuera más barata que la primera (coste cóncavo: un coste fijo de movilización y luego barato), el paso a paso fallaría: la primera semana parecería cara y nunca se emprendería, aunque acortar dos de golpe fuera lo mejor; habría que evaluar las dos semanas juntas.