4.3.2. Planificación de tareas.
Por reducción al absurdo, si S=(t1, t2, ..., tn) no están ordenados de forma creciente entonces podemos seleccionar un i, j, tal que (i<j) y (ti>tj). Si los intercambiamos en el orden S entonces el nuevo tiempo total disminuye:
TTOTAL = T’TOTAL- (n-i+1)ti - (n-j+1)tj + (n-i+1)tj + (n-j+1)ti = T’TOTAL + (i-j)ti + (j-i)tj =
= T’TOTAL + (i-j)(ti - tj) < T’TOTAL {Pues (i-j) < 0 y (ti - tj) > 0}
Conclusión: La solución óptima se obtiene ordenando las tareas en orden creciente de duración. El algoritmo voraz es una simple ordenación, que se puede ejecutar en ?(n·log n).
Planificación con plazo fijo
En la planificación con plazo fijo suponemos que todas las n tareas requieren un tiempo unitario en ejecutarse.
En cualquier instante T = 1, 2, ... podemos ejecutar una única tarea i. La ejecución de esta tarea provocará un beneficio gi.
Restricción: una tarea i sólo puede ejecutarse si se hace antes de un plazo di. Cada tarea tiene un plazo de ejecución y un beneficio dados.
En general puede que no sea posible ejecutar todas las tareas.