4.3.2. Planificación de tareas.
Función factible: Dada una planificación (i1, i2, ..., ik) en un paso del algoritmo y un nuevo candidato j,
- ¿Cuándo será factible la solución parcial que incluye a j?
- ¿Dónde debería ser colocado j dentro de la planificación?
Solución: buscar si existe alguna ordenación de {i1, i2, ..., ik, j} que respete los plazos de ejecución di. Problema: complejidad (k+1)!
Parece lógico no comprobar todas las posibles ordenaciones, sino hacer una ordenación de forma que las tareas con plazos di más tempranos se ejecuten antes, y dejar para después las que tengan plazos mayores.
Lema: Sea J un conjunto de k tareas, entonces existe una ordenación factible de J (es decir que respeta los plazos) si y sólo si la ordenación S = (s1, s2, ..., sk), con ds1 ? ds2 ? ... ? dsk es factible.
Es decir, sólo es necesario probar la planificación en orden creciente de plazo de ejecución, comprobando si cada dsi ? i (la tarea ejecutada en la i-ésima posición tiene un plazo de i ó más).