7.3.2. Secuenciamiento de trabajos.
Igual que en el algoritmo voraz, dado un conjunto de tareas el orden de ejecución será en orden creciente de plazo, di.
Representación de la solución:
- Representación binaria: (s1, s2, ..., sn), con si = (0, 1).
-
Cálculo de cotas:
- Cota inferior: penalización de los trabajos asignados con valor 0 hasta este nodo (son los trabajos que no se ejecutan).
- Cota superior: la cota inferior más la penalización de los trabajos no considerados hasta este momento.
- Coste estimado: podemos aproximarlo con la media de las dos cotas anteriores.