Recursos 06

9 actividades; 4 operarios; tres reglas de prioridad frente a Wiest-Levy

Enunciado

Considere el proyecto cuyo cuadro de prelaciones, duraciones (semanas) y operarios necesarios se adjunta. Sólo se dispone de 4 operarios y las actividades no pueden interrumpirse una vez empezadas.

  1. Calcule el calendario sin restricción de recursos y dibuje las cargas con los inicios más tempranos. ¿En qué semanas se superan los 4 operarios?
  1. Programe el proyecto periodo a periodo con un planificador en paralelo: en cada semana se ordenan las actividades disponibles según una regla de prioridad y se van admitiendo mientras quepan en el límite. Aplique tres reglas: (a) menor holgura total, (b) menor duración (SPT) y (c) mayor número de operarios. Dé la duración con cada una.
  1. Compare con el resultado del algoritmo de Wiest-Levy de la librería (asignar).
  1. ¿Alguna regla garantiza la duración mínima? ¿Qué información usa la regla de la holgura que no usan las otras?
Tabla 1: Cuadro de datos del enunciado
predecessor duration resources
activity
A --- 4 1
B --- 2 4
C B 2 3
D A,C 5 2
E A,C 4 3
F D 4 2
G D 2 1
H D,E 2 3
I F,G,H 3 1

Resolución

Apartado 1

  1. Calcule el calendario sin restricción de recursos y dibuje las cargas con los inicios más tempranos. ¿En qué semanas se superan los 4 operarios?

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 29
Figura 1: Grafo PERT con tiempos y camino crítico
Tabla 2: Calendario sin restricción de recursos
Haz clic en un número de la tabla para ver cómo se calcula.
👆 Interactivo: haz clic en cualquier celda de la tabla para ver cómo se calcula (otro clic la deselecciona).
Actividad Duración Inicio más temprano Fin más temprano Inicio más tardío Fin más tardío H total H libre H independiente
A 4 0 4 0 4 0 0 0
B 2 0 2 0 2 0 0 0
C 2 2 4 2 4 0 0 0
D 5 4 9 4 9 0 0 0
E 4 4 8 7 11 3 1 1
F 4 9 13 9 13 0 0 0
G 2 9 11 11 13 2 2 2
H 2 9 11 11 13 2 2 0
I 3 13 16 13 16 0 0 0
Figura 2: Cargas con los inicios más tempranos

Se superan los 4 operarios en las semanas 1, 2, 5, 6, 7, 8, 10, 11 (cargas 5, 5, 5, 5, 5, 5, 6, 6).

Apartado 2

  1. Programe el proyecto periodo a periodo con un planificador en paralelo: en cada semana se ordenan las actividades disponibles según una regla de prioridad y se van admitiendo mientras quepan en el límite. Aplique tres reglas: (a) menor holgura total, (b) menor duración (SPT) y (c) mayor número de operarios. Dé la duración con cada una.

El planificador recorre las semanas: una actividad es disponible cuando han terminado sus predecesoras; las que ya están en curso siguen (no se interrumpen) y las nuevas entran por orden de prioridad mientras quepan en el límite.

A B C D E F G H I
(a) menor holgura total 1 5 7 9 18 14 14 22 24
(b) menor duración (SPT) 3 1 3 11 7 18 16 16 22
(c) más operarios primero 3 1 3 11 7 18 16 16 22
sin límite 1 1 3 5 5 10 10 10 14
Tabla 3: Programación con la regla (a) menor holgura total
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
A 1 1 1 1
B 4 4
C 3 3
D 2 2 2 2 2
E 3 3 3 3
F 2 2 2 2
G 1 1
H 3 3
I 1 1 1
Total 1 1 1 1 4 4 3 3 2 2 2 2 2 3 3 2 2 3 3 3 3 3 3 1 1 1
≤ límite sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí
Tabla 4: Programación con la regla (b) menor duración (SPT)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
A 1 1 1 1
B 4 4
C 3 3
D 2 2 2 2 2
E 3 3 3 3
F 2 2 2 2
G 1 1
H 3 3
I 1 1 1
Total 4 4 4 4 1 1 3 3 3 3 2 2 2 2 2 4 4 2 2 2 2 1 1 1
≤ límite sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí
Tabla 5: Programación con la regla (c) más operarios primero
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
A 1 1 1 1
B 4 4
C 3 3
D 2 2 2 2 2
E 3 3 3 3
F 2 2 2 2
G 1 1
H 3 3
I 1 1 1
Total 4 4 4 4 1 1 3 3 3 3 2 2 2 2 2 4 4 2 2 2 2 1 1 1
≤ límite sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí sí
(a) menor holgura total (b) menor duración (SPT) (c) más operarios primero sin límite de recursos
duración (semanas) 26 24 24 16

