7.3.2. Secuenciamiento de trabajos.
Es una generalización del problema de la planificación con plazo fijo (del tema 4, algoritmos voraces).
Tenemos n trabajos y un solo procesador.
Cada trabajo i tiene:
- Duración: ti
- Plazo de ejecución: di
- Penalización si no se ejecuta: pi
Dado un trabajo, o bien empieza a ejecutarse dentro de su plazo di (requiriendo un tiempo ti) o bien no se ejecuta, produciendo una penalización pi.
Objetivo: hacer una planificación de las tareas de forma que se minimice la penalización de las tareas no ejecutadas.