L5.4 Kapitola K5 — Rozvrhování (Slot 5) · [MUST]

McNaughton (P |pmtn| C_max)

Z [L5.1] Grahamovy notace víš, co znamená $P \,|\, \mathrm{pmtn} \,|\, C_{max}$: $R$ identických paralelních procesorů, nezávislé preemptivní úlohy (prázdná $\beta$ jinak = bez precedencí, $r_j = 0$), minimalizuj makespan. A z pmtn-demos v [L5.1] už tušíš, že preempce umí stlačit $C_{max}$ pod nepreemptivní optimum. Dnes ten princip proměníme v kompletní algoritmus — McNaughtonův — který je u zkoušky stavebním kamenem: sám o sobě je cvičná klasika a o pár lekcí dál ho bude volat Muntz & Coffman [L5.10] jako podprogram („Use McNaughton to re-schedule parts with more tasks on less res.“).

Ostrov „easy“ v NP-hard moři (slide 38)

Bez preempce je rozvrhování na paralelních strojích těžké hned od dvou procesorů: rozhodnout, jestli jde $n$ úloh rozdělit na dva stroje s makespanem $\le \frac{1}{2}\sum p_i$, je přesně 2-Partition — tu jsi modeloval v [L1.1] T01 (2-Partition, vč. vztahu k P2||Cmax).

Slide 38 (EN 1:1) — Scheduling on Parallel Identical Resources, Minimizing $C_{max}$

• “$P2 \,||\, C_{\max}$ — NP-hard … the problem is NP-hard because the 2 partition problem (see ILP lecture) can be reduced to $P2 \,||\, C_{\max}$ while comparing the optimal $C_{\max}$ with the threshold of $0.5 \cdot \sum_{i \in 1..n} p_i$.”
• “$P \,|\, \mathrm{pmtn} \,|\, C_{\max}$ — easy: can be solved by the McNaughton algorithm in $\mathcal{O}(n)$.”
• “$P \,|\, \mathrm{pmtn}, r_j, \tilde{d}_j \,|\, -$ — easy: decision version of maximum flow problem (see the lecture on Flows).”
• “$P \,|\, \mathrm{prec} \,|\, C_{\max}$ — NP-hard: LS — approximation algorithm with factor $r_{LS} = 2 - \frac{1}{R}$.”
• “$P \,||\, C_{\max}$ — NP-hard: LPT — approximation algorithm with factor $r_{LPT} = \frac{4}{3} - \frac{1}{3R}$; dynamic programming — Rothkopf's pseudopolynomial algorithm.”
• “$P \,|\, \mathrm{pmtn}, \mathrm{prec} \,|\, C_{\max}$ — NP-hard: Muntz&Coffman's level algorithm with factor $r_{MC} = 2 - \frac{2}{R}$.”

Mapu si zapamatuj: preempce sama o sobě dělá z $C_{max}$ na identických strojích snadný problém (dnešní lekce); preempce + časová okna $r_j, \tilde{d}_j$ = toky [L5.0]; jakmile ale přibudou precedence, je to zase NP-hard a McNaughton přežívá jen jako podprogram aproximačního Muntze&Coffmana [L5.10]. Nepreemptivní $P\,||\,C_{max}$ (bez precedencí) řeší DP Rothkopf [L5.11] (pseudopolynomiálně) a aproximačně LPT [L5.12]; list scheduling (LS) je naproti tomu aproximace pro precedenční variantu $P\,|\,\mathrm{prec}\,|\,C_{max}$.

Jak rychle to vůbec může být hotovo?

Než začneš rozvrhovat, spočti si, pod co se žádný — ani sebechytřejší — preemptivní rozvrh nedostane.

Slide 40 (EN 1:1) — interpretace $C_{max}^*$

“The term $C_{\max}^* = \max\left\{\max_{i=1\ldots n}\{p_i\},\ \frac{1}{R} \sum_{1}^{n} p_i\right\}$ should be interpreted as follows:

• component $\max_{i=1\ldots n}\{p_i\}$ represents the sequential nature of each task — it's parts can be assigned to different resources, but these parts can not be run simultaneously. Note that each task can be divided into two parts at most.
• component $\frac{1}{R} \sum_{1}^{n} p_i$ represents a situation when all resources work without idle waiting.”

Algoritmus: nalévání s wrap-around (slide 39)

Představ si $R$ „polic“, každou dlouhou přesně $C_{max}^*$. McNaughton bere úlohy v libovolném pořadí a nalévá je na první polici zleva doprava. Když se úloha nevejde (přetekla by za $C_{max}^*$), rozřízne ji: kus do konce police nechá tam a zbytkem začne plnit další polici od času $0$ — to je ten wrap-around.

Slide 39 (EN 1:1) — McNaughton's Algorithm for $P \,|\, \mathrm{pmtn} \,|\, C_{\max}$