Apartado 3

  1. Compare con el resultado del algoritmo de Wiest-Levy de la librería (asignar).

La librería recorre también las semanas, pero en vez de admitir actividades hasta llenar el límite aplaza una semana, cuando la carga lo supera, las que tienen más holgura (y las ya empezadas no se tocan). Traza semana a semana:


Periodo: 1.

Periodo: 1. Total: 5. Se programan: [‘B’]

Periodo: 1. Se desplazan: [‘A’]


Periodo: 2.

Periodo: 2. Total: 5. Se programan: [‘B’]

Periodo: 2. Se desplazan: [‘A’]


Periodo: 3.

Periodo: 3. Total: 4. Se programan: [‘A’, ‘C’]


Periodo: 4.

Periodo: 4. Total: 4. Se programan: [‘A’, ‘C’]


Periodo: 5.

Periodo: 5. Total: 1. Se programan: [‘A’]


Periodo: 6.

Periodo: 6. Total: 1. Se programan: [‘A’]


Periodo: 7.

Periodo: 7. Total: 5. Se programan: [‘D’]

Periodo: 7. Se desplazan: [‘E’]


Periodo: 8.

Periodo: 8. Total: 5. Se programan: [‘D’]

Periodo: 8. Se desplazan: [‘E’]


Periodo: 9.

Periodo: 9. Total: 5. Se programan: [‘D’]

Periodo: 9. Se desplazan: [‘E’]


Periodo: 10.

Periodo: 10. Total: 5. Se programan: [‘D’]

Periodo: 10. Se desplazan: [‘E’]


Periodo: 11.

Periodo: 11. Total: 5. Se programan: [‘D’]

Periodo: 11. Se desplazan: [‘E’]


Periodo: 12.

Periodo: 12. Total: 6. Se programan: [‘G’, ‘E’]

Periodo: 12. Se desplazan: [‘F’]


Periodo: 13.

Periodo: 13. Total: 6. Se programan: [‘G’, ‘E’]

Periodo: 13. Se desplazan: [‘F’]


Periodo: 14.

Periodo: 14. Total: 5. Se programan: [‘E’]

Periodo: 14. Se desplazan: [‘F’]


Periodo: 15.

Periodo: 15. Total: 5. Se programan: [‘E’]

Periodo: 15. Se desplazan: [‘F’]


Periodo: 16.

Periodo: 16. Total: 5. Se programan: [‘F’]

Periodo: 16. Se desplazan: [‘H’]


Periodo: 17.

Periodo: 17. Total: 5. Se programan: [‘F’]

Periodo: 17. Se desplazan: [‘H’]


Periodo: 18.

Periodo: 18. Total: 5. Se programan: [‘F’]

Periodo: 18. Se desplazan: [‘H’]


Periodo: 19.

Periodo: 19. Total: 5. Se programan: [‘F’]

Periodo: 19. Se desplazan: [‘H’]


Periodo: 20.

Periodo: 20. Total: 3. Se programan: [‘H’]


Periodo: 21.

Periodo: 21. Total: 3. Se programan: [‘H’]


Periodo: 22.

Periodo: 22. Total: 1. Se programan: [‘I’]


Periodo: 23.

Periodo: 23. Total: 1. Se programan: [‘I’]


Periodo: 24.

Periodo: 24. Total: 1. Se programan: [‘I’]

Figura 3: Asignación de la librería (Wiest-Levy)

La librería obtiene 24 semanas; las reglas dan (a) menor holgura total: 26, (b) menor duración (SPT): 24, (c) más operarios primero: 24. Wiest-Levy también es una heurística (aplaza las actividades con más holgura), de modo que ninguna de las cuatro cifras es necesariamente el óptimo.

Apartado 4

  1. ¿Alguna regla garantiza la duración mínima? ¿Qué información usa la regla de la holgura que no usan las otras?

Ninguna regla garantiza el óptimo: el problema de programación con recursos limitados es NP-duro y las reglas de prioridad son heurísticas; para proyectos pequeños se puede comprobar por enumeración o programación entera. La regla de la holgura mínima es la única que usa la estructura del proyecto (qué actividades tienen margen y cuáles arrastrarían el plazo); SPT y «más operarios» sólo miran la actividad aislada. Por eso suele funcionar mejor, aunque no siempre: la holgura se calculó sin recursos y deja de ser exacta en cuanto se aplaza algo.