4.3.2. Planificación de tareas.
Podemos aplicar la técnica de avance rápido:
- Los candidatos son las n tareas.
- La solución no es un conjunto de candidatos, sino el orden en que deben ejecutarse.
- Añadir un nuevo candidato no es una unión de conjuntos sino insertar un nuevo elemento a una lista.
- Función de selección: ejecutar primero la tarea más corta de entre los candidatos restantes.
Solución del problema de planificación: ordenar las tareas en orden creciente de duración (ti).
¿Garantiza este método la solución óptima?
Demostración: Supongamos que tenemos una ordenación S= (i1, i2, ..., in), con tiempos (t1, t2, ..., tn), entonces el tiempo hasta que se finaliza la tarea i será:
El tiempo total de espera de los procesos será:
TTOTAL = t1 + (t1+t2) + (t1+t2+t3) + ... + (t1+t2+ ... + tn) = n·t1 + (n-1)·t2 +...+ tn =