Grahamova notace α|β|γ
Vstupujeme do kapitoly rozvrhování (scheduling) — slot 5 písemky, padá v každém termínu. Každé zkouškové zadání z rozvrhování začíná zápisem typu $P2 \,|\, \mathrm{pmtn}, \mathrm{prec} \,|\, C_{max}$ a po tobě se často výslovně chce „Meaning of the notation“. Tahle lekce nemá žádné prerekvizity a celá kapitola na ní stojí — proto jde první.
Co je rozvrhování (a jak vypadá výsledek)
Terminologie (slide 6, EN 1:1)- set of $n$ tasks $\mathcal{T} = \{T_1, T_2, \ldots, T_n\}$
- set of $m$ types of resources (processors, machines, employees,…) with capacities $R_k$
- “Scheduling is an assignment of a task to resources in time.”
- Each task must be completed (tím se rozvrhování liší od plánování, které teprve rozhoduje, co se vůbec zpracuje).
- Množina úloh je známa předem — off-line scheduling.
- “A result is a schedule which determines which task is run on which resource and when. Often depicted as a Gantt chart.”
K tomu dvě obecná omezení (general constraints, slide 7), která platí vždy: každá úloha běží v daném okamžiku nejvýš na jednom prostředku (úloha je sekvenční) a každý prostředek zpracovává v daném okamžiku nejvýš jednu úlohu. Výsledný rozvrh (schedule) se kreslí jako Gantt chart (Ganttův diagram): řádek = prostředek, blok = běh úlohy v čase.
Zkus sám: přečti z diagramu — kdy a kde běží $T_3$? A v jakém čase je hotová poslední úloha?
$T_3$ běží na procesoru $P^1$ v intervalu $[2,5]$. Poslední úlohy ($T_4$ na $P^1$ a $T_5$ na $P^2$) končí v čase $6$ — téhle hodnotě se říká makespan $C_{max}$, délka rozvrhu, a bude to nejčastější optimalizační kritérium celé kapitoly. Všimni si, že diagram dodržuje obě obecná omezení: v žádném sloupci (okamžiku) neběží na jednom řádku dvě úlohy a žádná úloha není na dvou řádcích zároveň.
Slovník jedné úlohy: parametry vs. proměnné
Než začneme problémy klasifikovat, potřebujeme slovník pro jednu úlohu $T_j$. Pozor na zásadní dělení (slide 8): parametry jsou dané vstupem, proměnné vznikají až rozvrhem (rozhodne o nich algoritmus).
| Symbol | EN název | Význam | |
|---|---|---|---|
| parametry (vstup) | $r_j$ | release time | okamžik uvolnění — dřív úloha začít nesmí |
| $p_j$ | processing time | doba zpracování | |
| $d_j$ | due date | “time in which task $T_j$ should be completed” — měla by stihnout | |
| $\tilde{d}_j$ | deadline | “time in which task $T_j$ has to be completed” — musí stihnout | |
| proměnné (výstup rozvrhu) | $s_j$ | start time | kdy úloha začne |
| $C_j$ | completion time | kdy úloha skončí | |
| $F_j$ | flow (lead) time | $F_j = C_j - r_j$ — jak dlouho je úloha „v systému“ | |
| $L_j$ | lateness | $L_j = C_j - d_j$ — zpoždění vůči due date | |
| $T_j$ | tardiness | $T_j = \max\{C_j - d_j,\, 0\}$ — jen kladná část zpoždění |
Zkus sám: v diagramu výše je $r_j = 1$, $s_j = 2$, $p_j = 3$, $d_j = 6$, $\tilde{d}_j = 7$. Spočítej $C_j$, $F_j$, $L_j$ a $T_j$. Co je na výsledku $L_j$ zvláštního?
$C_j = s_j + p_j = 5$ (úloha tu běží vcelku); $F_j = C_j - r_j = 4$; $L_j = C_j - d_j = 5 - 6 = \mathbf{-1}$; $T_j = \max\{-1, 0\} = 0$. Lateness může být záporná — úloha skončila dřív, než měla (earliness). Tardiness záporná být nemůže, zápornou část uřízne $\max$. Přesně to říká i poznámka ke slidu 27: “$L_{\max}$ may have negative value. In such case, minimization of lateness $L_{\max}$ may be interpreted as maximization of earliness.”
Nebezpečná polopravda: „due date a deadline je totéž“Není! Due date $d_j$ = úloha by měla skončit do $d_j$ — překročení je povolené a trestá ho až kritérium ($L_{max}$, $\sum w_j T_j$…). Deadline $\tilde{d}_j$ = úloha musí skončit do $\tilde{d}_j$ — překročení znamená nepřípustný rozvrh. Vlnka nad písmenem rozhoduje, jestli jde o měkké přání, nebo tvrdé omezení. Na písemce se obě značky potkávají vedle sebe (např. $1 \,|\, \mathrm{pmtn}, r_j, d_j = \tilde{d}_j \,|\, L_{\max}$ — due dates rovnou v roli deadlines).
Tři pole: $\alpha \,|\, \beta \,|\, \gamma$
Rozvrhovacích problémů jsou stovky — liší se prostředky, pravidly i cílem. Graham pro ně zavedl třípolní klasifikaci (slide 9, EN 1:1): “Classify scheduling problems by resources | tasks | criterion.” Tedy:
$\underbrace{\alpha}_{\text{prostředky — co mám}} \;\Big|\; \underbrace{\beta}_{\text{vlastnosti úloh — jaká pravidla}} \;\Big|\; \underbrace{\gamma}_{\text{kritérium — co minimalizuji}}$
Zkus sám: rozlušti $P2 \,|\, \mathrm{pmtn} \,|\, C_{max}$ — dvě paralelní identická „pécéčka“, něco se smí přerušovat a $C_{max}$ už znáš z Ganttova diagramu. Co celý zápis říká?
Slide 9 doslova: “$P2 \,|\, \mathrm{pmtn} \,|\, C_{\max}$ represents scheduling on two parallel identical resources, and preemption is allowed. The optimization criterion is the completion time of the last task.” Tedy: dva identické paralelní procesory ($\alpha$), preempce povolena ($\beta$), minimalizuj makespan ($\gamma$). Čte se to vždy zleva: co mám / jaká pravidla / co minimalizuji.
Teď jednotlivá pole podrobně — tabulky odpovídají slidům 10–12 a budou ti sloužit jako tahák po celou kapitolu.
$\alpha$ — prostředky (resources)
Pole $\alpha$ má dvě části: $\alpha_1$ = typ prostředků, $\alpha_2$ = počet. Typy se dělí do tří rodin (slide 9): parallel resources (úloha může běžet na kterémkoli prostředku — existuje jediný typ s kapacitou $R$), dedicated resources (úloha smí běžet jen na svém prostředku — $m$ typů s jednotkovou kapacitou) a Project Scheduling ($m$ typů, každý s kapacitou $R_k$ — nejobecnější).
| $\alpha_1$ | Description (slide 10, EN 1:1) | česky |
|---|---|---|
| $1$ | single resource | jediný prostředek |
| $P$ | parallel identical resources | paralelní identické |
| $Q$ | parallel uniform resources, computation time is inversely related to resource speed | paralelní uniformní (různě rychlé) |
| $R$ | parallel unrelated resources, computation times are given as a matrix (resources × tasks) | paralelní nezávislé (matice časů) |
| $O$ | dedicated resources — open-shop — tasks are independent | dedikované, pořadí volné |
| $F$ | dedicated resources — flow-shop — tasks are grouped in the sequences (jobs) in the same order, each job visits each machine once | dedikované, všechny joby stejné pořadí strojů |
| $J$ | dedicated resources — job-shop — order of tasks in jobs is arbitrary, resource can be used several times in a job | dedikované, pořadí per job |
| $PS$ | Project Scheduling — most general (several resource types with capacities, general precedence constraints) | projektové rozvrhování |
$\alpha_2$: prázdné $\emptyset$ = “arbitrary number of resources” (počet je součástí instance), číslo = konkrétní počet (např. $2$), u Project Scheduling ($PS$) $m, R$ = $m$ typů s kapacitami $R$.
Zkus sám: jaký je rozdíl mezi $P$, $P2$ — a co znamená $PS1$, které potkáš na písemce v $PS1 \,|\, temp \,|\, C_{max}$?
$P$ = identické paralelní procesory, jejichž počet je libovolný / součást instance; $P2$ = právě dva. A $PS1$? Theory appendix banky úloh doslova: “project scheduling with one renewable resource of capacity one. In practice for these tasks, this means one resource plus temporal constraints.” Tedy projektové rozvrhování s jediným zdrojem kapacity 1 — v daný okamžik běží nejvýš jedna úloha, ale navíc jsou ve hře temporální vazby (o nich [L5.2] Precedence a temporální omezení; graf TC).
$\beta$ — vlastnosti úloh (tasks)
Prostřední pole je seznam vlastností/omezení; slide 11 je čísluje $\beta_1, \ldots, \beta_8$. Nejdůležitější pro zkoušku:
| $\beta_i$ | Value | Meaning (slide 11, EN 1:1) |
|---|---|---|
| $\beta_1$ | $\mathrm{pmtn}$ / $\emptyset$ | preemption is allowed / preemption is not allowed |
| $\beta_2$ | $\mathrm{prec}$; in-tree, out-tree; chain; tmpn; $\emptyset$ | precedence constraints; tree constraints; chain constraints; temporal constraints (for Project Sched.); independent tasks |
| $\beta_3$ | $r_j$ | release time |
| $\beta_4$ | $p_j = k$; $p_L \le p_j \le p_U$; $\emptyset$ | uniform processing time; restricted processing time; arbitrary processing time |
| $\beta_5$ | $\tilde{d}_j$, $d_j$ | deadline, due-date |
| $\beta_6$–$\beta_8$ | $n_j \le k$; no-wait; set-up | maximal number of tasks in a job; buffers of zero capacity; time for resource reconfiguration |
Dvojí pravopis temporálních omezeníTabulka na slidu 11 píše tmpn, ale konkrétní problémy se v týchž slidech i na písemkách zapisují s temp — např. $PS1 \,|\, temp \,|\, C_{max}$ nebo lakovna $PSm,1 \,|\, \mathrm{temp}, o_{ij}, t_g \,|\, \sum w_j T_j$ ze slidu 4. Je to totéž: temporal constraints mezi starty úloh, $s_i + l_{ij} \le s_j$ (detailně v [L5.2] Precedence a temporální omezení; graf TC).
Zkus sám (klíčová otázka): co znamená, když je pole $\beta$ úplně prázdné — třeba v $P \,||\, C_{max}$?
Prázdné $\beta$ není „žádná informace“ — každá vynechaná položka má svou výchozí hodnotu: preempce zakázána ($\beta_1 = \emptyset$), úlohy nezávislé (žádné precedence), všechny $r_j = 0$ (úlohy jsou v systému od začátku), doby zpracování libovolné, žádné deadlines ani due dates. Dvě svislítka $\|$ v $P \,||\, C_{max}$ tedy nejsou žádný speciální operátor „paralelně“ — jen prázdné prostřední pole.
Vlastnost $\mathrm{pmtn}$ (preemption, preempce = přerušitelnost) si zaslouží obrázek, protože mění i dosažitelné optimum. Slide 7: u nepreemptivního rozvrhování úloha nesmí být pozastavena a dokončena později; u preemptivního smí (počet přerušení musí být konečný). Mini-instance: $R = 2$ procesory, tři úlohy s $p_1 = p_2 = p_3 = 2$ (vlastní ilustrační příklad):
Zkus sám: proč bez preempce nejde na 2 procesorech stihnout tři dvojkové úlohy do času 3?
Práce je celkem $2+2+2 = 6$ jednotek na 2 procesorech, takže $C_{max} \ge 6/2 = 3$. Jenže bez preempce běží každá úloha vcelku: do okna $[0,3]$ se na jeden procesor vejde jen jedna celá dvojková úloha a zbylá jednotka okna propadne — někdo musí mít dvě úlohy za sebou, tj. $C_{max} = 4$. S preempcí rozdělíš $T_3$ na dva jednotkové kusy a dolní mez $3$ se dosáhne. Systematicky tohle „nalévání“ úloh dělá McNaughtonův algoritmus — lekce [L5.4].
$\gamma$ — kritérium (criterion)
| $\gamma$ | Description (slide 12, EN 1:1) |
|---|---|
| $C_{max}$ | minimize schedule length $C_{max} = \max\{C_j\}$ (makespan, i.e. completion time of the last task) |
| $\sum C_j$ | minimize the sum of completion times |
| $\sum w_j C_j$ | minimize weighted completion time |
| $L_{max}$ | minimize max. lateness $L_{max} = \max\{C_j - d_j\}$ |
| $\emptyset$ | decision problem |
Zkus sám: na zkoušce (2023) padl problém $P \,|\, \mathrm{pmtn}, r_j, \tilde{d}_j \,|$ — třetí pole úplně chybí. Co to znamená?
Prázdné $\gamma$ = rozhodovací problém (decision problem): nic se neminimalizuje, ptáme se jen „existuje přípustný rozvrh?“ — tady: lze úlohy s release times a deadlines preemptivně stihnout na $R$ identických procesorech? Přesně tenhle feasibility problém budeme hned v příští lekci [L5.0] Rozvrhování přes toky řešit převodem na maximální tok.
A kontrolní čtení celého zápisu — slide 12 doslova (EN 1:1):
An Example (slide 12)“$P \,||\, C_{\max}$ means: Scheduling on an arbitrary number of parallel identical resources, no preemption, independent tasks (no precedence), tasks arrive to the system at time 0, processing times are arbitrary, objective is to minimize the schedule length.”
Mimochodem — s $P2 \,||\, C_{max}$ ses už potkal: dělení bankovek na dvě hromádky v [L1.1] Cílová funkce a základní omezení je přesně tento problém.
Pozor: $L_{max}$ v $\gamma$ implikuje due dates, i když v $\beta$ nejsouPoznámka ke slidu 27 (EN 1:1): “minimization of $L_{\max}$ implies existence of due-date $d_j$ (even if it is not in $\beta$ notation)”. Takže třeba $1 \,||\, L_{\max}$ má due dates na vstupu — schované v kritériu. Neexistující $d_j$ by dělalo $L_j = C_j - d_j$ nedefinované. Obecně: parametr může do hry vstoupit i přes $\gamma$, nejen přes $\beta$.
Čtecí rutina na písemku
U každého rozvrhovacího zadání proveď stejné tři kroky — nahlas, do řešení se to píše jako „meaning of the notation“:
- $\alpha$ — co mám: kolik a jakých prostředků (1 stroj? $R$ identických? projektový zdroj s kapacitou?).
- $\beta$ — jaká pravidla: smím přerušovat? jsou precedence/temporální vazby? kdy úlohy přicházejí ($r_j$)? do kdy musí/měly by skončit ($\tilde{d}_j$/$d_j$)? Prázdné = defaulty.
- $\gamma$ — co minimalizuji: makespan, (vážené) součty dokončení, max. lateness… Prázdné = jen rozhodnutí o existenci rozvrhu.
Kterým algoritmem se který problém řeší, je druhá půlka příběhu — tu poskládáme postupně a shrneme v referenční tabulce [L5.14]; v zadání zkoušky bývá metoda obvykle předepsaná.
Key takeaways — L5.1- $\alpha\,|\,\beta\,|\,\gamma$ = resources | tasks | criterion. Čteš zleva: co mám / jaká pravidla / co minimalizuji.
- $\alpha$: $1$, $P$ (identické), $Q$ (uniformní), $R$ (unrelated), $O$/$F$/$J$ (dedikované shopy), $PS$ (project scheduling); číslo za písmenem = počet prostředků ($P2$, $PS1$ = 1 zdroj kapacity 1).
- $\beta$: $\mathrm{pmtn}$, $\mathrm{prec}$/in-tree/chain/$temp$ (totéž co tmpn ze slidu 11), $r_j$, $p_j = k$, $\tilde{d}_j$/$d_j$, no-wait, set-up. Prázdné $\beta$ = defaulty: bez preempce, nezávislé úlohy, $r_j = 0$, libovolná $p_j$.
- $\gamma$: $C_{max}$, $\sum C_j$, $\sum w_j C_j$, $L_{max}$; prázdné $\gamma$ = rozhodovací problém (feasibilita). $L_{max}$ implikuje existenci $d_j$, i když v $\beta$ nejsou.
- Parametry vs. proměnné: vstup $r_j$, $p_j$, $d_j$ (should), $\tilde{d}_j$ (has to); výstup rozvrhu $s_j$, $C_j$, $F_j = C_j - r_j$, $L_j = C_j - d_j$ (může být záporná), $T_j = \max\{L_j, 0\}$.
- Gantt chart = standardní zápis rozvrhu: řádek = prostředek, blok = úloha; u preemptivního rozvrhu se táž úloha smí objevit ve více blocích.
Explain the meaning of the notation of the following scheduling problems (one short paragraph each):
(i) $PS1 \mid temp \mid C_{\max}$ (ii) $P2 \mid pmtn, prec \mid C_{\max}$ (iii) $P \mid pmtn, r_j, \tilde{d}_j \mid$
a) Co je v zadání?
Tři reálné zkouškové notace (první dvě jsou přesně problémy z písemek 2.6.2021 — druhý odpovídá úloze Muntz&Coffman z banky #40; třetí je feasibility problém ze zkoušky 2023, který řeší příští lekce). U rozvrhovacích úloh banka řešení vždy začíná odstavcem „Meaning of the notation“ — tohle je trénink přesně toho odstavce.
b) Co k tomu budeme potřebovat?
- Tato lekce — tabulky $\alpha$/$\beta$/$\gamma$ a čtecí rutina.
c) Jak nad úlohou uvažovat?
Jdi pole po poli zleva: identifikuj prostředky (vč. počtu a kapacity), vyjmenuj všechny vlastnosti z $\beta$ (a u prázdných polí řekni defaulty — hlavně preempci!), nakonec kritérium. U (iii) si všimni, že třetí pole je prázdné. U (i) nezapomeň, že ve slovníku této lekce $PS1$ implikuje i nepreemptivnost (v $\beta$ není $\mathrm{pmtn}$) a kapacitu 1.
d) Úplné řešení
(i) — odstavec banky úloh (EN 1:1): “The notation $PS1 \mid temp \mid C_{\max}$ denotes a project-scheduling problem on one resource. The tasks are non-preemptive, so once a task starts, it runs continuously for its processing time. The resource has capacity one, so at most one task can be processed at any time. The symbol $temp$ means temporal constraints between task start times. The objective $C_{\max}$ is the makespan, i.e. the completion time of the last task.”
(ii) — odstavec banky úloh (EN 1:1): “The notation $P2 \mid pmtn, prec \mid C_{\max}$ describes scheduling on two identical parallel processors. The abbreviation $pmtn$ means that preemption is allowed, so a task may be interrupted and later resumed. The abbreviation $prec$ means that the precedence constraints in the graph must be respected. The objective $C_{\max}$ is the makespan, i.e. the completion time of the last task.”
(iii) (řešení vlastní podle tabulek této lekce): $P$ = identické paralelní procesory, počet $R$ je součástí instance; $pmtn$ = preempce povolena; $r_j$ = úlohy mají release times (úloha $T_j$ nesmí začít před $r_j$); $\tilde{d}_j$ = úlohy mají tvrdé deadliny (musí skončit nejpozději v $\tilde{d}_j$). Třetí pole je prázdné — jde o rozhodovací problém: existuje přípustný preemptivní rozvrh, který všechna časová okna $\langle r_j, \tilde{d}_j\rangle$ stihne? (Řeší se převodem na max flow — příští lekce [L5.0] Rozvrhování přes toky.)
Write down the Graham notation $\alpha \mid \beta \mid \gamma$ of each problem described below:
(i) “Scheduling on an arbitrary number of parallel identical resources, no preemption, independent tasks (no precedence), tasks arrive to the system at time 0, processing times are arbitrary, objective is to minimize the schedule length.”
(ii) “scheduling on two parallel identical resources, and preemption is allowed. The optimization criterion is the completion time of the last task.”
(iii) “one machine, release times and deadlines, minimize makespan”
(iv) “one machine, preemption, release times, deadlines/due dates, minimize maximum lateness”
a) Co je v zadání?
Obrácený směr než T01: ze slovního popisu sestavit zápis. Popisy (i)–(ii) jsou doslovné věty ze slidů 12 a 9; (iii)–(iv) jsou doslovné položky „What it means“ z tabulky volby metody v theory appendixu banky — všechny čtyři problémy v kapitole K5 potkáš jako samostatné lekce.
b) Co k tomu budeme potřebovat?
- Tato lekce — tabulky $\alpha$/$\beta$/$\gamma$, defaulty prázdných polí a rozdíl $d_j$ vs. $\tilde{d}_j$.
c) Jak nad úlohou uvažovat?
Z popisu vytahej postupně: typ + počet prostředků → $\alpha$; každou zmíněnou vlastnost (preempce? release times? deadlines — tvrdé, nebo měkké?) → $\beta$; cíl → $\gamma$. Vlastnosti, o kterých popis říká, že jsou „výchozí“ (no preemption, arrive at time 0…), do $\beta$ nepiš — právě tím vznikne prázdné pole.
d) Úplné řešení
(i) $P \,||\, C_{max}$ — vše v popisu kromě „parallel identical“ a „minimize schedule length“ jsou defaulty, takže $\beta$ zůstane prázdné (slide 12).
(ii) $P2 \,|\, \mathrm{pmtn} \,|\, C_{max}$ — dva procesory → $P2$; „completion time of the last task“ = $C_{max}$ (slide 9).
(iii) $1 \,|\, r_j, \tilde{d}_j \,|\, C_{max}$ — „deadlines“ jsou tvrdé → vlnka $\tilde{d}_j$; jeden stroj → $1$. (V K5 ho řeší Bratleyho B&B / position-based ILP — [L5.9].)
(iv) $1 \,|\, \mathrm{pmtn}, r_j, d_j = \tilde{d}_j \,|\, L_{\max}$ — „deadlines/due dates“ v jedné roli zapisuje appendix i slide 27 jako $d_j = \tilde{d}_j$; kritérium max. lateness. (Hornův algoritmus / EDF — [L5.7] EDD a Hornův algoritmus.) Uznatelná je i volnější odpověď $1 \,|\, \mathrm{pmtn}, r_j \,|\, L_{\max}$, pokud due dates bereš jen přes kritérium — vzpomeň: $L_{max}$ existenci $d_j$ implikuje.