List scheduling pro P | prec | Cmax (faktor)
Nepreemptivní $P\,||\,C_{max}$ je NP-hard a s precedencemi $P\,|\,prec\,|\,C_{max}$ to lepší není (víc o NP-těžkosti rozvrhování v [L5.13]). Exaktní Rothkopf [L5.11] platí pseudopolynomiální daň a precedence vůbec neumí; Muntz&Coffman [L5.10] potřebuje preempci. Co zbývá, když je úloh hodně, precedence v zadání a preempce zakázaná? Heuristika se zárukou — aproximační algoritmus ve smyslu [L3.1]: nevrátí nutně optimum, ale dokazatelně nikdy nepřekročí $r \cdot C^*_{max}$. Dnes ta nejslavnější: list scheduling (slidy 41–46). Notaci $P\,|\,prec\,|\,C_{max}$ čteš dle [L5.1]: identické paralelní stroje, nepreemptivní úlohy s precedencemi (DAG), minimalizuj makespan.
Algoritmus: první připravená úloha ze seznamu (slide 41)
Zkus sám: navrhni nejjednodušší možný rozvrhovač pro $P\,|\,prec\,|\,C_{max}$. Co budeš dělat ve chvíli, kdy se uvolní stroj?
Přesně to, co by tě napadlo: drž si seznam (list) úloh a uvolněnému stroji dej první úlohu ze seznamu, která je připravená — tj. všichni její predchůdci v DAGu už doběhli. Žádné přerozvrhování, žádný backtracking, jeden průchod. Jediné, co je potřeba hlídat, je kdy se úloha stává připravenou — k tomu slouží availability time $a_i$.
Slide 41 (EN 1:1) — List Scheduling - Approximation Alg. for $P \,|\, \mathrm{prec} \,|\, C_{\max}$“Input: $R$, number of parallel identical resources, $n$, number of non-preemptive tasks and their proc. times $(p_1, p_2, \ldots, p_n)$. DAG.
Output: start times $(s_1, s_2, \ldots, s_n)$ and resource IDs $(z_1, z_2, \ldots, z_n)$.”
t_v := 0 for all v ∈ 1..R; // free time of resource
s_i = z_i := 0 for all i ∈ 1..n;
Sort tasks in list L;
for i := 1 to n do // for all tasks
k = arg min_{v=1..R} {t_v}; // choose res. with lowest t_v
Create S, a subset of tasks in L with smallest availability time a_i;
Choose T_i ∈ S which is the first one in list L;
Remove T_i from list L;
s_i = max{t_k, a_i}; z_i = k; // assign T_i to P_k
t_k = s_i + p_i; // update free time of P_k
end
“$a_i$, availability time of $T_i$, is equal to $t_k$ if it has no predecessors, it is equal to $\infty$ if at least one of its predecessors is in $L$, and it is equal to $\max_{j \in \mathrm{Pred}(T_i)}\{s_j + p_j\}$ if all of its predecessors have been removed from $L$.”
Čtení pseudokódu: v každé iteraci vyber nejdřív uvolněný stroj $P_k$ (nejmenší $t_v$), pak mezi úlohami zbylými v $L$ najdi ty s nejmenším $a_i$ a z nich vezmi tu, která je v $L$ první. Tři případy $a_i$: úloha bez predchůdců je k dispozici hned ($a_i = t_k$); úloha, jejíž predchůdce ještě čeká v $L$, nepřipadá v úvahu ($a_i = \infty$); jinak je k dispozici od dokončení posledního predchůdce ($\max_j \{s_j + p_j\}$). Start je $s_i = \max\{t_k, a_i\}$ — stroj může na připravovanou úlohu i chvíli čekat.
Slide 42 (EN 1:1) — co LS vlastně je“List Scheduling (LS) is a general heuristic useful in many problems.
- We have a list ($n$-tuple) of tasks and when some resource is free, we assign available task from the list to this resource.
- The accuracy of LS depends on the criterion and sorting procedure.”
Jak špatné to může být? Faktor $2 - \frac{1}{R}$ (slide 42)
Kvalita výsledku závisí na pořadí úloh v $L$. Slide 42 to ukazuje na instanci, kde se nejhorší případ opravdu stane: $R = 4$, $n = (R-1)\cdot R + 1 = 13$, $p = (1, 1, \ldots, 1, 4)$ (dvanáct jednotkových úloh + jedna délky $R = 4$), $\prec$ prázdné. Proklikej běh LS s „hloupým“ seznamem $L' = (T_1, T_2, \ldots, T_{13})$:
Tatáž instance se seznamem $L = (T_{13}, T_1, \ldots, T_{12})$ — dlouhá úloha jde první:
Zkus sám: spočítej poměr $C_{max}^{LS} / C^*_{max}$ z obou obrázků. Vidíš v něm $2 - \frac{1}{R}$?
$\frac{7}{4} = 1{,}75 = 2 - \frac{1}{4}$ — přesně faktor pro $R = 4$. A obecně: $C^*_{max} = R$ (dlouhá úloha běží paralelně s jednotkovými), kdežto špatný list nejdřív rovnoměrně rozlije $(R-1)\cdot R$ jednotek na $R$ strojů (do času $R - 1$) a dlouhou úlohu délky $R$ nechá až nakonec: $C_{max} = (R-1) + R = 2R - 1 = (2 - \frac{1}{R}) \cdot R$. Hůř to dopadnout nemůže — to je obsah Grahamovy věty.
Slide 42 (EN 1:1) — Approximation factor of LS algorithm [Graham 1966]“For $P \,|\, \mathrm{prec} \,|\, C_{\max}$ (and also for $P \,||\, C_{\max}$) and arbitrary (unsorted) list $L$, List Scheduling is an approximation algorithm with factor $r_{LS} = 2 - \frac{1}{R}$”
An example illustrating the case when the factor is attained: $n = (R-1)\cdot R + 1$, $p = (1, 1, \ldots, 1, R)$, $\prec$ empty. Illustration for $R = 4$: $r_{LS} = 2 - \frac{1}{4} = \frac{7}{4}$, $L = (T_n, T_1, \ldots, T_{n-1})$ vs $L' = (T_1, T_2, \ldots, T_n)$.
Zkus sám (náčrt důkazu pro $P\,||\,C_{max}$ — vlastní doplněk, na slidech věta bez důkazu): ať $T_l$ je úloha, která končí poslední. Proč před jejím startem $s_l$ žádný stroj nezahálí? A co z toho plyne?
Bez precedencí je každá úloha připravená od začátku — kdyby nějaký stroj před $s_l$ zahálel, LS by mu $T_l$ (nebo jinou čekající úlohu) přidělil dřív. Do času $s_l$ tedy všech $R$ strojů nepřetržitě pracuje: $R \cdot s_l \le \sum_i p_i - p_l$, tj. $s_l \le \frac{1}{R}\sum_i p_i - \frac{p_l}{R}$. Dosaď dolní meze $C^*_{max} \ge \frac{1}{R}\sum_i p_i$ a $C^*_{max} \ge p_l$: $$C_{max} = s_l + p_l \le \frac{1}{R}\textstyle\sum_i p_i + \left(1 - \frac{1}{R}\right) p_l \le C^*_{max} + \left(1 - \frac{1}{R}\right) C^*_{max} = \left(2 - \frac{1}{R}\right) C^*_{max}.$$ S precedencemi je argument jemnější (místo jedné úlohy se sleduje řetěz predchůdců, jehož délka je dolní mez $C^*_{max}$), ale mez $2 - \frac{1}{R}$ platí beze změny [Graham 1966].
Anomálie: „pomohl jsem si“ — a rozvrh se prodloužil (slidy 43–44)
Faktor je záruka na nejhorší případ — neříká nic o tom, že se LS chová „rozumně“ při změnách vstupu. Slide 43 dává instanci pro $R = 2$: $n = 8$, $p = (3, 4, 2, 4, 4, 2, 13, 2)$ s precedencemi (DAG rekonstruován z popisu obrázku slidu — přiznáno):
Běh LS se seznamem $L = (T_1, T_2, \ldots, T_8)$ — sleduj, jak rozhoduje availability time:
Zkus sám: výsledných $C_{max} = 17$ vypadá obyčejně. Srovnej se $\sum_i p_i / R$. Co zjistíš?
$\sum_i p_i = 34$, takže $\frac{34}{2} = 17$ — ani jeden stroj ani chvíli nezahálí, LS tady našel optimum. To je důležitá kalibrace: heuristika často trefí optimum a faktor $2 - \frac{1}{R}$ je jen pojistka. Pointa slidů 43–44 je ale jinde: stačí drobnost a výsledek se zhorší.
Slide 43 (EN 1:1) — Anomalies of List Scheduling Algorithm“The LS algorithm depends not only on the order of tasks in $L$, but it exhibits anomalies ($C_{\max}$ surprisingly increases when relaxing some constraints/parameters) caused by:
- the decrease of processing time $p_i$
- the removal of some precedence constraints
- the increase of the number of resources $R$”
Slide 44 pak na téže instanci předvádí čtyři modifikace (EN 1:1): “Exchange position of $T_7$ and $T_8$”, “(2) Remove prec. constr. $T_3 \prec T_4$.”, “(1) Decrease $p_i$ of all tasks by one.”, “(3) Add resource ($R = 3$).” — každá vede k delšímu $C_{max}$ než původních 17 (Gantty na slidu).
Zkus sám: prohoď v seznamu $T_7$ a $T_8$ (tj. $L = (T_1, \ldots, T_6, T_8, T_7)$) a odsimuluj LS. Proč se rozvrh prodlouží?
V okamžiku, kdy jsou $T_7$ i $T_8$ připravené (obě $a = 3$), bere LS tu, která je v $L$ dřív — teď tedy krátkou $T_8$ na uvolněnou $P_2$. Obří $T_7$ ($p_7 = 13$) pak startuje až v čase 5 na $P_1$ a táhne rozvrh do $C_{max} = 18 > 17$ (běh níže; simulace dle pseudokódu vlastní — přiznáno, Gantt slidu 44 je jen na obrázku):
A nejprotivnější anomálie (3): přidej stroj a bude hůř. S $R = 3$ a původním seznamem dá LS $C_{max} = 19$ (simulace dle pseudokódu vlastní — přiznáno): třetí stroj „ukradne“ $T_3$ dřív, takže se dřív připraví $T_4, T_5, T_6$, ty předběhnou ve frontě dlouhou $T_7$ — a ta startuje až v čase 6:
Anomálie nejsou folklór — u ústní se na ně ptají- LS není monotónní. Zkrácení úloh, odebrání precedencí i přidání stroje — všechno „zlepšení“ vstupu — může $C_{max}$ prodloužit (příčiny slide 43, prodloužení demonstruje slide 44, případy 1–3). Záruka je jen jedna: $C_{max} \le (2 - \frac{1}{R}) \, C^*_{max}$.
- Mechanismus je vždy stejný: změna uvolní/posune nějakou úlohu ve frontě dřív, tím se přehází přiřazení strojům a dlouhá úloha (tady $T_7$) skončí pozdě. Faktor se tím neporuší — jen se v rámci něj posuneš k horšímu.
- Proto v praxi: výsledek LS po změně vstupu vždy přepočítej; neargumentuj „ubral jsem práci, hůř být nemůže“.
LPT: setřiď list a faktor klesne (slidy 45–46)
Zkus sám: v příkladu na faktor (R = 4 výše) prohrál seznam, který nechal dlouhou úlohu nakonec. Jak bys list seřadil, aby se to nestalo?
Od nejdelší úlohy — dlouhé úlohy odbavit první, krátkými se mezery dorovnají. Přesně to je LPT (Longest Processing Time first): při inicializaci LS setřiď $L$ podle nerostoucích $p_i$. Na příkladu výše dá LPT rovnou optimum ($T_{13}$ první). Obecně faktor klesne z $2 - \frac{1}{R}$ na $\frac{4}{3} - \frac{1}{3R}$ — ale pozor, věta platí pro $P\,||\,C_{max}$, tedy bez precedencí.
Slide 45 (EN 1:1) — LPT (Longest Processing Time First) - Approximation Algorithm for $P \,||\, C_{\max}$“The approximation factor of the LS algorithm can be decreased using the Longest Processing Time first (LPT) strategy
- During initialization of LS, we sort list $L$ in a non-increasing order of $p_i$
Approximation factor of LPT algorithm [Graham 1966]: LPT algorithm for $P \,||\, C_{\max}$ is an approximation algorithm with factor $r_{LPT} = \frac{4}{3} - \frac{1}{3R}$
Time complexity of LPT algorithm is $\mathcal{O}(n \cdot \log(n))$ due to the sorting.”
I LPT má svou těsnou instanci (slide 46): $p = (2R-1, 2R-1, 2R-2, 2R-2, \ldots, R+1, R+1, R, R, R)$, $n = 2R + 1$, $\prec$ prázdné. Pro $R = 3$: $p = (5, 5, 4, 4, 3, 3, 3)$, $r_{LPT} = \frac{4}{3} - \frac{1}{9} = \frac{11}{9}$. Proklikej běh LPT (list už je setříděný):
Zkus sám: najdi pro $p = (5, 5, 4, 4, 3, 3, 3)$, $R = 3$ optimum. Nápověda: zkus dát dvě trojky k sobě.
$\sum p_i = 27 = 3 \cdot 9$, takže dolní mez je 9 — a jde trefit: $P_1$: $T_1 + T_3$ ($5 + 4$), $P_2$: $T_2 + T_4$ ($5 + 4$), $P_3$: $T_5 + T_6 + T_7$ ($3 + 3 + 3$). $C^*_{max} = 9$, poměr $\frac{11}{9} = \frac{4}{3} - \frac{1}{3 \cdot 3}$ — faktor je těsný. LPT prohrává, protože páruje hladově „dlouhá + dlouhá“ podle uvolnění strojů a tři trojky mu nakonec nevyjdou na jeden stroj.
Slide 46 (EN 1:1) — Factor of LPT algorithm“If the number of tasks is big, the factor can get better depending on $k$ - the number of tasks assigned to the resource which finishes last: $r_{LPT} = 1 + \frac{1}{k} - \frac{1}{kR}$”
Nebezpečné polopravdy kolem LS/LPT- Faktor $2 - \frac{1}{R}$ je worst-case záruka, ne typický výsledek. LS klidně najde optimum (instance slidu 43: $C_{max} = 17 = \sum p_i / R$). Ale taky se na faktor přesně dosáhne (instance slidu 42) — „heuristika“ tu neznamená „bez záruky“, znamená to r-aproximaci dle [L3.1].
- LPT faktor $\frac{4}{3} - \frac{1}{3R}$ platí jen pro $P\,||\,C_{max}$. S precedencemi smíš tvrdit jen obecných $2 - \frac{1}{R}$ (věta o LS platí pro libovolný, i setříděný list). Neprohazuj.
- Nezaměň role: LS je aproximační, ne exaktní. Exaktně řeší $P\,||\,C_{max}$ Rothkopf DP [L5.11] (pseudopolynomiálně, bez prec); s preempcí je $P\,|\,pmtn\,|\,C_{max}$ snadný McNaughton [L5.4] a $P\,|\,pmtn,prec\,|\,C_{max}$ řeší Muntz&Coffman [L5.10] (sám je pro obecné DAGy aproximační s faktorem $2 - \frac{2}{R}$). Volba metody: tahák [L5.14].
- „První v listu“ ≠ „první podle indexu“. Výběr jde přes nejmenší availability time $a_i$ a teprve mezi nimi rozhoduje pořadí v $L$ — proto LS někdy nechá stroj čekat krátce na připravovanou úlohu a proto vznikají anomálie při prohození položek.
Key takeaways — L5.12- Algoritmus: drž list $L$; v každé iteraci vyber stroj s nejmenším $t_v$, mezi úlohami s nejmenším availability time $a_i$ vezmi první v $L$; $s_i = \max\{t_k, a_i\}$, $t_k \mathrel{+}= p_i$. $a_i$: $t_k$ bez predchůdců / $\infty$ dokud je predchůdce v $L$ / $\max_j\{s_j + p_j\}$ jinak.
- Faktor [Graham 1966]: pro $P\,|\,prec\,|\,C_{max}$ i $P\,||\,C_{max}$ a libovolný list je $r_{LS} = 2 - \frac{1}{R}$; těsné na $n = (R-1)R + 1$, $p = (1, \ldots, 1, R)$ se špatným pořadím (dlouhá úloha nakonec).
- LPT: setřiď $L$ nerostoucně podle $p_i$ → pro $P\,||\,C_{max}$ faktor $r_{LPT} = \frac{4}{3} - \frac{1}{3R}$, složitost $\mathcal{O}(n \log n)$; zpřesnění $r_{LPT} = 1 + \frac{1}{k} - \frac{1}{kR}$ ($k$ = počet úloh na stroji, který končí poslední).
- Anomálie: $C_{max}$ může vzrůst po zkrácení $p_i$, odebrání precedencí i přidání stroje (a po přeskupení listu) — LS není monotónní, platí jen worst-case faktor.
- Volba metody (tahák [L5.14]): $P\,|\,prec\,|\,C_{max}$ bez pmtn = list scheduling; s pmtn = M&C [L5.10]; bez prec exaktně Rothkopf [L5.11], s pmtn McNaughton [L5.4].
„List scheduling - algoritmus v pseudokódu, jaký je faktor aproximace a jaký pro LPT“
(EN) Write down the List Scheduling algorithm in pseudocode. What is its approximation factor, and what is the approximation factor of LPT?
a) Co je v zadání?
Čistě reprodukční otázka za plný počet bodů: (i) pseudokód LS pro $P\,|\,prec\,|\,C_{max}$ včetně definice availability time, (ii) Grahamův faktor LS, (iii) faktor LPT — u obou říct, pro který problém platí.
b) Co k tomu budeme potřebovat?
- Tato lekce — pseudokód, oba faktory a jejich těsné instance (takeaways).
- [L3.1] Co je aproximační algoritmus a faktor r — co tvrzení $C_{max} \le r \cdot C^*_{max}$ znamená.
- [L5.1] Grahamova notace — korektní zápis $P\,|\,prec\,|\,C_{max}$ vs. $P\,||\,C_{max}$.
c) Jak nad úlohou uvažovat?
Pseudokód piš kolem tří rozhodnutí: který stroj ($\arg\min t_v$), které úlohy připadají v úvahu (nejmenší $a_i$), která z nich (první v $L$) — a nezapomeň na $s_i = \max\{t_k, a_i\}$. K faktorům přidej jednu větu kontextu (pro jaký problém, kdo, čím je těsný) — to bývá rozdíl mezi „zná vzorec“ a „rozumí“.
d) Úplné řešení
(i) Pseudokód (slide 41; Input: $R$, $n$, $(p_1, \ldots, p_n)$, DAG; Output: $(s_1, \ldots, s_n)$, $(z_1, \ldots, z_n)$):
t_v := 0 for all v ∈ 1..R; // free time of resource
s_i = z_i := 0 for all i ∈ 1..n;
Sort tasks in list L;
for i := 1 to n do
k = arg min_{v=1..R} {t_v}; // res. with lowest t_v
Create S, a subset of tasks in L with smallest availability time a_i;
Choose T_i ∈ S which is the first one in list L;
Remove T_i from list L;
s_i = max{t_k, a_i}; z_i = k; // assign T_i to P_k
t_k = s_i + p_i;
end
kde $a_i = t_k$, nemá-li $T_i$ predchůdce; $a_i = \infty$, je-li aspoň jeden predchůdce ještě v $L$; jinak $a_i = \max_{j \in \mathrm{Pred}(T_i)}\{s_j + p_j\}$.
(ii) Faktor LS: pro $P\,|\,prec\,|\,C_{max}$ (a také $P\,||\,C_{max}$) a libovolný (nesetříděný) list $$r_{LS} = 2 - \frac{1}{R} \qquad \text{[Graham 1966]},$$ těsné na instanci $n = (R-1)R + 1$, $p = (1, \ldots, 1, R)$, $\prec$ prázdné, s listem končícím dlouhou úlohou (pro $R = 4$: $\frac{7}{4}$).
(iii) Faktor LPT (list setříděný nerostoucně podle $p_i$, $\mathcal{O}(n \log n)$): pro $P\,||\,C_{max}$ $$r_{LPT} = \frac{4}{3} - \frac{1}{3R} \qquad \text{[Graham 1966]},$$ těsné na $p = (2R-1, 2R-1, \ldots, R+1, R+1, R, R, R)$, $n = 2R+1$ (pro $R = 3$: $\frac{11}{9}$). Bonus k ústní: pro velký počet úloh platí jemnější $r_{LPT} = 1 + \frac{1}{k} - \frac{1}{kR}$, kde $k$ je počet úloh na stroji, který končí poslední. S precedencemi pro LPT žádná lepší záruka než $2 - \frac{1}{R}$ z (ii) není.
Consider $P \,||\, C_{max}$ with $R = 2$ identical parallel resources and $n = 5$ tasks with processing times $p = (3, 3, 2, 2, 2)$.
(i) Run the LPT algorithm and draw the Gantt chart.
(ii) Find an optimal schedule and compare the ratio $C_{max}^{LPT} / C^*_{max}$ with the LPT approximation factor.
(iii) For general $R$, which instances attain the LPT factor?
a) Co je v zadání?
Malá instance bez precedencí — ručně odsimulovat LPT (= LS se setříděným listem), najít optimum a ověřit, že poměr sedí na vzorec faktoru. Je to přesně rodina těsných instancí ze slidu 46, dosazená pro $R = 2$: $(2R-1, 2R-1, R, R, R) = (3, 3, 2, 2, 2)$, $n = 2R+1 = 5$.
b) Co k tomu budeme potřebovat?
- Tato lekce — pseudokód LS + LPT a vzorec faktoru (takeaways).
- Dolní meze $C^*_{max} \ge \max\{\max_i p_i, \frac{1}{R}\sum_i p_i\}$ — viz [L5.4].
c) Jak nad úlohou uvažovat?
List je už setříděný ($3, 3, 2, 2, 2$). Iteruj pseudokód: vždy stroj s menším $t_v$ (při shodě $P_1$), úlohy jsou bez precedencí, takže vyhrává prostě první zbylá v $L$. U optima zkus dolní mez $\frac{1}{2}\sum p_i$ a hledej rozdělení, které ji trefí. U (iii) si vzpomeň, čím přesně LPT na téhle rodině prohrává.
d) Úplné řešení (vlastní — přiznáno)
(i) Běh LPT, $L = (T_1, T_2, T_3, T_4, T_5)$:
| iterace | $k$ ($t_1, t_2$) | úloha | $s_i$ | nové $t_k$ |
|---|---|---|---|---|
| 1 | $P_1$ $(0,0)$ | $T_1$, $p=3$ | 0 | $t_1 = 3$ |
| 2 | $P_2$ $(3,0)$ | $T_2$, $p=3$ | 0 | $t_2 = 3$ |
| 3 | $P_1$ $(3,3)$ | $T_3$, $p=2$ | 3 | $t_1 = 5$ |
| 4 | $P_2$ $(5,3)$ | $T_4$, $p=2$ | 3 | $t_2 = 5$ |
| 5 | $P_1$ $(5,5)$ | $T_5$, $p=2$ | 5 | $t_1 = 7$ |
$C_{max}^{LPT} = 7$, $s = (0, 0, 3, 3, 5)$, $z = (1, 2, 1, 2, 1)$:
(ii) Optimum: $\sum p_i = 12$, dolní mez $\frac{12}{2} = 6$ — a trefí se: $P_1$: $T_1 + T_2$ ($3+3$), $P_2$: $T_3 + T_4 + T_5$ ($2+2+2$), $C^*_{max} = 6$.
Poměr $\frac{C_{max}^{LPT}}{C^*_{max}} = \frac{7}{6} = \frac{4}{3} - \frac{1}{3 \cdot 2} = r_{LPT}$ — faktor je na této instanci dosažen (těsný). Sedí i zpřesnění: poslední končí stroj se $k = 3$ úlohami ($T_1, T_3, T_5$), $1 + \frac{1}{3} - \frac{1}{3 \cdot 2} = \frac{7}{6}$ ✓.
(iii) Rodina ze slidu 46 (EN 1:1): “$p = (2R - 1, 2R - 1, 2R - 2, 2R - 2, \ldots, R + 1, R + 1, R, R, R)$, $n = 2 \cdot R + 1$, $\prec$ empty”. LPT na ní hladově spáruje dlouhé úlohy podle uvolňování strojů a tři úlohy délky $R$ mu nevyjdou na jeden stroj — optimum přitom dává všem strojům přesně $3R$ jednotek… pro $R = 2$: $3R = 6$ ✓. Obecně $C^*_{max} = 3R$, $C_{max}^{LPT} = 4R - 1$, poměr $\frac{4R-1}{3R} = \frac{4}{3} - \frac{1}{3R}$.