4.3.2. Planificación de tareas.
Demostración del lema:
- Si el orden S es factible entonces existe una ordenación factible de J: Trivial.
- Si existe una ordenación factible de J entonces S es factible:
Supongamos (reducción al absurdo) que existe esa ordenación pero que S (definida de la forma anterior) no es factible.
Entonces debe existir una tarea sr tal que dsr < r. Puesto que las r-1 tareas anteriores tienen dsi ? dsr < r, habrán r tareas cuyo plazo sea menor que r.
En conclusión, no puede existir ningún orden de las tareas J, de forma que se ejecuten dentro de su plazo.
Estructura del algoritmo voraz:
- Empezar con una secuencia vacía, con todos las tareas como candidatas.
- Ordenar los candidatos según el valor de gi.
- En cada paso, hasta que se acaben los candidatos, repetir:
- Elegir entre los candidatos restantes el que tenga mayor beneficio.
- Comprobar si es posible añadir la tarea elegida a la solución actual. Para ello introducir la nueva tarea en la posición adecuada, según el valor de plazo d.
- Si el nuevo orden (s1, s2, ..., sk) es tal que dsi ? i, para todo i entre 1 y k, entonces el nuevo candidato es factible. Sino rechazar el candidato.