L5.0 Kapitola K5 — Rozvrhování (Slot 5) · [MUST] · FOTO checkpoint kapitoly

Rozvrhování přes toky ($P \mid \mathrm{pmtn}, r_j, \tilde{d}_j \mid$)

První „výpočetní“ lekce kapitoly K5 — a schválně taková, která ještě nepotřebuje žádný nový algoritmus: celou práci odvede max flow, který umíš z K4. Notaci $P \mid \mathrm{pmtn}, r_j, \tilde{d}_j \mid$ už přečteš z minulé lekce [L5.1] Grahamova notace α|β|γ: identické paralelní procesory (počet $R$ je v instanci), preempce povolena, release times a tvrdé deadliny — a prázdné $\gamma$ = rozhodovací problém: ptáme se jen, jestli přípustný rozvrh existuje. Přesně takhle padl na zkoušce 2023 (str. 3) s pokynem “Formulate as Maximum flow problem.”

Zadání problému (slide 5, 04_Flows — EN 1:1)

“Consider a $P \mid pmtn, r_j, \widetilde{d_j} \mid -$ problem - we have $n$ tasks which we want to assign to $R$ identical resources (processors). Each task has its own processing time $p_j$, release date $r_j$ and deadline $\widetilde{d_j}$. Preemption is allowed (including migration from one resource to another).”

Goal: “Assign all tasks to processors so that every processor will execute no more than one task at a moment and no task will be executed simultaneously on more than one processor. This can be solved as a Maximum flow problem.”

Pracovat budeme s ukázkovou instancí ze slidů 5–6 (3 paralelní identické procesory):

Krok 1: Rozsekej časovou osu body $r_j$ a $\tilde{d}_j$

Časovou osu nebudeme dělit na jednotkové slotíky — rozdělíme ji jen v bodech, kde se „něco děje“. Nejdřív se podívej na časová okna $\langle r_j, \tilde{d}_j \rangle$ všech čtyř úloh:

Krok 2: Postav třívrstvou síť

Síť má stejný vrstvený půdorys, jaký znáš z [L4.5] Modelování přiřazení jako tok (vrstvená síť): $s \to$ úlohy $\to$ intervaly $\to t$. Než ti prozradím kapacity, zkus si je rozmyslet sám:

A samozřejmě: hrana $T_j \to I_{x,y}$ v síti existuje jen tehdy, když úloha v daném intervalu smí běžet, tj. $\langle x, y\rangle \subseteq \langle r_j, \tilde{d}_j\rangle$. Celou stavbu si proklikej:

Nebezpečná polopravda: „prostřední hrany kapacitu nepotřebují“

Potřebují — a je to nejčastěji zapomenutá část formulace. Bez kapacity $y-x$ na hraně $T_j \to I_{x,y}$ by tok mohl poslat třeba 3 jednotky úlohy do intervalu délky 1 — dekódováno: úloha běží na třech procesorech současně, což obecné omezení „task on at most one resource at a moment“ zakazuje. Kapacita $p_j$ na zdrojové hraně ani $(y-x)R$ na stokové tohle neuhlídají. Druhá zapomínaná věc: hrany kreslit jen do intervalů uvnitř okna $\langle r_j, \tilde{d}_j\rangle$.

Krok 3: Pusť max flow a přečti odpověď

Kritérium feasibility

Přípustný preemptivní rozvrh existuje $\iff$ maximální tok má hodnotu $|f| = \sum_j p_j$, tj. všechny hrany ze zdroje jsou nasycené — každá úloha dostala celých svých $p_j$ jednotek práce. Stejné čtecí pravidlo jako u vrstvených přiřazovacích sítí v [L4.5]. Když $|f| < \sum_j p_j$, rozvrh neexistuje a minimální řez je certifikát úzkého hrdla [L4.4] — ukáže okno, do kterého se předepsaná práce nevejde.

Pozor: celý trik stojí a padá s pmtn

Tok rozhoduje feasibilitu preemptivní verze problému. Jakmile $\beta$ preempci nepovoluje, množstevní pohled se rozbije (úloha musí běžet vcelku — tok neumí říct „vcelku“) a problém tvrdne: už jednostrojové nepreemptivní $1 \mid r_j, \tilde{d}_j \mid C_{max}$ je silně NP-těžké a řeší se úplně jinak (Bratleyho branch & bound — lekce [L5.9]). Než začneš kreslit síť, zkontroluj v notaci, že tam pmtn opravdu je.

Krok 4: Z toku zpátky rozvrh (flow → schedule)

Formulací úloha na písemce obvykle končí — ale opravující na ručním řešení ze zkoušky 2023 červeně připsal „chybí flow → schedule“. Umět z toku vyrobit rozvrh tedy patří k plné odpovědi (a u ústní se na to ptají). Postup:

1. Přečti tok prostředních hran: $f(T_j \to I_{x,y})$ = kolik jednotek úlohy $T_j$ poběží uvnitř intervalu $\langle x, y\rangle$. Kirchhoff zaručuje, že se to na obou stranách sečte správně.
2. Každý interval vyřeš samostatně: uvnitř $I_{x,y}$ máš kousky úloh o celkové délce $\le (y-x)R$, každý kousek $\le y-x$. Takové kousky vždy jdou „nalít“ na $R$ procesorů tak, aby se žádná úloha nepřekrývala sama se sebou — kousky skládej za sebe a při přetečení konce intervalu zalom na další procesor (systematicky to dělá McNaughtonův algoritmus, lekce [L5.4]; kapacita $y-x$ na hraně zaručí, že zalomený kousek nekoliduje sám se sebou).
3. Slep intervaly za sebe a máš Gantt chart celého rozvrhu.

Co odevzdat u zkoušky

U zadání “Formulate as Maximum flow problem” odevzdej pět věcí (srovnej se čtyřmi věcmi z [L4.5] — přibyly intervaly):

1. Body a intervaly: seřazené sjednocení $\{r_j\} \cup \{\tilde{d}_j\}$ → intervaly $I_{x,y}$ (vypiš je).
2. Vrcholy a hrany: $s \to T_j \to I_{x,y} \to t$; prostřední hrany jen pro $\langle x,y\rangle \subseteq \langle r_j, \tilde{d}_j\rangle$.
3. Kapacity: $p_j$ / délka intervalu $y-x$ / $(y-x)\cdot R$; dolní meze 0.
4. Kritérium: feasibilní $\iff |f| = \sum_j p_j$ (nasycené zdrojové hrany).
5. Čtení výsledku: $f(T_j \to I_{x,y})$ = množství práce úlohy v intervalu; uvnitř intervalu rozlít na procesory (flow → schedule).

Key takeaways — L5.0

• Body z $\{r_j\} \cup \{\tilde{d}_j\}$ rozdělí časovou osu na intervaly (parametry dle [L5.1]) — uvnitř intervalu se množina běžet-smějících úloh nemění, takže díky pmtn stačí rozhodovat množství práce, ne přesné časy.
• Síť: $s \to$ úloha (kapacita $p_j$) $\to$ interval, kde úloha smí běžet, tj. $\langle x,y\rangle \subseteq \langle r_j,\tilde d_j\rangle$ (kapacita = délka $y-x$, úloha je sekvenční!) $\to t$ (kapacita délka $\cdot R$).
• Feasibilita = nasycení všech hran ze zdroje: $|f| = \sum_j p_j$ ([L4.4], [L4.5]); jinak rozvrh neexistuje a min řez je certifikát. Zlomkový tok nevadí — pmtn krájí úlohy libovolně.
• Flow → schedule: $f(T_j \to I_{x,y})$ = kolik úlohy běží v intervalu; uvnitř intervalu kousky nalít na $R$ procesorů (à la McNaughton [L5.4]) a intervaly slepit. Bez tohoto kroku je odpověď neúplná („chybí flow → schedule“).
• Funguje jen s pmtn — nepreemptivní varianty (např. $1|r_j,\tilde d_j|C_{max}$) jsou NP-těžké a tok je nevyřeší [L5.9].

T01 Multiprocessor Scheduling problem with preemption, release date and deadline (zkouška 2023) FOTO checkpoint zdroj: zkouška 2023, str. 3 / úloha 6 (zadání EN 1:1); řešení dle ručního zkouškového řešení, dopočet feasibility + Gantt vlastní (přiznáno)

Assignment (original, EN)

We have $n$ tasks which we want to assign to $R$ identical resources (processors). Each task has its own processing time $p_j$, release date $r_j$ and deadline $\tilde{d}_j$. Preemption is allowed (including migration from one resource to another). Every processor will execute no more than one task at a moment and no task will be executed simultaneously on more than one processor.

2 parallel identical resources:

	$T_1$	$T_2$	$T_3$	$T_4$	$T_5$
$p_j$	2.1	3.2	4.1	1.6	2
$r_j$	0	2	0	5	5
$\tilde{d}_j$	5	6	6	7	7

Formulate as Maximum flow problem.

a) Co je v zadání?

Feasibility problém $P2 \mid \mathrm{pmtn}, r_j, \tilde{d}_j \mid$ — pět úloh s okny $\langle r_j, \tilde{d}_j\rangle$, dva identické procesory, preempce s migrací povolena. Nechtějí po tobě rozvrh hledat ručně — chtějí formulaci jako max flow: síť + kapacity + kritérium (+ čtení výsledku).

b) Co k tomu budeme potřebovat?

