Referenční tabulka: problém → algoritmus (tahák)
Poslední lekce kapitoly nic nového nevykládá — sbírá úrodu. U písemky bývá metoda obvykle napsaná přímo v zadání („[Rothkopf]“ v nadpisu, “Use Muntz&Coffman's algorithm…”), takže tahák je hlavně pojistka pro případ, kdy tam není, a kostra odpovědi pro ústní („čím se řeší … a proč zrovna tím?“). Všechny řádky tabulky jsou doslova ze souhrnných slidů přednášky; detaily algoritmů už znáš z lekcí, na které tabulka odkazuje.
Tři otázky, kterými tahák čteš
Zkus sám: dostaneš zápis $1\,|\,pmtn, r_j\,|\,L_{max}$. Na která tři pole zápisu se podíváš a v jakém pořadí, abys trefil metodu?
Přesně v pořadí polí Grahamovy notace [L5.1]:
- $\alpha$ — co mám za zdroje? Jeden stroj ($1$), paralelní identické ($P$), nebo project scheduling s temporálními omezeními ($PS$)? Tím se rozhoduje mezi třemi „patry“ tabulky.
- $\gamma$ — co minimalizuji? $C_{max}$, $\sum w_j C_j$, $L_{max}$, nebo nic (prázdné $\gamma$ = rozhodovací/feasibility problém)? Stejné $\beta$ u jiného kritéria = úplně jiný svět.
- $\beta$ — jaká mám pravidla? Hlavně: je povolená preempce ($pmtn$)? Jsou precedence ($prec$)? Jsou release timy $r_j$ a deadliny $\tilde{d}_j$? Každý z těchto přepínačů typicky přehodí easy ↔ NP-hard, nebo vymění algoritmus.
Pro $1\,|\,pmtn, r_j\,|\,L_{max}$: jeden stroj, kritérium $L_{max}$, s preempcí a release timy → Hornův algoritmus [L5.7].
Než tabulku ukážu celou, dvě kontrolní otázky na nejčastější zkouškové „chytáky“ — jestli je trefíš, tahák už vlastně umíš.
Zkus sám: na jednom stroji jsou $1\,||\,C_{max}$, $1\,|\,r_j\,|\,C_{max}$ i $1\,|\,\tilde{d}_j\,|\,C_{max}$ triviální (stačí správně seřadit). Co se stane, když se $r_j$ a $\tilde{d}_j$ potkají v jednom zápisu?
$1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ je silně NP-hard — kombinace oken $\langle r_j, \tilde{d}_j \rangle$ umí postavit „ploty“ a zakódovat 3-PARTITION, jak jsi viděl v [L5.13]. Řadicí pravidla (dle $r_j$, dle $\tilde{d}_j$ = EDF) fungují jen na každé omezení zvlášť; dohromady zbývá Bratleyho branch & bound [L5.9] nebo ILP [L5.6b]. Výjimka dle slidu 13: pro $p_j = 1$ polynomiální algoritmus existuje.
Zkus sám: $P\,|\,pmtn\,|\,C_{max}$ vs. $P2\,||\,C_{max}$ — jeden je easy a druhý NP-hard. Který je který a proč?
Easy je ten s preempcí: $P\,|\,pmtn\,|\,C_{max}$ řeší McNaughton v $\mathcal{O}(n)$ [L5.4] — optimum $C^*_{max} = \max\{\max_i p_i, \sum_i p_i / R\}$ se prostě „nalije“ wrap-around plněním. Bez preempce je už $P2\,||\,C_{max}$ NP-hard (slide 38: redukce z 2-PARTITION s prahem $\frac{1}{2}\sum p_i$, viz [L1.1]) — proto exaktně Rothkopfovo DP [L5.11], aproximačně LPT [L5.12]. Preempce tu mění svět: rozbíjet úlohy na kousky je to, co dělá problém spojitě „nalévatelným“.
Referenční tabulka (souhrnné slidy 13, 23, 27, 38 + PS)
Tučně je vždy metoda, kterou po tobě zkouška typicky chce odsimulovat. Sloupec těžkosti drží terminologii slidů (slidy 13, 23 a 38 píší „easy“/„NP-hard“; slide 27 pro $L_{max}$ rozlišuje „polynomiální“/„NP-hard“).
| Problém ($\alpha\,|\,\beta\,|\,\gamma$) | Těžkost | Metoda | Lekce | Poznámka |
|---|---|---|---|---|
| Jeden stroj — $C_{max}$ (slide 13) | ||||
| $1\,||\,C_{max}$, $\;1\,|\,prec\,|\,C_{max}$ | easy | libovolné (topologické) pořadí | [L5.1] | vždy $C_{max} = \sum p_j$ |
| $1\,|\,r_j\,|\,C_{max}$ | easy | řazení dle neklesajícího $r_j$ | [L5.9] | nejmenší $r_j$ první |
| $1\,|\,\tilde{d}_j\,|\,C_{max}$ | easy | EDF (řazení dle neklesajícího $\tilde{d}_j$) | [L5.9] | přípustný rozvrh nemusí existovat |
| $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ | silně NP-hard | Bratley B&B; position-based ILP | [L5.9], [L5.6b] | 3-PARTITION [L5.13]; pro $p_j = 1$ polynomiální |
| Jeden stroj — $\sum C_j$, $\sum w_j C_j$ (slide 23) | ||||
| $1\,||\,\sum C_j$, $\;1\,||\,\sum w_j C_j$ | easy | SPT / weighted SPT (neklesající $p_j / w_j$) | [L5.6a] | jen třídění |
| $1\,|\,prec\,|\,\sum w_j C_j$ | NP-hard | relative-order ILP + B&B s LP relaxací | [L5.6a], [L5.6b] | $x_{ij}$ = „$T_i$ před $T_j$“; pozor na $C_j = \sum_i p_i x_{ij}$ |
| Jeden stroj — $L_{max}$ (slide 27) | ||||
| $1\,||\,L_{max}$ | polynomiální | EDD (earliest due date first) | [L5.7] | optimalita swap argumentem |
| $1\,|\,r_j\,|\,L_{max}$ | NP-hard | — (bez preempce nic polynomiálního) | [L5.7] | preempce je tu klíč k easy |
| $1\,|\,pmtn, r_j\,|\,L_{max}$ | polynomiální | Horn (iterované EDD) | [L5.7] | preempce jen v release timech |
| $1\,|\,pmtn, r_j, d_j{=}\tilde{d}_j\,|\,L_{max}$ | polynomiální | týž Horn — říká se mu EDF | [L5.7] | $L_{max} \le 0$ ⟺ schedulovatelné |
| $1\,|\,pmtn, prec, r_j, d_j{=}\tilde{d}_j\,|\,L_{max}$ | polynomiální | Chetto-Silly-Bouchentouf → EDF | [L5.8] | $r'$ dopředně, $\tilde{d}'$ zpětně, pak nezávislé úlohy |
| Paralelní identické stroje — $C_{max}$ (slide 38) | ||||
| $P\,|\,pmtn\,|\,C_{max}$ | easy | McNaughton, $\mathcal{O}(n)$ | [L5.4] | $C^* = \max\{\max p_i, \textstyle\sum p_i / R\}$, wrap-around |
| $P\,|\,pmtn, r_j, \tilde{d}_j\,|\,-$ | easy | max flow (rozhodovací verze) | [L5.0] | intervaly z $\{r_j\} \cup \{\tilde{d}_j\}$; feasibilita = nasycený zdroj |
| $P\,||\,C_{max}$ (NP-hard už $P2\,||\,C_{max}$) | NP-hard | exaktně Rothkopf DP; aproximačně LPT | [L5.11], [L5.12] | 2-PARTITION [L1.1]; DP $\mathcal{O}(n \cdot UB^R)$; $r_{LPT} = \frac{4}{3} - \frac{1}{3R}$ |
| $P\,|\,prec\,|\,C_{max}$ | NP-hard | list scheduling | [L5.12] | faktor $r_{LS} = 2 - \frac{1}{R}$; pozor na anomálie |
| $P\,|\,pmtn, prec\,|\,C_{max}$ | NP-hard | Muntz&Coffman (level algoritmus) | [L5.10] | faktor $r_{MC} = 2 - \frac{2}{R}$; exaktní pro $P2$ a stromy |
| Project scheduling — temporální omezení (slidy 59–75) | ||||
| $PS1\,|\,temp\,|\,C_{max}$ | NP-hard | time-indexed ILP (proměnné $x_{it}$) | [L5.3] | graf TC [L5.2]; NP-těžkost z Bratleyho [L5.13]; existuje i relative-order model (slidy 68–70, mimo náš kurz lekcí) |
A obecná zbraň přes všechny řádky: cokoli z toho umíš zapsat jako ILP a poslat do branch & boundu [L5.5] — exaktně, bez polynomiální záruky. To je legitimní odpověď přesně tam, kde tabulka říká NP-hard (a lenost tam, kde říká easy).
Tatáž tabulka jako dva rozhodovací stromy
Dvě nejhustší rodiny tabulky se dají odříkat jako posloupnost ano/ne otázek na $\beta$ — přesně tak je dobré je u ústní vyslovit.
Rychlý sebetest — poznáš metodu?
Zápisy níže jsou skutečné zkouškové problémy z lekcí této kapitoly. Odpověz dřív, než rozklikneš.
Zkus sám: (a) $P\,|\,pmtn, prec\,|\,C_{max}$ (zkouška 02.06.2021, doloženo i 1. 6. 2026) — (b) $PS1\,|\,temp\,|\,C_{max}$, “Formulate $PS1\,|temp|\,C_{max}$ problem as a time-indexed ILP.” (zkouška 25. 5. 2026)?
Zkus sám: (a) $P\,|\,pmtn, r_j, \tilde{d}_j\,|\,-$ , “does a feasible schedule exist?” (zkouška 2023) — (b) $1\,|\,pmtn, r_j\,|\,L_{max}$?
Zkus sám: (a) $P\,||\,C_{max}$, $R = 2$, zadány jen processing timy, “[Rothkopf]” — (b) $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$, malá instance se stromem řešení?
Nebezpečné záměny v tabulce- Horn potřebuje $pmtn$. $1\,|\,r_j\,|\,L_{max}$ bez preempce je NP-hard (slide 27) — neexistuje „Horn bez preempce“. Stejně tak McNaughton: bez $pmtn$ je už $P2\,||\,C_{max}$ NP-hard.
- Aproximační ≠ exaktní. LS ($2 - \frac{1}{R}$), LPT ($\frac{4}{3} - \frac{1}{3R}$) a M&C ($2 - \frac{2}{R}$) vracejí jen zaručeně-ne-moc-špatné rozvrhy; exaktní jsou EDD/Horn/CSB/McNaughton (polynomiální problémy) a Rothkopf/Bratley/ILP+B&B (NP-hard problémy). M&C je exaktní jen pro $P2$ a stromové precedence.
- Toky [L5.0] nic neminimalizují. Řeší jen feasibilitu (prázdné $\gamma$) a jen s $pmtn$ — tok smí úlohu libovolně porcovat mezi intervaly.
- $L_{max}$ implikuje due daty $d_j$, i když v $\beta$ nejsou vypsané (slide 27) — a nezaměň $d_j$ (měkké, měří se zpoždění) s $\tilde{d}_j$ (tvrdé deadliny, rozhodují přípustnost) [L5.1].
- „NP-hard“ v tabulce neznamená „neřešitelné“, znamená „sáhni po B&B / DP / ILP a počítej s exponenciálou“ — a obráceně: na easy řádek u zkoušky nevytahuj ILP, chtějí třídicí pravidlo a zdůvodnění.
Key takeaways — L5.14- Čtení klíče: $\alpha$ (1 / P / PS) → $\gamma$ ($C_{max}$ / $\sum w_j C_j$ / $L_{max}$ / nic = feasibilita) → $\beta$ ($pmtn$? $prec$? $r_j, \tilde{d}_j$?). V zadání zkoušky obvykle stojí, jaký algoritmus chtějí — tahák je pojistka a kostra ústní odpovědi.
- KLÍČ (problém → algoritmus): $P\,||\,C_{max}$, $R = 2$, jen processing timy = Rothkopf DP [L5.11]; $P\,|\,prec\,|\,C_{max}$ = list scheduling [L5.12]; $P\,|\,pmtn, prec\,|\,C_{max}$ = Muntz&Coffman [L5.10]; $P\,|\,pmtn\,|\,C_{max}$ = McNaughton [L5.4]; $1\,|\,pmtn, r_j\,|\,L_{max}$ = Horn [L5.7]; $1\,|\,pmtn, prec, r_j, d_j\,|\,L_{max}$ = CSB [L5.8]; $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ = Bratley [L5.9]; $PS1\,|\,temp\,|\,C_{max}$ = time-indexed ILP [L5.3]; $P\,|\,pmtn, r_j, \tilde{d}_j\,|\,-$ feasibilita = toky [L5.0].
- Easy řádky = třídění: $1\,||\,C_{max}$ libovolně, $1\,|\,r_j\,|$ dle $r_j$, $1\,|\,\tilde{d}_j\,|$ EDF, $1\,||\,L_{max}$ EDD, $1\,||\,\sum w_j C_j$ weighted SPT ($p_j/w_j$). NP-hard řádky = B&B / DP / ILP ([L5.5], [L5.6a]/[L5.6b]); aproximace LS/LPT/M&C s faktory $2-\frac1R$ / $\frac43-\frac1{3R}$ / $2-\frac2R$.
- Přepínače těžkosti: $pmtn$ dělá z $P\,||\,C_{max}$ a $1\,|\,r_j\,|\,L_{max}$ polynomiální problémy; kombinace $r_j + \tilde{d}_j$ na jednom stroji bez preempce dělá silně NP-hard [L5.13]. Celá tabulka: #tab.
Tím je kapitola K5 u konce. Pokračuje Slot 6: CSP a hranová konzistence — poslední nová technika před zkouškou.