Algoritmo YDS

YDS es un algoritmo de programación dinámica velocidad escalar los procesadores que minimiza el consumo total de energía. Fue bautizada y desarrollado por Yao et al. Hay una línea y una versión sin conexión del algoritmo.

Algoritmo offline

Definiciones:

• Hay un conjunto de trabajos n $J := J_1, ..., J_n$, donde cada trabajo $J_i$ tiene un tiempo de liberación $r_i$, plazo $d_i$ y un volumen de procesamiento $w_i$.
• $I$ es un cierto intervalo de tiempo.
• También tenemos $\Delta_I = \frac{1}{|I|} \sum_{J_i \in S_I} w_i$, la densidad del trabajo en $I$.
• Y por último $S_I \in J$ es el conjunto de trabajos que deben ser procesados en $I$, eso significa puestos de trabajo con $[r_i, d_i] \in I$.

El algoritmo funciona entonces como sigue:

Tiempo $J \neq \{\}$

Determinar el intervalo de tiempo $I$ de la densidad máxima $\Delta_I$.

En $I$ los trabajos de proceso $S_I$ a la velocidad $\Delta_I$ Según EDF

Conjunto $J := J \setminus S_I$.

Quitar $I$ desde el horizonte temporal y actualización de los tiempos de liberación y los plazos de imprevisto empleos en consecuencia.

End While

En otros términos es un algoritmo recursivo que seguirá estos pasos hasta que todos los trabajos están programados:

1. Calcular todas las intensidades de todas las posibles combinaciones de intervalos. Esto significa que para cada combinación de hora Inicio hora y al final se calcula la intensidad de trabajo. Para ello los tiempos de los puestos de trabajo cuya hora de llegada y fecha límite se encuentran dentro del intervalo son añadidos y divididos por la longitud del intervalo. Para acelerar el proceso, sólo las combinaciones de tiempos de llegada y plazos posteriores deben ser considerados, como tiempos sin la llegada de un proceso o el plazo pueden ser reducidos a un intervalo más pequeño con los mismos procesos, aumentando de intensidad, e intervalos negativos no son válidos. Entonces se selecciona el intervalo de intensidad máxima. En el caso de múltiples intervalos igualmente intensos, uno puede ser elegido en, como intensidades de intervalos no solapados no influyen mutuamente y la eliminación de una parte de un intervalo no se va a cambiar la intensidad del resto, como los procesos son removidos proporcionalmente.
2. Los procesos dentro de este intervalo se programan utilizando primeros primero de plazo, lo que significa que el trabajo dentro de este intervalo cuyo plazo va a llegar lo más pronto posible está programado en primer lugar, y así sucesivamente. Los trabajos se ejecutan en la intensidad calculada anteriormente para caber todos los trabajos dentro del intervalo.
3. El intervalo se retira de la línea de tiempo, como no hay cálculos pueden ser programados aquí. Para simplificar aún más los cálculos, se recalculan todos los horarios de llegada y los plazos de puestos restantes de omitir ya ocupado veces.

Por ejemplo, supongamos que un trabajo $A$ con hora de llegada $a_A = 0$, plazo $d_A = 10$ y una carga de trabajo $w_A = 5$y un trabajo $B$ con $a_B = 5$, $d_B = 10$ y $w_B = 4$. Asumir que el intervalo anterior era de tiempo $3$ Para $8$. Para omitir este intervalo, los tiempos de $A$ y $B$ necesitan ser ajustadas; las cargas de trabajo se ven afectados, como no se ha hecho ningún trabajo para cualquiera $A$ o $B$. $a_A$ sigue siendo el mismo, como tiene inafectado por omisiones más adelante. $a_B$, sin embargo, necesita ser cambiado a $5$, como $10 - (8 - 3) = 5$. Este es el trabajo de tiempo $A$ ha dejado antes de su fecha límite. La hora de llegada $a_B$ se convierte en $3$, pues habría sido dentro del intervalo quitado. $d_B$ también se convierte en $5$, como el tiempo dejado tras el intervalo eliminado es $2$. Sin embargo, es importante, para recordar los tiempos de llegada y fecha límite para el montaje posterior de la programación.

1. Repita los pasos 1-3 hasta que todos los trabajos se han programado.
2. Montar puestos de trabajo en programación final según los intervalos de tiempo asignado. Sin embargo, recuerda que un intervalo puede ser dividido en dos por otro intervalo calculado anteriormente.

Para cualquier instancia de trabajo, el algoritmo calcula un plan óptimo minimizando el consumo total de energía.

Véase también

• EDF algoritmo

Otras Páginas

• Rehumanization
• Seguro
• Numero de cuenta bancaria internacional
• Preocupacion (de negocios)
• Pegamento de la fibrina