4.3.2. Planificación de tareas.
Objetivo: dar una planificación de las tareas a ejecutar (i1, i2, ..., im) de forma que se maximice el beneficio obtenido:
Ejemplo: n = 4
g = (100, 10, 15, 27)
d = ( 2, 1, 2, 1)
Soluciones:
(1) GTOTAL = 100 (2, 1) GTOTAL = 110
(4, 3) GTOTAL = 42 (4, 1) GTOTAL = 127
Comprobar todas las posibilidades tendría una complejidad n!
Con un algoritmo voraz construimos la solución paso a paso.
Una solución estará formada por un conjunto de candidatos, junto con un orden de ejecución de los mismos, S = (i1, i2, ..., im).
Función solución: Tendremos la solución cuando hayamos tratado todos los candidatos.
Función de selección: de los candidatos restantes elegir el que tenga mayor valor de beneficio.