YDS algorithm

YDS is a scheduling algorithm for dynamic speed scaling processors which minimizes the total energy consumption. It was named after and developed by Yao et al. There is both an online and an offline version of the algorithm.

Offline Algorithm

Definitions:

• There is a set of n Jobs $J:=J_{1},...,J_{n}$, where each job $J_{i}$ has a release time $r_{i}$, deadline $d_{i}$ and a processing volume $w_{i}$.
• $I$ is a certain time interval.
• Also we have $\Delta _{I}={\frac {1}{|I|}}\sum _{J_{i}\in S_{I}}w_{i}$, the work density in $I$.
• And finally $S_{I}\in J$ is the set of Jobs that that must be processed in $I$.

The algorithm then works as follows:

While $J\neq \{\}$

Determine the time interval $I$ of maximum density $\Delta _{I}$.

In $I$ process the jobs of $S_{I}$ at speed $\Delta _{I}$ according to EDF

Set $J:=J\setminus S_{I}$.

Remove $I$ from the time horizon and update the release times and deadlines of unscheduled jobs accordingly.

end While

For any Job instance, the algorithm computes an optimal schedule minimizing the total energy consumption.

See also

• EDF scheduling algorithm