Rothkopf DP pro P || Cmax
Z [L5.4] McNaughtona víš, že nepreemptivní $P \,||\, C_{max}$ je NP-hard už pro dva stroje — rozhodnout $C_{max} \le \frac{1}{2}\sum p_i$ je přesně [L1.1] 2-Partition. „NP-hard“ ale neznamená „beznadějné“: dnes si postavíme exaktní algoritmus — Rothkopfovo dynamické programování (slidy 47–50) — který platí daň jinde: jeho čas roste s hodnotou horní meze $UB$, ne jen s počtem úloh. Stejný „pseudopolynomiální“ obchod jsi už viděl u time-indexed ILP [L5.3]. Notaci $P \,||\, C_{max}$ čteš dle [L5.1]: identické paralelní stroje, nezávislé nepreemptivní úlohy (prázdná $\beta$: bez precedencí, bez $r_j$, bez preempce), minimalizuj makespan.
Co si stačí pamatovat? Jen zátěže (slide 47)
DP stojí a padá s volbou stavu. U knapsacku (uvidíš v [L7.1]) je stavem „kapacita“, u Rothkopfa to bude vektor obsazenosti strojů. Proč to stačí?
Zkus sám: u $P \,||\, C_{max}$ chceš najít celý rozvrh — start časy a stroje. Proč o částečném rozvrhu prvních $i$ úloh stačí vědět jen $R$ čísel: kolik práce už leží na kterém stroji?
V $\beta$ není nic: žádné $r_j$, žádné deadliny, žádné precedence. Úlohy přiřazené jednomu stroji proto můžeš nalepit těsně za sebe od času 0 — žádná mezera nikdy nepomůže a na pořadí na stroji nezáleží (poslední úloha vždy skončí v čase = součet délek = zátěž stroje). Rozvrh je tedy plně určen rozdělením úloh strojům a $C_{max}$ = největší zátěž. A dvě různá rozdělení prvních $i$ úloh se stejným vektorem zátěží $(t_1, \ldots, t_R)$ jsou pro budoucnost zaměnitelná — zbylé úlohy „vidí“ jen obsazené intervaly $\langle 0, t_v\rangle$. Přesně to je definice DP stavu.
Slide 47 (EN 1:1) — Dynamic Programming for $P \,||\, C_{\max}$ [Rothkopf]“For fixed $R$, the number of processors, there is a pseudopolynomial algorithm — input instance is restricted to bounded nonnegative integers: number of tasks and their processing times.
- we add a binary variable $x_i(t_1, t_2, \ldots, t_R)$ where
- $i = 1, 2 \ldots n$ is the task index
- $v = 1, 2, \ldots R$ is the index of the resource
- $t_v = 0, 1, 2, \ldots UB$ is the time variable associated to the resource $v$
- $UB$ is upper bound on $C_{\max}$
- $x_i(t_1, t_2, \ldots, t_R) = 1$ iff tasks $T_1, T_2, \ldots, T_i$ can be assigned to the resource such that $P_v$ is occupied during the time interval $\langle 0, t_v \rangle$; $v = 1, 2, \ldots R$”
Pozor na čtení: $x_i$ je dosažitelnost (0/1 — „jde to?“), ne žádná „cena“ stavu. Tabulka vrstvy $i$ má $(UB+1)^R$ buněk — pro $R = 2$ je to obyčejná 2D mřížka $(t_1, t_2)$ a přesně tu budeš u zkoušky kreslit.
Rekurence: OR přes stroje (slide 48)
Zkus sám: jak z vrstvy $x_{i-1}$ poznám, že $x_i(t_1, \ldots, t_R) = 1$? (Kam mohla jít úloha $T_i$?)
Úloha $T_i$ skončila na některém stroji $v$ — a před jejím přidáním byly zátěže stejné, jen $t_v$ bylo o $p_i$ menší. Tedy: $$x_i(t_1, \ldots, t_R) = \bigvee_{v=1}^{R} x_{i-1}(t_1, \ldots, t_v - p_i, \ldots, t_R),$$ kde člen s $t_v - p_i < 0$ je automaticky 0 (mimo tabulku). Pro $R = 2$: buňka je 1, pokud o $p_i$ vlevo nebo o $p_i$ dole byla ve vrstvě $i-1$ jednička.
Slide 48 (EN 1:1) — Dynamic Programming for $P \,||\, C_{\max}$ [Rothkopf]“Input: $R$, the number of parallel identical resources, $n$, the number of nonpreemptive tasks and their processing time $(p_1, p_2, \ldots, p_n)$.
Output: $n$-elements vectors $s$ and $z$ where $s_i$ is the start time and $z_i$ is the resource ID.”
for (t_1, t_2, ..., t_R) ∈ {1, 2, ... UB}^R do x_0(t_1, t_2, ..., t_R) := 0;
x_0(0, 0, ..., 0) := 1;
for i := 1 to n do // for all tasks
for (t_1, t_2, ..., t_R) ∈ {0, 1, 2, ... UB}^R do // in the whole space
x_i(t_1, t_2, ..., t_R) := OR_{v=1}^R x_{i-1}(t_1, t_2, ..., t_v - p_i, ... t_R);
// x_i() = 1 iff there existed
// x_{i-1}() = 1 ``smaller'' by p_i in any direction
end
end
C*_max = min_{x_n(t_1, t_2, ..., t_R)=1} { max_{v=1, 2, ... R} { t_v } };
Assign tasks T_n, T_{n-1}, ..., T_1 in the reverse direction;
“Time complexity is $\mathcal{O}(n \cdot UB^R)$.”
Čtení pseudokódu: inicializace = jediná jednička v počátku ($x_0(0,\ldots,0) = 1$ — „nic nepřiřazeno, stroje prázdné“), všude jinde 0. Hlavní smyčka jede po úlohách $i = 1 \ldots n$ a pokaždé přepočítá celou mřížku. Na konci se optimum přečte z poslední vrstvy a rozvrh zrekonstruuje odzadu (sekce níže).
Zkus sám (kontrola, která u zkoušky šetří chyby): kde ve vrstvě $i$ můžou jedničky vůbec ležet? (Sečti souřadnice.)
Prvních $i$ úloh představuje $P_i = \sum_{j \le i} p_j$ jednotek práce a všechna leží někde — takže každá jednička vrstvy $i$ splňuje $t_1 + \cdots + t_R = P_i$. Pro $R = 2$ leží všechny jedničky na antidiagonále $t_1 + t_2 = P_i$ (případně oříznuté hranicí $t_v \le UB$). Jednička mimo diagonálu = chyba v posouvání. Bonus: mřížka je symetrická podle výměny strojů ($t_1 \leftrightarrow t_2$) — identické stroje nerozlišíš.
Běh na příkladu slidu 49
Slide 49: $n = 3$, $R = 2$, $p = (2, 1, 2)$, $UB = 5$. Proklikej vrstvy — každý krok je jedna iterace hlavní smyčky (jedna úloha):
Zkus sám: z poslední vrstvy $x_3$ přečti $C^*_{max}$. Která buňka vyhrává?
$C^*_{max} = \min_{x_3 = 1} \max\{t_1, t_2\}$. Kandidáti: $(5,0) \to 5$, $(4,1) \to 4$, $(3,2) \to 3$, $(2,3) \to 3$, $(1,4) \to 4$, $(0,5) \to 5$. Minimum je $\mathbf{3}$ v buňkách $(3,2)$ a $(2,3)$ — geometricky buňky diagonály nejblíž ose souměrnosti $t_1 = t_2$ (nejvyrovnanější rozdělení práce; přesně intuice 2-Partition). Kontrola dolní mezí: $C_{max} \ge \lceil \frac{1}{R}\sum p_i \rceil = \lceil 2{,}5 \rceil = 3$ ✓ optimum.
Rekonstrukce rozvrhu: odzadu $T_n, \ldots, T_1$
Poslední řádek pseudokódu — “Assign tasks $T_n, T_{n-1}, \ldots, T_1$ in the reverse direction” — je u zkoušky druhá polovina práce: bez Ganttova diagramu nemáš rozvrh, jen číslo.
Zkus sám: stojíš v optimální buňce $(3,2)$ vrstvy $x_3$. Jak zjistíš, kde běžela úloha $T_3$ ($p_3 = 2$)?
Otoč rekurenci: jednička v $(3,2)$ vznikla z nějakého $v$ s $x_2(\ldots, t_v - p_3, \ldots) = 1$. Zkoušej stroje: $v = 1$: $x_2(1, 2) = 1$ ✓ → $T_3$ běžela na $P_1$ a začala v $s_3 = t_1 - p_3 = 1$, tj. $z_3 = 1$, interval $\langle 1, 3\rangle$. Pokračuj ze stavu $(1,2)$ s úlohou $T_2$, atd. až k $T_1$ — skončit musíš v $(0,0)$. (Tady šlo i $v = 2$: $x_2(3,0) = 1$ — rozvrhů s $C_{max} = 3$ je víc, vyber si libovolnou cestu.)
Pseudopolynom — ale jen pro pevné $R$ (slide 50)
Zkus sám: $\mathcal{O}(n \cdot UB^R)$ vypadá jako polynom. Není to spor s NP-těžkostí $P2 \,||\, C_{max}$ (2-Partition, [L1.1])?
Není. Vstup kóduje číslo $UB$ binárně na $\log_2 UB$ bitech — $UB$ samotné je tedy v délce vstupu exponenciální. Algoritmus polynomiální v hodnotách čísel (ne v délce jejich zápisu) je pseudopolynomiální — přesně tohle smí u slabě (weakly) NP-těžkých problémů existovat, viz $\mathcal{O}(nW)$ knapsack [L7.1]. A pozor na druhý exponent: $UB^{\mathbf{R}}$ — polynomialita v $UB$ drží jen pro konstantní počet strojů.
Slide 50 (EN 1:1) — Complexity of $P \,||\, C_{\max}$ [Rothkopf]- “For polynomially bounded $R$, (i.e., $R = poly(n)$) the problem is strongly NP-hard.
- Can be shown by reduction from 3-partition problem with $C_{\max} = B$, $R = m$, $n = 3m$, $p_i = a_i$ (take care, in 3-partition the number 3 means number of items in the bin).
- Here, the Rothkopf algorithm is not pseudopolynomial, since its complexity is $\mathcal{O}(n \cdot UB^R) = \mathcal{O}(n \cdot UB^{poly(n)})$, which is equal to $\mathcal{O}(n \cdot UB^{n/3})$ for the instances reduced from 3-partition.
- “For any constant $R$, e.g., $R = 2$, the problem is weakly NP-hard
- Here, the Rothkopf algorithm is pseudopolynomial, since its complexity is $\mathcal{O}(n \cdot UB^2)$.
- It can not be used to solve the instance reduced from 3-partition, with arbitrary $m$. On the other hand, it can be used to solve the instances reduced from 2-partition problem, which is weakly NP-hard (take care, in 2-partition the number 2 means number of bins).”
Nebezpečné polopravdy kolem Rothkopfa- $x_i$ není „hodnota“, je to dosažitelnost. Do buňky nepíšeš nejlepší $C_{max}$, jen 0/1 („umím prvních $i$ úloh složit přesně na zátěže $(t_1, \ldots, t_R)$?“). Optimalizuje se až čtením poslední vrstvy: $C^*_{max} = \min \max_v t_v$.
- $t_v - p_i < 0$ nebo $t_v > UB$ = mimo tabulku = 0. Stavy „přeteklé“ přes $UB$ zahodíš — a proto musí být $UB \ge C^*_{max}$, jinak v $x_n$ nezbude žádná jednička a odpověď si uřízneš. Bezpečná volba je vždy $UB = \sum_i p_i$ (vše na jednom stroji); těsnější $UB$ z heuristiky (list scheduling [L5.12]) = menší tabulka.
- „Pseudopolynomiální“ platí jen pro konstantní $R$ (slide 50): pro $R = poly(n)$ je $P \,||\, C_{max}$ silně NP-hard (redukce z 3-partition) a $UB^R$ exploduje exponenciálně. Žádný pseudopolynomiální algoritmus tam (pokud P≠NP) neexistuje.
- Rothkopf = nezávislé nepreemptivní úlohy. S preempcí je to triviální McNaughton [L5.4] ($\mathcal{O}(n)$, žádné DP!); s precedencemi M&C [L5.10] (pmtn) nebo list scheduling [L5.12] (bez pmtn). Klíč k volbě metody = tahák [L5.14]; u zkoušky navíc obvykle stojí v zadání „[Rothkopf]“ přímo v nadpisu.
Key takeaways — L5.11- Stav: $x_i(t_1, \ldots, t_R) = 1$ ⟺ úlohy $T_1, \ldots, T_i$ lze rozmístit tak, že $P_v$ je obsazen přesně $\langle 0, t_v\rangle$. Stačí to, protože u $P\,||\,C_{max}$ se na stroji lepí úlohy beze mezer od 0 a záleží jen na zátěžích.
- Rekurence: $x_i(t_1,\ldots,t_R) = \bigvee_{v=1}^R x_{i-1}(\ldots, t_v - p_i, \ldots)$; init $x_0(0,\ldots,0) = 1$; záporné indexy a $t_v > UB$ jsou 0. Kontrola pro $R=2$: jedničky vrstvy $i$ leží na antidiagonále $t_1 + t_2 = \sum_{j\le i} p_j$ (oříznuté $UB$) a mřížka je symetrická.
- Čtení a rekonstrukce: $C^*_{max} = \min_{x_n = 1} \max_v t_v$ (u $R=2$ buňky diagonály nejblíž $t_1 = t_2$); rozvrh odzadu $T_n, \ldots, T_1$ — najdi $v$ s $x_{i-1}(\ldots, t_v - p_i, \ldots) = 1$, zapiš $s_i = t_v - p_i$, $z_i = v$, sniž $t_v$; skončíš v $(0,\ldots,0)$. Pak nakresli Gantt.
- Složitost $\mathcal{O}(n \cdot UB^R)$: pseudopolynomiální pro konstantní $R$ (slabá NP-těžkost, 2-Partition [L1.1]); pro $R = poly(n)$ silně NP-hard (3-partition) a DP nepomůže. $UB \ge C^*_{max}$ nutné, $UB = \sum p_i$ vždy bezpečné.
- Volba metody (tahák [L5.14]): $P\,||\,C_{max}$, malé $R$, jen $p_i$ = Rothkopf DP; pmtn = McNaughton [L5.4]; prec = list scheduling [L5.12] / M&C [L5.10].
“Scheduling on Parallel Identical Resources [Rothkopf]
Solve the following instance $P \,||\, C_{max}$ by dynamic programming. Record the main variables for each iteration of the main loop. Draw the Gantt chart.
- processing time $p = (2, 2, 1, 2)$
- $R = 2$, two parallel identical resources
- $UB$, upper bound $C_{max}$, is equal to 5”
a) Co je v zadání?
Čtyři nepreemptivní nezávislé úlohy, dva identické stroje, minimalizovat makespan — a explicitní pokyn použít Rothkopfovo DP. Odevzdat máš tři věci: záznam hlavních proměnných po každé iteraci (= vrstvy $x_i$ — mřížka nebo výčet jedniček), přečtené $C^*_{max}$ a Gantt zrekonstruovaného rozvrhu. $UB = 5$ je dané, tabulka je $6 \times 6$.
b) Co k tomu budeme potřebovat?
- Tato lekce — stav, rekurence, čtení optima, zpětná rekonstrukce (takeaways).
- [L5.1] Grahamova notace — čtení $P \,||\, C_{max}$ a kreslení Ganttova diagramu.
- Kontrola výsledku dolní mezí $\max\{\max_i p_i, \lceil\frac{1}{R}\sum_i p_i\rceil\}$ — viz [L5.4].
c) Jak nad úlohou uvažovat?
Čistě mechanicky, iterace = úloha: vrstvu $x_{i-1}$ posuň o $p_i$ doprava (stroj 1) a o $p_i$ nahoru (stroj 2), sjednoť, ořízni na $t_v \le 5$. Po každé vrstvě zkontroluj antidiagonálu $t_1 + t_2 = P_i$ (zde $P_i = 2, 4, 5, 7$) a symetrii. Optimum hledej v $x_4$ co nejblíž ose $t_1 = t_2$. Při rekonstrukci jdi odzadu $T_4 \to T_1$ a každý krok ověř jedničkou v předchozí vrstvě; skončit musíš v $(0,0)$.
d) Úplné řešení (provedení DP a Gantt vlastní — vzorové řešení se ve zdrojích nedochovalo, přiznáno)
Záznam hlavních proměnných po iteracích (vypisuji jedničkové buňky $(t_1, t_2)$; vše ostatní 0):
| iterace $i$ | $p_i$ | $\{(t_1, t_2) : x_i(t_1,t_2) = 1\}$ | kontrola $t_1{+}t_2$ |
|---|---|---|---|
| 0 (init) | — | $(0,0)$ | 0 |
| 1 | 2 | $(2,0),\ (0,2)$ | 2 |
| 2 | 2 | $(4,0),\ (2,2),\ (0,4)$ | 4 |
| 3 | 1 | $(5,0),\ (4,1),\ (3,2),\ (2,3),\ (1,4),\ (0,5)$ | 5 |
| 4 | 2 | $(5,2),\ (4,3),\ (3,4),\ (2,5)$ | 7 |
Pozor v iteraci 4: kandidáti $(7,0), (6,1), (1,6), (0,7)$ přetékají $UB = 5$ → mimo tabulku, zahazují se. Totéž v mřížce (proklikej):
Čtení optima: $C^*_{max} = \min\{\max(5,2), \max(4,3), \max(3,4), \max(2,5)\} = \min\{5, 4, 4, 5\} = \mathbf{4}$, v buňkách $(4,3)$ a $(3,4)$. Kontrola dolní mezí: $\lceil\frac{2+2+1+2}{2}\rceil = \lceil 3{,}5\rceil = 4$ ✓ — DP našlo optimum (a líp to nejde, $C_{max}$ je při celočíselných $p_i$ celé číslo).
Rekonstrukce odzadu z $(4,3)$:
- $T_4$ ($p_4 = 2$): $v = 1$? $x_3(2, 3) = 1$ ✓ → $s_4 = 4 - 2 = 2$, $z_4 = 1$, tj. $T_4$ na $P_1\,\langle 2,4\rangle$; nový stav $(2,3)$.
- $T_3$ ($p_3 = 1$): $v = 1$? $x_2(1,3) = 0$ ✗. $v = 2$? $x_2(2, 2) = 1$ ✓ → $s_3 = 3 - 1 = 2$, $z_3 = 2$, tj. $T_3$ na $P_2\,\langle 2,3\rangle$; stav $(2,2)$.
- $T_2$ ($p_2 = 2$): $v = 1$? $x_1(0,2) = 1$ ✓ → $s_2 = 0$, $z_2 = 1$, tj. $T_2$ na $P_1\,\langle 0,2\rangle$; stav $(0,2)$.
- $T_1$ ($p_1 = 2$): $v = 2$? $x_0(0,0) = 1$ ✓ → $s_1 = 0$, $z_1 = 2$, tj. $T_1$ na $P_2\,\langle 0,2\rangle$; stav $(0,0)$ — konec ✓.
Výstupní vektory: $s = (0, 0, 2, 2)$, $z = (2, 1, 2, 1)$. (Rozvrh není jednoznačný — symetrická větev z $(3,4)$ jen prohodí stroje, a u $T_4$ šlo i $v = 2$ přes $x_3(4,1)$.)
Stroj $P_2$ zahálí $\langle 3,4\rangle$: $2 \cdot 4 - 7 = 1$ jednotka — nevyhnutelné, protože $\sum p_i = 7$ je liché (přesně ta „nerozměnitelná“ jednotka z 2-Partition pohledu).
“Rothkopf, solve P||Cmax by dynamic prog. p=(2,2,1,2), UB=7, R=2”
(i) Which reachable states appear in the layers $x_i$ that were cut off when $UB = 5$ (task T01)?
(ii) Do $C^*_{max}$ or the reconstructed schedule change? Why is any $UB \ge C^*_{max}$ equally correct?
(iii) Compare the table sizes for $UB = 5$ and $UB = 7$ and give the general rule for choosing $UB$.
a) Co je v zadání?
Tatáž instance jako T01 (studentský souhrn ji cvičí s $UB = 7$), jiná horní mez. Cíl: pochopit, co přesně $UB$ v algoritmu dělá — je to jen ořez tabulky, ne parametr ovlivňující optimum (dokud $UB \ge C^*_{max}$).
b) Co k tomu budeme potřebovat?
- Tato lekce — role $UB$ v rekurenci a ve složitosti (takeaways).
- Vrstvy $x_0$–$x_4$ z řešení T01 (výše).
c) Jak nad úlohou uvažovat?
Nepřepočítávej všechno znovu: vrstvy se liší jen tam, kde T01 něco ořízl o podmínku $t_v \le 5$. Projdi tabulku z T01 a najdi zahozené kandidáty. Pak si rozmysli: může buňka s $\max(t_1,t_2) > 4$ vyhrát čtení minima, když $(4,3)$ zůstává jedničkou?
d) Úplné řešení (vlastní — přiznáno)
(i) Vrstvy $x_0$–$x_3$ jsou stejné jako v T01 — žádný jejich stav nepřesáhl 5, takže ořez nic nedělal ($P_3 = 5 \le 5$). Rozdíl je až ve vrstvě $x_4$ (antidiagonála $t_1 + t_2 = 7$), kde s $UB = 7$ přežijí i dříve zahozené stavy: $$x_4: \ (7,0),\ (6,1),\ \underbrace{(5,2),\ (4,3),\ (3,4),\ (2,5)}_{\text{jako v T01}},\ (1,6),\ (0,7) .$$
(ii) Nic se nemění: nové stavy mají $\max(t_1,t_2) \in \{5, 6, 7\}$, takže čtení $C^*_{max} = \min_{x_4=1}\max_v t_v = 4$ vyhrávají pořád $(4,3)$ a $(3,4)$ a zpětná rekonstrukce z $(4,3)$ proběhne identicky ($s = (0,0,2,2)$, $z = (2,1,2,1)$, Gantt jako v T01). Obecně: stavy nad $C^*_{max}$ nikdy nevyhrají minimum — $UB$ jen určuje, kolik zbytečných stavů taháš s sebou. Každé $UB \ge C^*_{max}$ tedy dá stejný výsledek; menší $UB$ jen víc ořezává. (A $UB < C^*_{max}$ by smazalo všechny jedničky z $x_n$ — algoritmus by nevrátil nic, viz danger box.)
(iii) Vrstva má $(UB+1)^R$ buněk: $6^2 = 36$ pro $UB = 5$ vs. $8^2 = 64$ pro $UB = 7$ — celkem $n \cdot (UB+1)^R$, tj. $144$ vs. $256$ vyhodnocení rekurence. Obecné pravidlo: $UB = \sum_i p_i$ (zde právě $7$ — souhrn volí přesně tuhle bezpečnou mez) funguje vždy; cokoli těsnějšího z heuristiky (např. list scheduling [L5.12]) tabulku zmenší a výsledek nezmění, dokud $UB \ge C^*_{max}$. U zkoušky je $UB$ prostě v zadání — použij ho a nezdržuj se.