Programación de listas

La planificación por lista es un algoritmo voraz para la planificación en máquinas idénticas . La entrada de este algoritmo es una lista de trabajos que deben ejecutarse en un conjunto de m máquinas. La lista está ordenada en un orden fijo, que puede determinarse, por ejemplo, por la prioridad de ejecución de los trabajos o por su orden de llegada. El algoritmo ejecuta repetidamente los siguientes pasos hasta obtener una planificación válida:

• Toma el primer trabajo de la lista (el que tenga la mayor prioridad).
• Encuentra una máquina que esté disponible para realizar esta tarea.
  • Si se encuentra una máquina, programe esta tarea en esa máquina.
  • En caso contrario (si no hay ninguna máquina adecuada disponible), seleccione el siguiente trabajo de la lista.

Supongamos que hay cinco trabajos con tiempos de procesamiento {4,5,6,7,8} y m =2 procesadores. Entonces, la programación resultante es {4,6,8}, {5,7} y el tiempo de finalización es max(18,12)=18; si m =3, entonces la programación resultante es {4,7}, {5,8}, {6} y el tiempo de finalización es max(11,13,6)=13.

El algoritmo se ejecuta en tiempo${\displaystyle O(n)}$donde n es el número de trabajos. El algoritmo siempre devuelve una partición de los trabajos cuyo tiempo de finalización es como máximo${\displaystyle 2-1/m}$veces el tiempo de finalización óptimo. ^{[ 1 ]} Esto se debe a que tanto la duración del trabajo más largo como la duración promedio de todos los trabajos son límites inferiores para el tiempo de finalización óptimo. El algoritmo puede utilizarse como un algoritmo en línea , cuando no se puede controlar el orden en que llegan los elementos.

En lugar de usar un orden arbitrario, se pueden preordenar los trabajos para obtener mejores garantías. Algunas estrategias conocidas de planificación de listas son: ^{[ 2 ]}

• El algoritmo de nivel más alto primero , o HLF;
• Algoritmo de ruta más larga o LP;
• Planificación de tiempo de procesamiento más largo primero , o LPT; esta variante disminuye la relación de aproximación a${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}}$.
• Método de la ruta crítica .
• Tiempo de finalización más temprano heterogéneo o HEFT. Para el caso de trabajadores heterogéneos.

El algoritmo de planificación por lista tiene varias anomalías. ^{[ 1 ]} Supongamos que hay m = 3 máquinas y que las duraciones de los trabajos son:

3, 2, 2, 2, 4, 4, 4, 4, 9

Además, supongamos que todos los trabajos "4" deben ejecutarse después del cuarto trabajo "2". Entonces, la planificación por lista devuelve la siguiente programación:

• 3, 9
• 2, 2, 4, 4
• 2, [2 inactivos], 4, 4

y el tiempo de finalización es 12.

Anomalía 1. Si los trabajos "4" ya no dependen de trabajos anteriores, entonces la lista de programación es:

• 3, 4, 9
• 2, 2, 4
• 2, 4, 4

y el tiempo de finalización es de 16. Eliminar las dependencias ha aumentado el tiempo de finalización.

Anomalía 2. Supongamos que la duración de los trabajos disminuye en 1, a 2, 1, 1, 1, 3, 3, 3, 3, 8 (con las dependencias originales). Entonces, la lista de programación es:

• 2, 3, 3
• 1, 1, 3, 8
• 1, [1 inactivo], 3

y el tiempo de finalización es de 13. Acortar todos los trabajos ha aumentado el tiempo de finalización.

Anomalía 3. Supongamos que hay una máquina más (con las longitudes originales, con o sin dependencias). Entonces, la lista de programación es:

• 3, 4
• 2, 4, 9
• 2, 4
• 2, 4

y el tiempo de finalización es de 15. Agregar una máquina ha aumentado el tiempo de finalización.

Las anomalías se acotan de la siguiente manera. Supongamos que inicialmente teníamos m ₁ máquinas y el tiempo de finalización era t ₁ . Ahora, tenemos m ₂ máquinas, las dependencias son las mismas o se relajan, las duraciones de los trabajos son las mismas o más cortas, la lista es la misma o diferente, y el tiempo de finalización es t _2. Entonces: ^{[ 1 ] [ 3 ]}

${\displaystyle {\frac {t_{2}}{t_{1}}}\leq 1+{\frac {m_{1}-1}{m_{2}}}}$.

En particular, con el mismo número de máquinas, la proporción es${\displaystyle 2-{\frac {1}{m}}}$Un caso especial se da cuando la programación original es óptima; esto produce el límite.${\displaystyle 2-{\frac {1}{m}}}$sobre la relación de aproximación.