Lower Bound on Load

A lower bound on the load of a problem window can be established using the following well known argument, which is also the basis of [16]:

Since the problem job misses its deadline, the sum of the lengths of all the time intervals in which the problem job does not execute must exceed its slack time, $d_k - c_k$.

Figure 1: All processors must be busy whenever $\tau _k$ is not executing.

This situation is illustrated for $m = 3$ processors in Figure 1. The diagonally shaded rectangles indicate times during which $\tau _k$ executes. The dotted rectangles indicate times during which all $m$ processors must be busy executing other jobs in the demand for this interval.

Lemma 3 (lower bound on load)   If $W/d_k$ is the load of the interval $[t, t+d_k)$, where $t+d_k$ is a missed deadline of $\tau _k$, then

$$\frac{W}{d_k} > m(1-\frac{c_k}{d_k})+\frac{c_k}{d_k}$$

Proof: Let $x$ be the amount of time that the problem job executes in the interval $[t, t+d_k)$. Since $\tau _k$ misses its deadline at $t+d_k$, we know that $x<c_k$. A processor is never idle while a job is waiting to execute. Therefore, during the problem window, whenever the problem job is not executing all $m$ processors must be busy executing other jobs with deadlines on or before $t+d_k$. The sum of the lengths of all the intervals in the problem window for which all $m$ processors are executing other jobs belonging to the demand of the interval must be at least $d_k - x$. Summing up the latter demand and the execution of $\tau _k$ itself, we have $W \geq m(d_k - x) + x > md_k - (m-1)c_k$. If we divide both sides of the inequality by $d_k$, the lemma follows.$\Box$