“Input: $R$, number of parallel identical resources, $n$, number of preemptive tasks and computation times $(p_1, p_2, \ldots, p_n)$.
Output: $n$-element vectors $s^1, s^2, z^1, z^2$ where $s_i^1$ (resp. $s_i^2$) is start time of the first (resp. second) part of task $T_i$ and $z_i^1$ (resp. $z_i^2$) is the resource ID on which the first (resp. second) part of task $T_i$ will be executed.”

s_i^1 = s_i^2 = z_i^1 = z_i^2 := 0 for all i ∈ 1..n;
t := 0; v := 1; i := 1;
C*_max = max { max_{i=1..n} {p_i}, (1/R) · Σ_{1..n} p_i };
while i ≤ n do
    if t + p_i ≤ C*_max then
        s_i^1 := t; z_i^1 := v; t := t + p_i; i := i + 1;
    else
        s_i^2 := t; z_i^2 := v; p_i := p_i − (C*_max − t); t := 0; v := v + 1;
    end
end

“Time complexity is $\mathcal{O}(n)$.”

Čtení pseudokódu: $t$ je hladina zaplnění aktuální police $v$. Větev if = úloha se vejde celá. Větev else = přetečení: kus $[t, C_{max}^*]$ zůstane na stroji $v$ (uloží se jako druhá část $s_i^2, z_i^2$ — časově běží později), zbytek $p_i - (C_{max}^* - t)$ se vrátí do smyčky se stejným $i$ a přistane na stroji $v+1$ od času $0$ jako první část ($s_i^1 = 0$). Každá úloha projde větví else nejvýš jednou — proto nejvýš dvě části.

Optimalita je teď zadarmo: výsledný rozvrh je přípustný (kusy se nepřekrývají, vše se vešlo) a končí v $C_{max}^*$, což je dolní mez každého rozvrhu — takže $C_{max}^*$ je optimum a McNaughton ho dosahuje. Žádné chytré pořadí úloh není potřeba.

Běh na instanci slidu 40 (Example 1)

Slide 40, Example 1: $p = (2, 3, 2, 3, 2)$, $R = 3$. Proklikej běh — v každém kroku sleduj hladinu $t$ a kde řežeme:

Nebezpečné polopravdy kolem McNaughtona

• „$C_{max}^* = \frac{1}{R}\sum p_i$“ — NE. Bez složky $\max_i p_i$ vyrobíš rozvrh, kde se rozříznutá dlouhá úloha překrývá sama se sebou. Když $\max_i p_i$ dominuje (viz T01 níže), stroje musí zahálet a průměr $\frac{1}{R}\sum p_i$ je nedosažitelný.
• McNaughton platí jen pro $P \,|\, \mathrm{pmtn} \,|\, C_{max}$ — nezávislé úlohy, bez precedencí, bez release times. S precedencemi je problém NP-hard a řeší se aproximačně (Muntz&Coffman [L5.10]); s okny $r_j, \tilde{d}_j$ jde feasibilita přes toky [L5.0].
• Bez pmtn nelze „zaokrouhlit“: nepreemptivní $P2\,||\,C_{max}$ je NP-hard (2-Partition, slide 38) — z McNaughtonova rozvrhu nepreemptivní optimum slepením kusů nedostaneš (T02 níže ukazuje instanci, kde je nepreemptivní optimum ostře horší).

Key takeaways — L5.4

• McNaughton ($P \,|\, \mathrm{pmtn} \,|\, C_{max}$, $\mathcal{O}(n)$): $C_{max}^* = \max\{\max_i p_i,\ \frac{1}{R}\sum_i p_i\}$; úlohy v libovolném pořadí nalévej sekvenčně do polic délky $C_{max}^*$, při přetečení nech kus $[t, C_{max}^*]$ na stroji $v$ a zbytkem pokračuj na stroji $v{+}1$ od času $0$ (wrap-around).
• Dvě složky meze: $\max p_i$ = sekvenčnost úlohy (kusy nesmí běžet současně — a zaručuje, že zalomený zbytek délky $p_i - (C_{max}^* - t) \le t$ nekoliduje sám se sebou); $\frac{1}{R}\sum p_i$ = stroje bez zahálení (vše se vejde do $R$ polic).
• Optimální pro nezávislé preemptivní úlohy: rozvrh dosáhne dolní meze $C_{max}^*$. Každá úloha má nejvýš 2 části, preempcí je nejvýš $R - 1$ (kontrola Ganttu!).
• Hranice platnosti: bez pmtn NP-hard už pro $R = 2$ (2-Partition [L1.1] → Rothkopf [L5.11] / LPT [L5.12]); s precedencemi NP-hard → Muntz&Coffman [L5.10] používá McNaughtona jako podprogram; s $r_j, \tilde{d}_j$ feasibilita → toky [L5.0]. Volba metody: tahák [L5.14].
• U zkoušky: spočti $C_{max}^*$ (obě složky vypiš!), nakresli Gantt, vyznač preempce a případné zahálení.