Bratleyho algoritmus (1|r_j,d̃_j|Cmax, B&B)
V [L5.7] a [L5.8] dělala preempce těžké problémy lehkými. Dnes preempci zakážeme: úloha, kterou jednou pustíš, musí doběhnout vcelku. Na jednom stroji s release times $r_j$ a tvrdými deadliny $\tilde{d}_j$ (vlnka = deadline, ne due date — [L5.1] Grahamova notace) minimalizujeme makespan $C_{max}$.
Problém: každý parametr zvlášť easy, dohromady NP-hard
Slide 13 (EN 1:1) — Scheduling on One Resource — Minimizing Makespan- “$1\,|\,r_j\,|\,C_{max}$ - easy — the tasks are processed in a non-descending order of $r_j$ ($T_j$ with the lowest $r_j$ first)
- $1\,|\,\tilde{d}_j\,|\,C_{max}$ - easy — the tasks are processed in a non-descending order of $\tilde{d}_j$ — can be solved by EDF - Earliest Deadline First — the feasible schedule doesn't have to exist
- $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”
Zkus sám: samotná $r_j$ vyřeší třídění podle release, samotná $\tilde{d}_j$ třídění podle deadlinu (EDF). Proč se ta dvě pravidla nedají „spojit“ a kombinace je najednou těžká?
Obě pravidla dávají protichůdné pokyny: release říká „vezmi, co už je k dispozici“, deadline říká „vezmi, co nejvíc spěchá“ — a bez preempce se špatná volba nedá opravit. Navíc se může vyplatit nechat stroj stát a počkat si na naléhavou úlohu (stejný jev jako u $1\,|\,r_j\,|\,L_{max}$ v [L5.7]). Formálně: silná NP-těžkost polynomiální redukcí z 3-Partition (slide 14; redukce a souvislost s $PS1|temp|C_{max}$ je téma lekce [L5.13]). Exaktně to tedy řešíme buď ILP — position-based model znáš z [L5.6b] — nebo kombinatoricky: branch & bound, jehož obecnou kostru (větvení, meze, incumbent) máš z [L5.5].
Větvení: strom pořadí úloh
U ILP jsme v [L5.5] větvili na hodnotě proměnné. Tady je rozhodnutím „která úloha pojede jako další“: kořen = prázdné pořadí, syn = připoj jednu dosud nezařazenou úlohu. List v hloubce $n$ = kompletní permutace.
Slide 17 (EN 1:1) — Bratley's Algorithm for $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$“A branch and bound (B&B) algorithm.
Branching - without bounding it is an enumerative method that creates a solution tree (some of the nodes are infeasible). Every node is labeled by: (the order of tasks)/(completion time of the last task).”
Zkus sám: uzel má pořadí $\sigma$ a čas dokončení poslední úlohy $c$. Připojím úlohu $T_j$ — jaký bude nový čas dokončení $c'$? Pozor na situaci, kdy $T_j$ ještě není uvolněná.
$T_j$ může začít nejdřív v $\max\{r_j,\ c\}$ — buď hned po předchozí úloze, nebo (je-li $r_j > c$) až po prostoji (idle waiting), kdy stroj čeká na její release. Takže $$c' = \max\{r_j,\ c\} + p_j.$$ To „$\max$“ je nejčastější početní chyba celé úlohy — kdo píše $c' = c + p_j$, rozbije si celý strom. Bez ořezávání má strom $n!$ listů; teď tři pravidla, která ho zmenší.
Pravidlo (i): ořez podle deadlinů — padají i „bratři“
Zkus sám: stojíš v uzlu $\sigma/c$ a díváš se na nezařazené úlohy. Kdy můžeš celý podstrom zahodit, aniž bys cokoli prozkoumal?
Když některá nezařazená $T_k$ nestihne deadline, ani kdyby jela hned teď: $\max\{c,\ r_k\} + p_k > \tilde{d}_k$. Hlouběji v podstromu se čas $c$ už jen zvětšuje, takže $T_k$ to nikdy nedožene — všechny listy pod $\sigma$ jsou nepřípustné.
Slide 18 (EN 1:1) — Reduction of the Tree - Bounding“(i) eliminate the node exceeding the deadline (and all its "brothers")
- If there is a node which exceeds any deadline, all its descendants should be eliminated
- Critical task (here $T_3$) will have to be scheduled anyway - therefore, all of its "brothers" should be eliminated as well”
Zkus sám: slide škrtá i „bratry“ provinilého uzlu. Proč je to korektní — proč smí padnout celé patro, když deadline překročil jen jeden syn?
Překročí-li syn $(\sigma, T_k)$ deadline $\tilde{d}_k$, znamená to $\max\{c, r_k\} + p_k > \tilde{d}_k$ už v rodiči. Jenže kritická úloha $T_k$ musí být někdy zařazena i v podstromu každého bratra $(\sigma, T_{k'})$ — a tam přijde na řadu ještě později (čas jen roste). Takže je mrtvý nejen syn, ale celé patro = celý podstrom rodiče $\sigma$. Prakticky si v každém uzlu jen projdeš nezařazené úlohy testem z předchozí otázky.
Pravidlo (ii): dekompozice při prostoji
Zkus sám: poslední zařazená úloha skončila v čase $c$ a všechny nezařazené úlohy mají $r_k \ge c$ (stroj by stejně stál). Má smysl se někdy vracet a přeskládávat to, co už je zařazené?
Ne. Zbylé úlohy nemohou začít dřív než ve svých release times — a ty nastanou až po $c$, takže žádné přeuspořádání už zařazených úloh by jim nepomohlo začít dřív. Dosavadní práce „byla optimální“ a uzel se může stát novým kořenem: nad něj se už nikdy nevracíme (odpadají i jeho bratři a všechny alternativy výš). Ze stromu s $n!$ listy zbude strom s $(n-k)!$ listy.
Slide 19 (EN 1:1) — Tree Size Reduction - Decomposition“(ii) problem decomposition due to idle waiting - e.g. when the employee waits for the material, his work was optimal
- Consider node $v$ on level $k$. If $C_i$ of the last scheduled task is less than or equal to $r_i$ of all unscheduled tasks, there is no need to backtrack above $v$
- $v$ becomes a new root and there are $n - k$ levels ($n - k$ unscheduled tasks) to be scheduled”
Test optimality: BRTP — kdy smíš rovnou skončit
Zkus sám: dorazil jsi k přípustnému listu s hodnotou $C_{max}$. Za jakých okolností můžeš okamžitě prohlásit optimum a zbytek stromu vůbec neprohledávat? (Nápověda: najdi dolní mez — před jakým časem nemůže poslední „blok“ rozvrhu nikdy začít?)
Podívej se na souvislý blok úloh na konci rozvrhu (od posledního prostoje do konce). Jestliže první úloha bloku startuje přesně ve svém release $r_{[1]}$ a $r_{[1]}$ je nejmenší release v celém bloku, pak žádná úloha bloku nemůže začít před $r_{[1]}$ — a protože blok běží bez mezer, jeho celková práce se před $r_{[1]} + \sum p_{[i]}$ nedá stihnout v žádném rozvrhu. Tvůj list téhle dolní meze přesně dosahuje → je optimální. To je BRTP.
Slide 20 (EN 1:1) — Optimality Test - Termination of Bratley's Algorithm“Definition: BRTP - Block with Release Time Property
BRTP is a set of $k$ tasks that satisfy:
- first task $T_{[1]}$ starts at its release time
- all $k$ tasks till the end of the schedule run without "idle waiting"
- $r_{[1]} \le r_{[i]}$ for all $i = 2 \ldots k$
Note: "till the end of the schedule" implies there is at most one BRTP
Lemma: sufficient condition of optimality — If BRTP exists, the schedule is optimal (the search is finished).
Proof: this schedule is optimal since the last task $T_{[k]}$ can not be completed earlier — order of prec. tasks is not important - see (ii) — no task from BRTP can be done before $r_{[1]}$ — there is no task after $C_{max}$”
Pozor na směr implikace — BRTP je podmínka postačující, ne nutná:
Slide 21 (EN 1:1) — BRTP is not Necessary Condition of Optimality“In this particular case, the schedule is optimal, but it does not have BRTP.
Tightening the bounds: In general, $C_{max}$ found without BRTP could be used for bounding further solutions while setting all deadlines to be at most $C_{max} - \epsilon$. This ensures that if other feasible schedules exist, only those that are better by $\epsilon$ than the solution at hand, are generated.”
Konkrétní mini-instance k obrázku slidu 21 (čísla vlastní — přiznáno): $T_1 = (r_1 = 1, p_1 = 2, \tilde{d}_1 = 3)$, $T_2 = (r_2 = 0, p_2 = 3, \tilde{d}_2 = 6)$. Kvůli $\tilde{d}_1$ musí $T_1$ jet přesně v $\langle 1, 3)$, takže $T_2$ (vcelku, bez preempce!) se před ni nevejde a pojede $\langle 3, 6)$:
Zkus sám: ověř, že rozvrh nahoře je optimální, ale BRTP nemá. A co s tím — jak hledání korektně ukončíš?
Koncový blok běží od $t = 1$ ($T_1$ startuje ve svém $r_1 = 1$, pak bez mezery $T_2$) — ale $r_2 = 0 < r_{[1]} = 1$, třetí podmínka BRTP padá. Optimální to přitom je: $T_2$ potřebuje 3 souvislé jednotky mimo okno $\langle 1, 3)$, takže dřív než v 6 neskončí. Řešení: zapamatuj si $C_{max} = 6$ jako incumbent (přesně jako $z^b$ v [L5.5]), utáhni všechny deadliny na $\min\{\tilde{d}_j,\ C_{max} - \epsilon\}$ (u celočíselných dat $\epsilon = 1$) a prohledávej dál — projít teď můžou jen ostře lepší rozvrhy. Když už nic neprojde (strom se uzavře), je incumbent optimum.
Celý běh: příklad ze slidu 22
Instance (slide 22, EN 1:1): $$r = (4, 1, 1, 0), \qquad p = (2, 1, 2, 2), \qquad \tilde{d} = (8, 5, 6, 4).$$
Zkus sám: spočítej labely všech čtyř synů kořene $(T_j)/c$ a rozhodni, kteří přežijí pravidlo (i).
$(T_1)/\max\{4, 0\} + 2 = 6$, $(T_2)/1 + 1 = 2$, $(T_3)/1 + 2 = 3$, $(T_4)/0 + 2 = 2$. Pravidlo (i): v uzlu $(T_1)/6$ by nezařazená $T_4$ končila nejdřív $\max\{6, 0\} + 2 = 8 > \tilde{d}_4 = 4$ → celý podstrom ✗ (svědkem je i $T_2$: $7 > 5$). V uzlu $(T_3)/3$: $T_4$ končí $\max\{3, 0\} + 2 = 5 > 4$ → ✗. Přežívají jen $(T_2)/2$ a $(T_4)/2$.
První nalezené řešení $(T_2, T_4, T_3, T_1)/8$ — rozvrh s prostojem na startu (stroj čeká na $r_2 = 1$):
Bez BRTP pokračujeme s utaženými deadliny $\tilde{d} \le 8 - 1 = 7$, tedy $\tilde{d} = (7, 5, 6, 4)$, a v podstromu $(T_4)$ najdeme $(T_4, T_2, T_3, T_1)/7$ — to už BRTP má:
Nebezpečné polopravdy① „$c' = c + p_j$.“ Ne — $c' = \max\{r_j,\ c\} + p_j$: když úloha ještě není uvolněná, stroj stojí (idle waiting). Zapomenutý $\max$ = celý strom špatně. ② Pravidlo (i) neškrtá jen jeden uzel. Kritická úloha musí být zařazena v každém bratrovi taky (a jen později) — padá celé patro / celý podstrom rodiče. ③ „Bez BRTP ⇒ není to optimum.“ Ne! BRTP je jen postačující podmínka (slide 21) — bez ní nesmíš nic uzavírat: utáhneš deadliny na $\le C_{max} - \epsilon$ a hledáš dál; optimum je potvrzené, až když se strom uzavře. ④ BRTP blok = od posledního prostoje do konce rozvrhu. Prostoj dříve v rozvrhu BRTP nevylučuje (uvidíš v T02: optimum má uprostřed díru a BRTP přesto existuje). A nezapomeň na třetí podmínku $r_{[1]} \le r_{[i]}$ — právě ta v běhu výše shodila řešení /8. ⑤ První přípustný list ≠ konec — stejné pravidlo jako u B&B v [L5.5]: incumbent jen inicializuje mez.
Key takeaways — L5.9- Bratley = B&B nad pořadími úloh pro silně NP-těžké $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$. Uzel značíme (pořadí úloh)/(čas dokončení poslední); připojení $T_j$: $c' = \max\{r_j,\ c\} + p_j$ (nezapomeň $\max$ — idle waiting).
- (i) Ořez deadliny: existuje-li nezařazená $T_k$ s $\max\{c,\ r_k\} + p_k > \tilde{d}_k$, je mrtvý celý podstrom — kritická úloha shazuje i všechny „bratry“.
- (ii) Dekompozice: je-li $c \le r_k$ všech nezařazených, uzel se stává novým kořenem — žádný backtrack nad něj.
- BRTP (blok od posledního prostoje do konce: $T_{[1]}$ startuje v $r_{[1]}$, žádné mezery, $r_{[1]} \le r_{[i]}$ v bloku) ⟹ rozvrh je optimální, hledání končí. Je to podmínka postačující, ne nutná — bez ní pokračuj s deadliny utaženými na $\le C_{max} - \epsilon$.
- U zkoušky odevzdej: strom s labely $(\sigma)/c$ a důvody ořezů, Gantt výsledného rozvrhu a zdůvodnění optimality (BRTP, nebo uzavřený strom). (Téma ústní.)
“Using Bratley's branch-and-bound algorithm for $1 \mid r_j, \widetilde{d}_j \mid C_{\max}$, solve the source example
$$r = (4, 1, 1, 0), \qquad p = (2, 1, 2, 2), \qquad \widetilde{d} = (8, 5, 6, 4).$$
Draw the search tree or list explored nodes. Label every node by $$\frac{\text{order of tasks}}{\text{completion time of the last task}}.$$
Use the bounding/decomposition/optimality rules from the Bratley slides.”
a) Co je v zadání?
Čtyři nepreemptivní úlohy na jednom stroji, release times a tvrdé deadliny; máme odevzdat celý strom (nebo seznam navštívených uzlů) se správnými labely $(\sigma)/c$, důvody ořezů a zdůvodněnou optimalitou. Je to přesně instance rozebraná ve výkladu — tady si ji zapiš tak, jak ji budeš psát na papír u zkoušky.
b) Co k tomu budeme potřebovat?
- Tato lekce — labely uzlů, pravidla (i)/(ii) a BRTP (takeaways).
- [L5.5] Branch & Bound pro ILP — disciplína B&B: incumbent, uzavírání větví.
- [L5.1] Grahamova notace — čtení $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$, kreslení Ganttova diagramu.
c) Jak nad úlohou uvažovat?
DFS, syny ber v pořadí indexů. V každém uzlu: ① spočti label $c' = \max\{r_j, c\} + p_j$, ② projeď nezařazené úlohy testem $\max\{c', r_k\} + p_k \le \tilde{d}_k$ — při neúspěchu ✗ s uvedeným svědkem, ③ zkontroluj dekompozici ($c' \le$ všechna zbylá $r_k$), ④ u listu spočti $C_{max}$ a otestuj všechny tři podmínky BRTP. Bez BRTP nezapomeň utáhnout deadliny a pokračovat.
d) Úplné řešení (strom = slide 22 1:1; běh rozebraný ve stepperu výše)
Navštívené uzly (✗ = ořez pravidlem (i) s uvedeným svědkem):
- $(T_1)/6$ ✗ — $T_4$: $\max\{6, 0\} + 2 = 8 > 4$ (stačí jeden svědek; padl by i na $T_2$: $7 > 5$).
- $(T_2)/2$ → $(T_2, T_1)/6$ ✗ ($T_3$: $\max\{6,1\} + 2 = 8 > 6$); $(T_2, T_3)/4$ ✗ ($T_4$: $6 > 4$); $(T_2, T_4)/4$ → $(T_2, T_4, T_1)/6$ ✗ ($T_3$: $8 > 6$); $(T_2, T_4, T_3)/6$ → $(T_2, T_4, T_3, T_1)/8$ přípustné, $C_{max} = 8$. Test optimality: koncový blok startuje s $T_2$ v $r_2 = 1$, ale $r_4 = 0 < 1$ → BRTP NE („NO, $r_2 > r_4$“ na slidu). Incumbent 8, deadliny utáhnout na $\tilde{d} := \min\{\tilde{d},\ 7\} = (7, 5, 6, 4)$.
- $(T_3)/3$ ✗ — $T_4$: $\max\{3, 0\} + 2 = 5 > 4$.
- $(T_4)/2$ → $(T_4, T_1)/6$ ✗ ($T_2$: $\max\{6,1\} + 1 = 7 > 5$); $(T_4, T_2)/3$ → $(T_4, T_2, T_1)/6$ ✗ ($T_3$: $8 > 6$); $(T_4, T_2, T_3)/5$ → $(T_4, T_2, T_3, T_1)/7$ přípustné ($7 \le 8$, prošlo i utaženým $\tilde{d}_1 = 7$), $C_{max} = 7$. Test optimality: blok $T_4, T_2, T_3, T_1$ běží od $t = 0$ bez prostojů až do konce, $T_4$ startuje v $r_4 = 0$ a $r_4 = 0 \le r_1, r_2, r_3$ → BRTP ANO → optimum, stop. Uzel $(T_4, T_3)$ se už neprozkoumá.
Výsledek: pořadí $(T_4, T_2, T_3, T_1)$, rozvrh $T_4\,\langle 0,2)$, $T_2\,\langle 2,3)$, $T_3\,\langle 3,5)$, $T_1\,\langle 5,7)$, $$C_{max}^* = 7,$$ optimalita certifikována BRTP (Gantt viz obrázek „optimum /7“ ve výkladu). U zkoušky nakresli strom (stepper výše, poslední krok) + tento Gantt + větu o BRTP.
„Bratley's algorithm (tree)
$$r = [5, 0, 4, 0], \qquad p = [3, 2, 2, 1], \qquad d = [10, 3, 10, 2]$$
a) nakreslit strom a Ganttuv diagram — b) je to optimalni reseni? Proc?“
(EN: Run Bratley's algorithm on the instance above. a) Draw the search tree and the Gantt chart. b) Is the solution optimal? Why?)
a) Co je v zadání?
Stejná disciplína jako T01, jiná čísla ($d$ zde čti jako tvrdé deadliny $\tilde{d}$). Bonus téhle instance: poprvé reálně vystřelí pravidlo (ii) — dekompozice a optimum má uprostřed prostoj — přesto BRTP existuje (pozor na polopravdu ④).
b) Co k tomu budeme potřebovat?
- Tato lekce — pravidla (i)/(ii), BRTP a utahování deadlinů (takeaways).
- [L5.5] — incumbent a uzavírání větví.
c) Jak nad úlohou uvažovat?
Začni syny kořene: tři ze čtyř padnou na tutéž kritickou úlohu — kterou? Pak si u uzlu $(T_4, T_2)/3$ srovnej $c = 3$ s release times nezařazených úloh… a vzpomeň si, co to znamená pro backtracking. První nalezený list ti vyjde s $C_{max} = 10$ — nezapomeň BRTP test a co dělat, když selže.
d) Úplné řešení (strom vlastní odvození — přiznáno; výsledný rozvrh a zdůvodnění = vzorové řešení 1:1)
Krokovaný strom (DFS, syny v pořadí indexů):
Výsledný rozvrh — vzorové řešení (Master_Zkouska_KO, 1:1): „a) Schedule: $T_4 \mid T_2\, T_2 \mid - \mid T_3\, T_3 \mid T_1\, T_1\, T_1$ ($t = 0..9$), $C_{max} = 9$. b) This solution is optimal since there is BRTP which starts at $r_3 = 4$.“
Rozepsáno: $T_4\,\langle 0,1)$, $T_2\,\langle 1,3)$, prostoj $\langle 3,4)$, $T_3\,\langle 4,6)$, $T_1\,\langle 6,9)$. Koncový blok $\{T_3, T_1\}$ běží od posledního prostoje do konce: $T_3$ startuje ve svém $r_3 = 4$, bez mezer, a $r_3 = 4 \le r_1 = 5$ → BRTP ANO → optimum, $C_{max}^* = 9$. Prostoj $\langle 3, 4)$ BRTP nevadí — blok se počítá od posledního prostoje (na tohle se ptal i autor wiki přepisu: „v nejlepším řešení se musí čekat“ — ano, a BRTP přesto existuje).
Pozn. k běhu: dekompozice v $(T_4, T_2)/3$ říká, že se nad tento uzel už nevracíme — větev $(T_4, T_3)$ ani alternativy u kořene netřeba zkoumat. První list $(T_4, T_2, T_1, T_3)/10$ BRTP neměl ($r_1 = 5 > r_3 = 4$), takže se deadliny utáhly na $\min\{\tilde{d}, 9\} = (9, 3, 9, 2)$ a pokračovalo se — druhý list $/9$ už prošel i utaženými deadliny a BRTP měl.
Drill navíc (test 6. 5. 2014, varianta B — čísla 1:1, řešení vlastní pro sebekontrolu): $r = (1, 8, 2, 0)$, $p = (2, 1, 2, 3)$, $\tilde{d} = (6, 9, 7, 6)$. Má vyjít: pořadí $(T_4, T_1, T_3, T_2)$, rozvrh $T_4\,\langle 0,3)$, $T_1\,\langle 3,5)$, $T_3\,\langle 5,7)$, prostoj, $T_2\,\langle 8,9)$, $C_{max}^* = 9$; dekompozice vystřelí v $(T_4, T_1, T_3)/7 \le r_2 = 8$ a optimalitu certifikuje jednoprvkový BRTP blok $\{T_2\}$ startující v $r_2 = 8$ ($k = 1$ stačí — podmínka $r_{[1]} \le r_{[i]}$ je prázdná).