Enunciado
Considere el proyecto cuyo cuadro de prelaciones, duraciones (semanas) y operarios necesarios se adjunta. Sólo se dispone de 5 operarios y las actividades no pueden interrumpirse una vez empezadas.
- Calcule el calendario sin restricción de recursos y dibuje las cargas con los inicios más tempranos. ¿En qué semanas se superan los 5 operarios?
- 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.
- Compare con el resultado del algoritmo de Wiest-Levy de la librería (
asignar).
- ¿Alguna regla garantiza la duración mínima? ¿Qué información usa la regla de la holgura que no usan las otras?
Resolución
Apartado 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 5 operarios?
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):
Se superan los 5 operarios en las semanas 1, 2, 3, 9, 10, 11 (cargas 7, 7, 6, 6, 6, 6).
Apartado 2
- 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) menor holgura total |
1 |
1 |
4 |
3 |
3 |
9 |
9 |
12 |
15 |
| (b) menor duración (SPT) |
1 |
1 |
3 |
3 |
4 |
8 |
9 |
12 |
15 |
| (c) más operarios primero |
1 |
1 |
3 |
4 |
3 |
8 |
8 |
11 |
14 |
| sin límite |
1 |
1 |
1 |
3 |
3 |
7 |
8 |
11 |
9 |
| duración (semanas) |
17 |
17 |
16 |
13 |
Apartado 3
- 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. Total: 7. Se programan: [‘B’, ‘A’]
Periodo: 1. Se desplazan: [‘C’]
Periodo: 2. Total: 7. Se programan: [‘B’, ‘A’]
Periodo: 2. Se desplazan: [‘C’]
Periodo: 3. Total: 6. Se programan: [‘C’, ‘B’, ‘E’]
Periodo: 3. Se desplazan: [‘D’]
Periodo: 4. Total: 5. Se programan: [‘C’, ‘E’, ‘D’]
Periodo: 5. Total: 5. Se programan: [‘C’, ‘E’, ‘D’]
Periodo: 6. Total: 5. Se programan: [‘C’, ‘E’, ‘D’]
Periodo: 7. Total: 5. Se programan: [‘C’, ‘E’, ‘D’]
Periodo: 8. Total: 5. Se programan: [‘G’, ‘F’]
Periodo: 9. Total: 5. Se programan: [‘G’, ‘F’]
Periodo: 10. Total: 6. Se programan: [‘G’]
Periodo: 10. Se desplazan: [‘I’]
Periodo: 11. Total: 6. Se programan: [‘H’]
Periodo: 11. Se desplazan: [‘I’]
Periodo: 12. Total: 6. Se programan: [‘H’]
Periodo: 12. Se desplazan: [‘I’]
Periodo: 13. Total: 6. Se programan: [‘H’]
Periodo: 13. Se desplazan: [‘I’]
Periodo: 14. Total: 2. Se programan: [‘I’]
Periodo: 15. Total: 2. Se programan: [‘I’]
Periodo: 16. Total: 2. Se programan: [‘I’]
La librería obtiene 16 semanas; las reglas dan (a) menor holgura total: 17, (b) menor duración (SPT): 17, (c) más operarios primero: 16. 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
- ¿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.