• Tato lekce — konstrukce intervalů a sítě, kritérium feasibility, flow → schedule.
• [L5.1] Grahamova notace α|β|γ — čtení notace, $\tilde{d}_j$ vs. $d_j$, prázdné $\gamma$.
• [L4.4] Řez a věta max-flow/min-cut — proč $|f| \le \sum p_j$ a řez jako certifikát.
• [L4.5] Modelování přiřazení jako tok — vrstvený vzor a čtení nasycení.

c) Jak nad úlohou uvažovat?

Drž se čtyř kroků lekce: (1) vypiš seřazené sjednocení $\{r_j\}\cup\{\tilde d_j\}$ a z něj intervaly; (2) nakresli tři vrstvy a rozmysli, do kterých intervalů má každá úloha hranu (okno $\langle r_j,\tilde d_j\rangle$ musí interval pokrývat celý); (3) přiřaď tři druhy kapacit — u prostředních hran si vzpomeň na sekvenčnost úloh; (4) napiš kritérium nasycení a větu o čtení rozvrhu z toku. Pozor, $R = 2$, ne 3 jako v ukázce ze slidů.

d) Úplné řešení

(Postup 1:1 podle ručního zkouškového řešení; značení intervalů dtto.)

1. Intervaly. $R = 2$. Důležité body určující intervaly: $\mathrm{set}(M[r_j; \tilde d_j]) = \{0, 2, 5, 6, 7\}$. Intervaly: $I_{0,2} = \langle 0;2)$, $I_{2,5} = \langle 2;5)$, $I_{5,6} = \langle 5;6)$, $I_{6,7} = \langle 6;7\rangle$ — délky $2, 3, 1, 1$.

2. Síť. Vrstvy $S \to$ úlohy $\{1,\dots,5\} \to$ intervaly $\to T$. Hrany úloha → interval jen tam, kde $\langle x,y\rangle \subseteq \langle r_j, \tilde d_j\rangle$: $T_1\,(0..5) \to I_{0,2}, I_{2,5}$; $T_2\,(2..6) \to I_{2,5}, I_{5,6}$; $T_3\,(0..6) \to I_{0,2}, I_{2,5}, I_{5,6}$; $T_4, T_5\,(5..7) \to I_{5,6}, I_{6,7}$.

3. Kapacity. Dolní meze všude $LB = 0$. $S \to$ úloha: $UB = p_j$ (2.1, 3.2, 4.1, 1.6, 2). Úloha → interval: $UB$ = délka intervalu. Interval → $T$: $UB$ = délka $\cdot R$, tedy $4, 6, 2, 2$ (ruční řešení: „upper bounds: množství volných jednotek v intervalu → délka $I \cdot R$“).

4. Kritérium. Spočti max flow. Přípustný rozvrh existuje $\iff |f| = \sum_j p_j = 2.1+3.2+4.1+1.6+2 = 13$, tj. všechny hrany ze zdroje nasycené. Čtení: $f(T_j \to I_{x,y})$ = kolik jednotek úlohy $T_j$ poběží v intervalu $\langle x,y\rangle$; uvnitř intervalu kousky rozliješ na 2 procesory (flow → schedule — bez této věty opravující strhával, viz červená poznámka na ručním řešení).

5. Dopočet feasibility + Gantt (vlastní rozšíření — ruční řešení končí formulací). Max flow hodnoty 13 skutečně dosahuje, např.:

$f$	$I_{0,2}$	$I_{2,5}$	$I_{5,6}$	$I_{6,7}$	$\sum$
$T_1$	2	0.1	—	—	2.1 ✓
$T_2$	—	3	0.2	—	3.2 ✓
$T_3$	2	2.1	0	—	4.1 ✓
$T_4$	—	—	0.8	0.8	1.6 ✓
$T_5$	—	—	1	1	2 ✓
do $T$ (kap.)	4 (4)	5.2 (6)	2 (2)	1.8 (2)	13

Všechny prostřední hrany respektují kapacitu = délku intervalu (max 2, 3, 1, 1) a zdrojové hrany jsou nasycené → rozvrh existuje. Rozlití uvnitř intervalů dá např. tento Gantt:

Kontrola: žádná úloha neběží na dvou procesorech naráz ($T_2$ končí na $P^1$ v čase 5 a na $P^2$ běží až $\langle 5; 5.2)$) a všechna okna jsou dodržena: $C_1 = 4.2 \le 5$, $C_2 = 5.2 \le 6$, $C_3 = 4.1 \le 6$, $C_4 = 6.8 \le 7$, $C_5 = 7 \le 7$.

FOTO checkpoint

Úlohu T01 vyřeš celou na papír (bez koukání do řešení): body → intervaly → síť se všemi kapacitami → kritérium → věta o flow → schedule. Pak pošli fotku — zkontroluju ti ji a vytknu chyby.

Příště začneme stavět hlavní příběh kapitoly: precedence a temporální omezení mezi úlohami a jejich graf — a nad nimi pak time-indexed ILP a celá rodina rozvrhovacích algoritmů, kterou na konci shrne referenční tabulka [L5.14].