Muntz & Coffman (P |pmtn,prec| C_max)

Slide 51 (EN 1:1) — Muntz&Coffman's Level Algorithm for $P \,|\,pmtn, prec\,|\, C_{\max}$

“Principle:

• tasks are picked from the list ordered by the level of tasks
• the level of task $T_j$ — sum of $p_i$ (including $p_j$) along the longest path from $T_j$ to a terminal task (a task with no successor)
• when more tasks of the same level are assigned to less resources, each task gets part of the resource capacity $\beta$
• the algorithm moves forward to time $\tau$ when one of the tasks ends or the task with a lower level should be processed by a bigger capacity $\beta$ than the tasks with a higher level

For $P2 \,|\,pmtn, prec\,|\, C_{\max}$ and $P \,|\,pmtn, forest\,|\, C_{\max}$, the algorithm is exact. For $P \,|\,pmtn, prec\,|\, C_{\max}$ approximation alg. with factor $r_{MC} = 2 - \frac{2}{R}$. Time complexity is $\mathcal{O}(n^2)$.

“Input: $R$, the number of parallel identical resources, $n$, the number of preemptive tasks, proc. times $(p_1, p_2, \ldots, p_n)$ and DAG. Output: $n$-elements vectors $s^1, \ldots, s^k, \ldots s^K$ and $z^1, \ldots, z^k, \ldots z^K$ where $s_i^k$ is the start time of the $k$-th part of task $T_i$ and $z_i^k$ is corresponding resource ID.”

Slide 52 (EN 1:1) — pseudokód

compute the level of all tasks ; t := 0; h := R;        // h free res.
while unfinished tasks exist do
    construct Z;                          // tasks that are free at time t
    while h > 0 and |Z| > 0 do            // free resources, free tasks
        construct S;                      // tasks in Z with the highest level
        if |S| > h then                   // more tasks than resources
            assign part of capacity β := h/|S| to tasks in S; h := 0;
        else
            assign one resource to each task in S; β := 1; h := h - |S|;
        end
        Z := Z \ S;
    end
    compute δ;                            // see explanation below
    decrease proc.times and levels by (δ)·β;   // finished part
    t := t + δ; h := R;
end
Use McNaughton to re-schedule parts with more tasks on less res.;

“$t + \delta$ is time when (1) EITHER one task is finished (2) OR a current level of an assigned task becomes lower than a level of an unassigned ready task (3) OR a task executed at faster rate $\beta$ starts to have current level below the current level of a task executed at slower rate $\beta$.”

Slide 53 (EN 1:1, výňatek) — Example

• “$t = 0$, $p = (3, 4, 3, 5, 3, 1, 2, 0)$, $level = (8, 9, 8, 5, 5, 1, 2, 0)$, $\mathcal{Z} = \{T_1, T_2, T_3\}$: $h = 2, \mathcal{S} = \{T_2\}, \beta = 1$; $h = 1, \mathcal{S} = \{T_1, T_3\}, \beta = 0.5$; $\delta = 2$ due to the case (3)” — $T_2$ klesá rychlostí 1 z levelu 9, dvojice $T_1, T_3$ rychlostí 0,5 z levelu 8; protnou se: $9 - \delta = 8 - 0{,}5\,\delta \Rightarrow \delta = 2$.
• “$t = 2$, $p = (2, 2, 2, 5, 3, 1, 2, 0)$, $level = (7, 7, 7, 5, 5, 1, 2, 0)$, $\mathcal{Z} = \{T_1, T_2, T_3\}$: $h = 2, \mathcal{S} = \{T_1, T_2, T_3\}, \beta = 0.67$; $\delta = 3$ due to the case (1)” — tři úlohy po 2 jednotkách rychlostí $\tfrac{2}{3}$: hotovo za $2 / \tfrac{2}{3} = 3$.

(Slide pokračuje dalšími iteracemi a grafem „levels–time“; přepis obrázku je dál nečitelný, proto si celý běh poctivě projdeme na vlastní instanci níže.)