NP-těžkost rozvrhování (redukce)
Celou kapitolou K5 se táhne jedna nevyslovená otázka: proč jsme na $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ vytáhli branch & bound [L5.9] a na $PS1\,|\,temp\,|\,C_{max}$ rovnou ILP se solverem [L5.3], místo nějakého chytrého polynomiálního algoritmu jako u Horna [L5.7] nebo McNaughtona [L5.4]? Tahle lekce dodává důkazy, že nic chytřejšího (pokud $P \ne NP$) neexistuje. Je to ústní téma („proč je $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ NP-těžký?“) — počítat tu skoro nebudeš, zato dvakrát stavět redukci.
Těžkost teče po šipce redukce
Zkus sám: z [L3.5] znáš důkaz NP-těžkosti TSP redukcí z hamiltonovské kružnice. Který problém se tam převáděl na který — a proč zrovna tímhle směrem?
Převáděl se známý těžký problém (HC) na náš problém (TSP): z každé instance HC se polynomiálně vyrobila instance TSP tak, že odpověď na TSP dává odpověď na HC. Kdyby TSP uměl polynomiální algoritmus, uměl by ho i HC — spor. Šipka redukce tedy vede od těžkého k mému: „můj problém je aspoň tak těžký jako…“. Opačný směr (můj problém převedu na ILP) nedokazuje vůbec nic — ILP umí zakódovat i triviálně lehké problémy.
Přesně tenhle vzor dnes použijeme dvakrát za sebou — jednou s 3-PARTITION v roli „známého těžkého“ a podruhé s čerstvě dokázaným Bratleyho problémem:
$$\underbrace{\text{3-PARTITION}}_{\text{silně NP-úplný}} \;\xrightarrow[\text{(slide 15)}]{\text{P-redukce}}\; \underbrace{1\,|\,r_j, \tilde{d}_j\,|\,C_{max}}_{\text{silně NP-těžký}} \;\xrightarrow[\text{(slide 75)}]{\text{P-redukce}}\; \underbrace{PS1\,|\,temp\,|\,C_{max}}_{\text{NP-těžký}}$$
Pojmy NP-úplnost a polynomiální redukce máš z [L3.3], silnou NP-těžkost (= těžké i při malých číslech v unárním kódování → žádný pseudopolynomiální algoritmus) z [L3.5] — tady je jen používáme.
3-PARTITION: rozdej čísla do košů po třech (slide 14)
Slide 14 (EN 1:1) — $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ Problem is strongly NP-hard“We prove it by reduction from the 3-Partition problem, which is strongly NP-complete.
3-Partition decision problem instance, $I_{3P} = (A, B)$, is given as:
- a multiset $A$ of $3m$ integers $a_1, a_2, \ldots, a_{3m}$ (sizes of items), and
- a positive integer $B$ (size of bins) such that $\forall i \in \{1, 2, \ldots, 3m\} : \frac{B}{4} < a_i < \frac{B}{2}$ and $\sum_{i=1}^{3m} a_i = mB$.
The problem is to determine whether $A$ can be partitioned into $m$ disjoint subsets $A_1, A_2, \ldots, A_m$ such that, $\forall j \in \{1, 2, \ldots, m\} : \sum_{a_i \in A_j} a_i = B$.”
Zkus sám: v definici se nikde neříká, kolik prvků má každý koš $A_j$ mít. Přesto každý přípustný koš obsahuje přesně tři čísla. Proč?
Kvůli podmínce $\frac{B}{4} < a_i < \frac{B}{2}$: čtyři čísla dají dohromady víc než $4 \cdot \frac{B}{4} = B$, dvě čísla míň než $2 \cdot \frac{B}{2} = B$. Jediný počet, který může trefit součet přesně $B$, jsou tři. Slide 14 to říká doslova: “if we show that there is a subset $A_j$ which contains integers summing to $B$, then it must contain three integers. This follows from the assumption $\frac{B}{4} < a_i < \frac{B}{2}$ (try to sum-up 4 integers or 2 integers).” Tahle drobnost ponese půlku důkazu ekvivalence.
Zkus sám (oba příklady ze slidu 14): Example 1: $A = \{4, 5, 5, 5, 5, 6\}$, $m = 2$, $B = 15$ — najdi 3-partition. Example 2: $A = \{4, 4, 4, 6, 6, 6\}$, $m = 2$, $B = 15$ — proč řešení neexistuje?
Example 1: $3.75 < a_i < 7.5$ ✓ a $\sum a_i = 30 = 2 \cdot 15$ ✓. Řešení (slide 14): $A_1 = \{4, 5, 6\}$, $A_2 = \{5, 5, 5\}$ — obojí součet 15.
Example 2: trojice z čísel $\{4, 6\}$ mají jen čtyři možné součty: $4{+}4{+}4 = 12$, $4{+}4{+}6 = 14$, $4{+}6{+}6 = 16$, $6{+}6{+}6 = 18$. Patnáctka mezi nimi není → “No solution” (slide 14).
Důležité je slovo strongly: 3-PARTITION zůstává NP-úplný, i když jsou všechna čísla malá (polynomiálně omezená velikostí instance). Příbuzný 4-PARTITION ses už potkal v úloze s bankovkami [L1.8].
Redukce 3-PARTITION → 1 | rj, d̃j | Cmax (slide 15)
Zkus sám: máš jediný stroj a chceš ho přinutit, aby se choval jako $m$ oddělených košů kapacity přesně $B$. Jaké úlohy (s jakými $p_j, r_j, \tilde{d}_j$) na to potřebuješ přidat?
Ploty. Úloha s oknem $\langle r_j, \tilde{d}_j \rangle$ dlouhým přesně $p_j$ nemá žádnou vůli — je „přibitá“ na své místo. Když takových jednotkových plotů rozestavíš $m$ s rozestupem $B + 1$, rozsekají časovou osu na $m$ mezer délky přesně $B$ — a to jsou tvoje koše. Zbylé úlohy (jedna za každý prvek $a_i$, bez release a deadlinu) se do mezer musí naskládat.
Slide 15 (EN 1:1) — Reduction from 3-Partition to $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$“From the given instance of the 3-Partition problem $I_{3P} = (A, B)$, we build $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ scheduling problem instance $I_{SCH}$ comprised of $4m$ tasks $T_j = (p_j, r_j, \tilde{d}_j)$ as follows:
- $\forall j \in \{1, \ldots, m\} : T_j = (1,\ (B+1) \cdot (j-1),\ (B+1) \cdot (j-1) + 1)$. These are "additional/artificial" tasks used to separate the subsets.
- $\forall j \in \{m+1, \ldots, 4m\} : T_j = (a_i, 0, \infty),\ i = j - m$. Each of these tasks $T_j$ corresponds to the element $a_i$ of $I_{3P}$.
It is easy to prove that the $I_{3P} = (A, B)$ has a solution if and only if the optimal solution of the related $I_{SCH}$ has value of $C_{\max} = m \cdot (B+1)$.”
Prohlédni si konstrukci na datech Example 1 ($m = 2$, $B = 15$, takže ploty $T_1 = (1, 0, 1)$ a $T_2 = (1, 16, 17)$; prvkové úlohy $T_3, \ldots, T_8$ s $p = (4, 5, 5, 5, 5, 6)$):
Zkus sám: směr „⇒“ (3-partition existuje → rozvrh s $C_{max} = m(B+1)$ existuje) jsi právě viděl v Ganttu. Dokaž směr „⇐“: proč rozvrh s $C_{max} = m(B+1)$ vynucuje existenci 3-partition?
(rozepsání vlastní — slide 15 říká jen „it is easy to prove“)
1. Žádná díra. Celková práce je $\sum p_j = m \cdot 1 + \sum_i a_i = m + mB = m(B+1)$. Rozvrh s $C_{max} = m(B+1)$ na jednom stroji tedy nemá ani jednotku nečinnosti.
2. Ploty stojí na svém. Každý plot $T_j$ má okno dlouhé přesně $p_j = 1$, takže běží v $\langle (B+1)(j-1), (B+1)(j-1)+1 \rangle$ — jinde nesmí.
3. Mezery se plní přesně. Mezi ploty (a za posledním) zbývá $m$ mezer délky $B$. Prvkové úlohy jsou nepreemptivní, takže žádná nemůže plot „přeskočit“ rozpůlením — každá leží celá v jedné mezeře. Bez děr (krok 1) má obsah každé mezery součet přesně $B$.
4. Po třech. Z $\frac{B}{4} < a_i < \frac{B}{2}$ obsahuje každá mezera přesně tři prvky (viz try výše) — obsahy mezer jsou hledané $A_1, \ldots, A_m$. ∎
A teď pointa, kterou chce zkoušející slyšet u ústní celou: konstrukce $I_{SCH}$ je polynomiální (vyrobí $4m$ úloh, čísla jen sčítá a násobí) a zachovává odpověď ANO/NE. Kdyby $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ uměl polynomiální (nebo i jen pseudopolynomiální) algoritmus, vyřešil by přes tuhle redukci i 3-PARTITION — který je ale silně NP-úplný. Slide 13 to shrnuje (EN 1:1): “$1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ - NP-hard — NP-hardness proved by the pol. reduction from 3-Partition problem — for $p_j = 1$ there exists a polynomial algorithm.” Plné znění slidu 13 (které varianty $1\,|\,\cdot\,|\,C_{max}$ jsou easy) máš v [L5.9].
Redukce 1 | rj, d̃j | Cmax → PS1 | temp | Cmax (slide 75)
Druhý krok řetězu posílá těžkost dál: do project schedulingu s temporálními omezeními, jehož graf TC a sémantiku $s_i + l_{ij} \le s_j$ znáš z [L5.2]. Slide 74 (EN 1:1): “Using $PS1\,|\,temp\,|\,C_{max}$ we will model: $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$, scheduling on dedicated resources $PSm,1\,|\,temp\,|\,C_{max}$.”
Zkus sám: temporální omezení umí jen nerovnosti tvaru $s_i + l_{ij} \le s_j$ mezi dvojicemi úloh. Jak jimi zapíšeš $s_i \ge r_i$ a $s_i + p_i \le \tilde{d}_i$, které mluví o jediné úloze a absolutním čase?
Potřebuješ pevný bod na časové ose — dummy úlohu $T_0$ s $p_0 = 0$ a $s_0 = 0$. Pak:
- hrana $T_0 \xrightarrow{\,l_{0i} = r_i\,} T_i$: $\quad s_0 + r_i \le s_i \;\Leftrightarrow\; s_i \ge r_i$ (release),
- hrana $T_i \xrightarrow{\,l_{i0} = -(\tilde{d}_i - p_i)\,} T_0$: $\quad s_i - (\tilde{d}_i - p_i) \le s_0 \;\Leftrightarrow\; s_i + p_i \le \tilde{d}_i$ (deadline).
Záporná hrana „v protisměru“ jako horní mez — přesně trik z katalogu [L5.2]. A proč si můžeme dovolit předpokládat $s_0 = 0$? Všechny hrany $r_i \ge 0$ vynucují $s_i \ge s_0$, takže posunutím celého rozvrhu o $-s_0$ doleva zůstanou všechna (rozdílová) omezení v platnosti a $C_{max}$ se nezvětší — minimalizace kritéria tedy $T_0$ sama přitlačí na nulu.
Slide 75 (EN 1:1) — Reduction from $1\,|\,r_j, \widetilde{d}_j\,|\,C_{max}$ to $PS1\,|\,temp\,|\,C_{max}$“This polynomial reduction proves that $PS1\,|\,temp\,|\,C_{max}$ is NP-hard, since Bratley's problem is NP-hard.
Instance $1\,|\,r_j, \widetilde{d}_j\,|\,C_{max}$: $\;r = (r_1, r_2, \ldots, r_n)$, $\;p = (p_1, p_2, \ldots, p_n)$, $\;\widetilde{d} = (\widetilde{d}_1, \widetilde{d}_2, \ldots, \widetilde{d}_n)$ — P-reducible ⇒” (následuje obrázek grafu; níže překreslen dle textového popisu — přiznáno)
Zbytek instance $PS1\,|\,temp\,|\,C_{max}$ je beze změny: úlohy $T_1, \ldots, T_n$ se svými $p_i$ sdílejí jednu unární kapacitu (= jeden stroj, nesmí se překrývat — jako v $1\,|\,\ldots\,|$), kritérium zůstává $C_{max}$. Rozvrhy si odpovídají 1:1, takže optimum se zachová — a tím je NP-těžkost $PS1\,|\,temp\,|\,C_{max}$ dokázána. Proto v [L5.3] nebylo nic lepšího než time-indexed ILP: pro NP-těžký problém se solver + dobrý model čekat má.
Jen zmínka: $PSm,1\,|\,temp\,|\,C_{max} \to PS1\,|\,temp\,|\,C_{max}$ (slidy 76–78) — VYLOUČENO ze zkoušky 2026Stejná hra se hraje i o patro výš: rozvrhování na $m$ dedikovaných zdrojích se převede na jediný zdroj tak, že se rozvrh každého zdroje $P^j$ promítne do vlastního časového okna $\langle (j-1) \cdot UB,\ j \cdot UB \rangle$; původní temporální omezení se přepočtou na $l'_{ij} = l_{ij} + (a_j - a_i) \cdot UB$ a přidají se dummy $T_0$ (pevný počátek) a $T_{n+1}$ (sběr kritéria). Na zkoušce se objevila 31.05.2011 („Převod PSm1|temp|Cmax -> PS1|temp|Cmax, najdete splnitelny rozvrh“ — CZ přepis 1:1), ale pro termín 2026 je oficiálně mimo rozsah — víc než tento odstavec nepotřebuješ.
Nebezpečné polopravdy kolem NP-těžkosti- Směr redukce se nedá otočit. Dokazuješ-li těžkost problému $X$, převádíš známý těžký problém na $X$ (3-PARTITION → Bratley → $PS1\,|\,temp\,|$). „Můj problém umím zapsat jako ILP, a ILP je NP-těžké, tedy můj problém je NP-těžký“ je klasický nesmysl — na ILP převedeš i hledání maxima v poli.
- NP-těžký ≠ neřešitelný. Bratleyho B&B [L5.9], position-based ILP [L5.6b] i time-indexed ILP [L5.3] ty problémy řeší exaktně — jen bez polynomiální záruky.
- „Silně“ NP-těžký = ani pseudopolynomiální algoritmus (pokud $P \ne NP$), viz [L3.5]. Time-indexed ILP s $n \cdot UB$ proměnnými tomu neodporuje — exponenciální řešení ILP žádná polynomiálnost není. Kontrast: knapsack je NP-těžký jen „slabě“ a DP $O(nC)$ má [L7.1].
- Těžkost je o deadlinech $\tilde{d}_j$, ne o due dates $d_j$ (rozdíl [L5.1]): tvrdé okno $\langle r_j, \tilde{d}_j \rangle$ je to, co dělá z plotů ploty. A pozor na speciální případy: pro $p_j = 1$ je $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ polynomiální (slide 13) — NP-těžkost obecného problému nezakazuje lehké podtřídy.
Key takeaways — L5.13- Řetěz redukcí: 3-PARTITION (silně NP-úplný) → $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ (silně NP-těžký) → $PS1\,|\,temp\,|\,C_{max}$ (NP-těžký). Směr: známý těžký problém → můj problém.
- 3-PARTITION → Bratley (slide 15): $m$ jednotkových „plotů“ $T_j = (1, (B+1)(j-1), (B+1)(j-1)+1)$ rozseká osu na koše délky $B$; prvky $a_i$ jako úlohy $(a_i, 0, \infty)$. 3-partition existuje ⟺ $C^*_{max} = m(B+1)$ (⇐: $\sum p_j = m(B+1)$ → žádná díra → koše přesně po $B$ → z $\frac{B}{4} < a_i < \frac{B}{2}$ tři prvky na koš).
- Bratley → $PS1\,|\,temp\,|$ (slide 75): přidej dummy $T_0$ ($p_0 = 0$, WLOG $s_0 = 0$); hrana $T_0 \to T_i$ s váhou $r_i$ dává $s_i \ge r_i$, hrana $T_i \to T_0$ s váhou $-(\tilde{d}_i - p_i)$ dává $s_i + p_i \le \tilde{d}_i$ — release/deadline jako temporální omezení [L5.2].
- Důsledky: žádný pseudopolynomiální algoritmus pro $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ (silná NP-těžkost); pro $PS1\,|\,temp\,|\,C_{max}$ je time-indexed ILP [L5.3] legitimní zbraň. Speciální případ $p_j = 1$ je polynomiální.
- $PSm,1\,|\,temp\,| \to PS1\,|\,temp\,|$ (projekce zdrojů do oken $\langle (j-1)UB, jUB \rangle$, $l'_{ij} = l_{ij} + (a_j - a_i) UB$) je pro zkoušku 2026 vyloučena — stačí vědět, že existuje.
„Převod 1|rj,dj|Cmax na PS1|temp|Cmax“
(EN) Consider the $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ instance with three tasks: $r = (2, 0, 3)$, $p = (2, 4, 1)$, $\tilde{d} = (8, 5, 10)$.
(i) Convert it to an equivalent $PS1\,|\,temp\,|\,C_{max}$ instance and draw the graph of temporal constraints.
(ii) Verify that the temporal constraints encode exactly the release times and deadlines.
(iii) Find an optimal schedule and its $C_{max}$.
(iv) What does this reduction prove, and why?
a) Co je v zadání?
Reprodukce redukce ze slidu 75 na malých číslech: postavit graf TC s dummy $T_0$, zkontrolovat sémantiku hran, rozvrhnout a říct teoretickou pointu. Typická ústní/teoretická otázka s malým výpočtem.
b) Co k tomu budeme potřebovat?
- Tato lekce — vzorec hran $r_i$ / $-(\tilde{d}_i - p_i)$ (takeaways).
- [L5.2] Precedence a temporální omezení; graf TC — sémantika $s_i + l_{ij} \le s_j$, záporné hrany jako horní meze.
- [L5.9] Bratleyho algoritmus — co je Bratleyho problém a že je NP-těžký.
c) Jak nad úlohou uvažovat?
Za každou úlohu $T_i$ jdou do grafu přesně dvě hrany od/k $T_0$ — dopředná s váhou $r_i$, zpětná s váhou $-(\tilde{d}_i - p_i)$. Dosaď a u každé hrany si nahlas přelož nerovnost $s_i + l_{ij} \le s_j$. U rozvrhu si spočti okna startů $[r_i, \tilde{d}_i - p_i]$ a všimni si, která úloha skoro nemá vůli. U (iv) si vybav směr šipky redukce.
d) Úplné řešení (vlastní — přiznáno)
(i) Přidáme $T_0$ s $p_0 = 0$ ($s_0 = 0$). Hrany: $T_0 \xrightarrow{r_i} T_i$ a $T_i \xrightarrow{-(\tilde{d}_i - p_i)} T_0$, tedy zpětné váhy $-(8-2) = -6$, $-(5-4) = -1$, $-(10-1) = -9$:
(ii) Překlad přes $s_i + l_{ij} \le s_j$ (a $s_0 = 0$):
| hrana | nerovnost | význam |
|---|---|---|
| $T_0 \to T_1$, $l = 2$ | $s_1 \ge 2$ | $s_1 \ge r_1$ |
| $T_1 \to T_0$, $l = -6$ | $s_1 \le 6$ | $s_1 + 2 \le 8 = \tilde{d}_1$ |
| $T_0 \to T_2$, $l = 0$ | $s_2 \ge 0$ | $s_2 \ge r_2$ |
| $T_2 \to T_0$, $l = -1$ | $s_2 \le 1$ | $s_2 + 4 \le 5 = \tilde{d}_2$ |
| $T_0 \to T_3$, $l = 3$ | $s_3 \ge 3$ | $s_3 \ge r_3$ |
| $T_3 \to T_0$, $l = -9$ | $s_3 \le 9$ | $s_3 + 1 \le 10 = \tilde{d}_3$ |
Okna startů: $s_1 \in [2, 6]$, $s_2 \in [0, 1]$, $s_3 \in [3, 9]$ — $T_2$ skoro nemá vůli, musí začít hned.
(iii) $T_2$ začne v 0 (jinak nestihne deadline 5), pak $T_1$, pak $T_3$: $s = (4, 0, 6)$, vše v oknech, bez překryvu:
$C_{max} = 7 = \sum p_i$ a stroj jede od 0 bez díry → optimum.
(iv) Redukce je polynomiální ($n$ úloh → graf s $n + 1$ uzly a $2n$ hranami, váhy jen dosazené vstupy) a rozvrhy obou instancí si odpovídají 1:1 včetně $C_{max}$. Protože Bratleyho problém $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ je (silně) NP-těžký (redukcí z 3-PARTITION), je $PS1\,|\,temp\,|\,C_{max}$ NP-těžký — slide 75: “This polynomial reduction proves that $PS1\,|\,temp\,|\,C_{max}$ is NP-hard, since Bratley's problem is NP-hard.”
Prove that $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ is strongly NP-hard.
(i) State the 3-Partition decision problem.
(ii) Describe the polynomial reduction (construction of the scheduling instance $I_{SCH}$).
(iii) Prove: $I_{3P}$ has a solution $\iff$ the optimum of $I_{SCH}$ equals $m \cdot (B+1)$.
(iv) Apply the reduction to Example 2 from the lecture: $A = \{4, 4, 4, 6, 6, 6\}$, $m = 2$, $B = 15$. What is the optimal $C_{max}$ of the resulting $I_{SCH}$?
a) Co je v zadání?
Kompletní důkazová otázka — přesně to, co OSNOVA eviduje jako ústní téma „proč je $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$ NP-těžký“. Části (i)–(iii) jsou reprodukce slidů 14–15, část (iv) je kontrola, že redukci umíš i spustit na instanci bez řešení.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice 3-PARTITION, konstrukce plotů, důkaz ⇐ (takeaways).
- [L3.5] TSP je silně NP-těžký — co znamená „silně“ a proč zabíjí pseudopolynomiální algoritmy.
- [L5.1] Grahamova notace — čtení $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$, rozdíl $d_j$ vs. $\tilde{d}_j$.
c) Jak nad úlohou uvažovat?
Struktura důkazu redukcí má vždy čtyři věty: odkud redukuju (silně NP-úplný 3-PARTITION), jak stavím instanci (ploty + prvkové úlohy), proč se odpověď zachová (oba směry ekvivalence!) a proč je převod polynomiální. U (iv) napřed rozhodni 3-partition otázku (try v lekci) a pak přemýšlej, co nejlepšího se do košů naskládat dá, když se trefit nejde.
d) Úplné řešení (rozepsání ⇐ a část (iv) vlastní — přiznáno)
(i) Slide 14 (EN 1:1): instance $I_{3P} = (A, B)$ je multiset $A$ o $3m$ celých číslech $a_1, \ldots, a_{3m}$ a kladné celé $B$ s $\frac{B}{4} < a_i < \frac{B}{2}$ a $\sum a_i = mB$; otázka zní, zda lze $A$ rozdělit do $m$ disjunktních podmnožin $A_1, \ldots, A_m$ se součtem každé přesně $B$. Problém je silně NP-úplný; z $\frac{B}{4} < a_i < \frac{B}{2}$ plyne, že každá $A_j$ má přesně 3 prvky.
(ii) Konstrukce $I_{SCH}$ o $4m$ úlohách (slide 15): ploty $T_j = (1, (B+1)(j-1), (B+1)(j-1)+1)$ pro $j \le m$, prvkové úlohy $T_j = (a_i, 0, \infty)$, $i = j - m$, pro $j > m$. Převod je zjevně polynomiální (i v unárním kódování — čísla se nezvětšují víc než násobením $m(B+1) \le$ velikost vstupu v unárce), proto přenáší silnou NP-těžkost.
(iii) ⇒: z 3-partition $A_1, \ldots, A_m$ poskládám rozvrh: plot $T_j$ do jeho okna, trojici $A_j$ do mezery $\langle (B+1)(j-1)+1,\ (B+1)j \rangle$ — vše bez díry, $C_{max} = m(B+1)$. (Ganttův diagram pro Example 1 je v lekci.) ⇐: práce celkem $\sum p_j = m + mB = m(B+1)$, takže rozvrh s $C_{max} = m(B+1)$ nemá nečinnost; ploty jsou okny přibité na svá místa; nepreemptivní prvková úloha nemůže plot překrýt, leží tedy celá v jedné mezeře; mezery mají délku $B$ a bez děr se plní přesně na $B$; podle (i) po třech prvcích → rozklad $A_1, \ldots, A_m$ existuje. ∎
(iv) $I_{SCH}$: ploty $T_1 = (1, 0, 1)$, $T_2 = (1, 16, 17)$; prvkové úlohy $T_3, \ldots, T_8$ s $p = (4, 4, 4, 6, 6, 6)$, $r = 0$, $\tilde{d} = \infty$. Trojice mají součty jen $12, 14, 16, 18$ — 3-partition neexistuje, takže podle (iii) je $C^*_{max} > m(B+1) = 32$, tj. $C^*_{max} \ge 33$ (celá čísla). A 33 se dosáhne: do první mezery $4 + 4 + 6 = 14$ (jedna jednotka díry před plotem $T_2$), zbytek $4 + 6 + 6 = 16$ za druhý plot:
$C^*_{max} = 33$. Přesně takhle redukce „počítá“: optimum $= m(B+1)$ ⟺ ANO, optimum $> m(B+1)$ ⟺ NE.