EDD a Hornův algoritmus ($1\,|\,\mathrm{pmtn}, r_j\,|\,L_{\max}$)

Slide 28 (EN 1:1) — Problem $1\,||\,L_{\max}$ — EDD and its Optimality

“Can be solved by EDD (Earliest Due Date first), i.e. tasks are scheduled in order of nondecreasing due dates. Time complexity is $\mathcal{O}(n \cdot \log n)$.

Optimality can be proven by simple swaps:

• Let $S^A$ be an optimal schedule produced by an algorithm A.
• Let $S^{EDD}$ be a schedule produced by EDD.
• If $S^A \ne S^{EDD}$, then there exist two tasks $T_a$ and $T_b$ with $d_a \le d_b$, such that $T_b$ immediately precedes $T_a$ in $S^A$.
• Swap of $T_a$ and $T_b$ cannot increase the maximum lateness of the task set $L_{\max}$.
• By finite number of swaps, $S^A$ is changed to $S^{EDD}$,
  $S^A \xrightarrow{\text{swap}} S' \xrightarrow{\text{swap}} \cdots \xrightarrow{\text{swap}} S^{EDD}$”

Slide 29 (EN 1:1) — Optimality of EDD — Illustration

“$L_{\max}^A(\{T_a, T_b\}) = C_a^A - d_a$,   $L_{\max}'(\{T_a, T_b\}) = \max\{L_a', L_b'\}$.

Two cases must be considered when $p_a > 0$ and $p_b > 0$:

1. If $L_a' \ge L_b'$ then $L_{\max}'(\{T_a, T_b\}) = C_a' - d_a < C_a^A - d_a$
2. If $L_a' \le L_b'$ then $L_{\max}'(\{T_a, T_b\}) = C_b' - d_b = C_a^A - d_b < C_a^A - d_a$”

“Since, in both cases, $L_{\max}'(\{T_a, T_b\}) < L_{\max}^A(\{T_a, T_b\})$ we can conclude that the swap of $T_a$ and $T_b$ decreases $L_{\max}(\{T_a, T_b\})$ and thus it cannot increase $L_{\max}(\mathcal{T})$, the maximum lateness of all tasks.”

Slide 27 (EN 1:1) — Scheduling on One Resource — Minimizing $L_{\max}$

• “$1\,||\,L_{\max}$ — solved by EDD (Earliest Due Date first), i.e. tasks are scheduled in order of nondecreasing due dates
• $1\,|\,r_j\,|\,L_{\max}$ — NP-hard
• $1\,|\,\mathrm{pmtn}, r_j\,|\,L_{\max}$ — polynomial — iterating EDD by Horn's algorithm
• $1\,|\,\mathrm{pmtn}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$ — polynomial — the same Horn's algorithm often called EDF
• $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$ — polynomial — transformation to independent task set and then solved EDF

Important notes:

• “minimization of $L_{\max}$ implies existence of due-date $d_j$ (even if it is not in $\beta$ notation)
• $L_{\max}$ may have negative value. In such case, minimization of lateness $L_{\max}$ may be interpreted as maximization of earliness.”

Slide 30 (EN 1:1) — Problem $1\,|\,\mathrm{pmtn}, r_j\,|\,L_{\max}$ — Horn's Algorithm

“Input: $\mathcal{T}$, set of $n$ preemptive tasks. Processing times $(p_1, p_2, \ldots, p_n)$, release dates $(r_1, r_2, \ldots, r_n)$ and due-dates $(d_1, d_2, \ldots, d_n)$.
Output: Start times of preempted parts of tasks.”

while T != ∅ do
    t1 := min_{Tj ∈ T} {rj};                          // t1 is now
    if all tasks are ready at time t1 then t2 = ∞;
    else t2 = min_{Tj ∈ T} {rj | rj > t1};            // situation changes in t2
    T' = {Tj | Tj ∈ T, rj = t1};                      // set of ready tasks
    choose Tk ∈ T' with minimal dj;                   // EDD in T'
    δ := min {pk, t2 − t1};
    schedule Tk or its part in interval ⟨t1, t1 + δ);
    if δ = pk then T := T \ {Tk};
    else pk := pk − δ;                                // preemption
    for Tj ∈ T' do rj := t1 + δ;
end

Slide 32 (EN 1:1) — Optimality of Horn's Algorithm

“Theorem — Optimality of Horn's Algorithm. Given a set of $n$ independent preemptive tasks with arbitrary release times, any algorithm that at any instant executes the task with earliest due date among all the ready tasks is optimal with respect to $L_{\max}$ minimization.

When we assume $1\,|\,\mathrm{pmtn}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$ then the algorithm is often called EDF (Earliest Deadline First) and we will speak about deadlines rather than due dates from now on. Such algorithm:

• minimizes $L_{\max}$ (i.e. its non positive value)
• decides schedulability — if there exists a feasible schedule ($L_{\max} \le 0$) for the given instance, then the EDF is able to find it”

Slidy 33–34 (EN 1:1) — důkaz výměnami jednotkových dílků

“Assuming the input parameters to be nonnegative integers, the proof of the theorem is based on the following reasoning:

• Let $S^A$ be an optimal schedule produced by algorithm A
• Let $S^{EDF}$ be a schedule produced by EDF
• Let schedule $S^A$ starts at time $t = 0$ and $D$ is the latest deadline.
• Without loss of generality $S^A$ can be divided into unit-time slices.
• Let $i_t$ is the id of the task executing slice $t$. Let $j_t$ is the id of the ready task with earliest deadline at time $t$.
• If $S^A \ne S^{EDF}$ then there is slice $t$ such that $i_t \ne j_t$.
• Swap of slices of $T_{i_t}$ and $T_{j_t}$ cannot increase the maximum lateness of the task set $L_{\max}$.
• $S^{EDF}$ is obtained from $S^A$ by at most $D$ swaps.

“Using the same argument adopted in the proof of EDD optimality for $1\,||\,L_{\max}$, it is easy to show that each swap cannot increase the maximum lateness of the task set $L_{\max}$.” (Oba důkazy — EDD i Horn/EDF — patří mezi férově zkoušené „dokažte“ u ústní.)