Precedence a temporální omezení; graf TC
V [L5.1] Grahamově notaci jsme v poli $\beta$ potkali zkratky $\mathrm{prec}$ (precedence) a $temp$ (temporal constraints) — třeba ve zkouškovém problému $PS1 \,|\, temp \,|\, C_{max}$. Tahle lekce vysvětluje, co přesně se za $temp$ skrývá: jak jednou nerovností popsat „B začne přesně 1 po A“, „D nejdřív 3 po dokončení C“ i „celý projekt musí skončit do 12“ — a jak z těchto nerovností sestavit graf temporálních omezení (graf TC), ze kterého feasibilitu přečteš z cyklů. Příští lekce [L5.3] pak nad tímhle grafem postaví time-indexed ILP.
Od precedence k temporálnímu omezení
Precedence constraint (precedenční omezení) $T_i \prec T_j$ znamená: úloha $T_j$ nesmí začít, dokud $T_i$ neskončí. S proměnnými z [L5.1] — start $s_i$, doba zpracování $p_i$ (a tedy konec $C_i = s_i + p_i$ u nepreemptivní úlohy) — to umíš zapsat sám:
Zkus sám: zapiš $T_i \prec T_j$ jako jednu nerovnost mezi starty $s_i$ a $s_j$.
$T_j$ smí začít až po konci $T_i$: $\;C_i \le s_j$, tedy $s_i + p_i \le s_j$. Všimni si tvaru: start plus nějaká konstanta $\le$ druhý start. Když konstantu pustíme z $p_i$ na libovolné číslo $l_{ij}$ (klidně nulu nebo záporné!), dostaneme přesně temporální omezení — precedence je jen jeho speciální případ $l_{ij} = p_i$.
Definice — Temporal Constraints (slide 59 + 60, EN 1:1)- “Set of non-preemptive tasks $\mathcal{T} = \{T_1, T_2, \ldots, T_n\}$ is represented by the nodes of the directed graph $G$ (may include negative cycles).”
- “Processing time $p_i$ is assigned to each task.”
- “The edges represent temporal constraints. Each edge from $T_i$ to $T_j$ has the length $l_{ij}$.”
- “Each temporal constraint is characterized by one inequality $\;s_i + l_{ij} \le s_j$.”
- Jiná jména (slide 60): generalized precedence constraint (zobecněná precedence), positive-negative time lag.
Klíčový posun oproti obyčejné precedenci: nerovnost svazuje starty, ne konec s počátkem, a délka hrany $l_{ij}$ je libovolné číslo — kladné, nulové i záporné. Takhle vypadá příklad ze slidu 59 (5 úloh, jedna hrana záporná) i s přípustným rozvrhem:
Zkus sám: ověř v rozvrhu nahoře hrany $T_4 \to T_5$ ($l_{45}=4$) a $T_5 \to T_1$ ($l_{51}=-10$). Která je „těsná“?
$T_4 \to T_5$: $s_4 + 4 = 6 + 4 = 10 \le s_5 = 10$ ✓ — těsná (proto $T_5$ nemůže začít dřív). $T_5 \to T_1$: $s_5 - 10 = 0 \le s_1 = 0$ ✓ — také těsná! Záporná hrana čteno po lidsku: $T_1$ smí začít nejvýš 10 po startu $T_5$, ekvivalentně $T_5$ musí začít nejpozději 10 po startu $T_1$ — drží konec rozvrhu „u země“. Kdyby $s_5 = 11$, omezení by spadlo: $11 - 10 = 1 \not\le 0$.
Katalog: co všechno $l_{ij}$ umí (slidy 60–63)
Slidy třídí temporální omezení podle vztahu $l_{ij}$ k $p_i$. Nejdřív otázka na záporný případ — ten je na písemce nejdůležitější:
Zkus sám: co po lidsku říká hrana $T_i \to T_j$ se záporným $l_{ij}$, třeba $l_{ij} = -2$?
$s_i - 2 \le s_j$, tedy $s_i \le s_j + 2$: úloha $T_i$ musí začít nejpozději 2 po startu $T_j$ (klidně i dřív). Slide 63 (EN 1:1): “Task $T_i$ has to start earlier or at most $|l_{ij}|$ later than $T_j$. It loses the sense of normal precedence relation, since $T_i$ does not have to precede $T_j$. It represents the relative deadline of $T_i$ related to the start-time of $T_j$.” Záporná hrana = relativní deadline, žádné pořadí nevynucuje.
| případ | vztah | Meaning (slidy 60–63, EN 1:1) | příklad ze slidů |
|---|---|---|---|
| a) | $l_{ij} = p_i$ | “normal” precedence relation — “the second task can start when the previous task is finished” | běžná technologická návaznost |
| b) | $l_{ij} > p_i$ | “the second task can start some time after the completion of previous task” | paint → dry → pack; pipelined ALU |
| c) | $0 < l_{ij} < p_i$ | “Partial results of the previous task may be used to start the execution of the following task.” | cut-through switch (zpráva se posílá dál, než celá dorazí) |
| d) | $l_{ij} = 0$ | “Task $T_i$ has to start earlier or at the same time as $T_j$” | synchronizované starty |
| e) | $l_{ij} < 0$ | “relative deadline of $T_i$ related to the start-time of $T_j$” | katalyzátor, deadliny |
Proklikej si všech pět případů na časové ose ($T_j$ kreslíme vždy v nejdřívějším povoleném startu — nerovnost dovoluje i pozdější):
Relativní časové okno: dvojice hran tam a zpět
Zajímavé věci začnou, když mezi dvěma úlohami vedou hrany oběma směry. Slide 64 dává příklad nasazení katalyzátoru v chemickém procesu: $l_{12} = 2$ a $l_{21} = -3$.
Zkus sám: napiš obě nerovnosti pro $l_{12} = 2$, $l_{21} = -3$ a vyjádři, co plyne pro rozdíl $s_2 - s_1$.
$s_1 + 2 \le s_2$ a $s_2 - 3 \le s_1$, dohromady $\;2 \le s_2 - s_1 \le 3$. Úloha $T_2$ musí začít mezi 2 a 3 po startu $T_1$ — slide 64 tomu říká relative time window (relativní časové okno). A doslova (EN 1:1): “If finite $l_{ij} \ge 0$ and $l_{ji} < 0$ do exist, tasks $T_i$ and $T_j$ are constrained by the relative time window. The length of the negative cycle determines the ‘clearance’ of the time window.” Tady cyklus $T_1 \to T_2 \to T_1$ má délku $2 + (-3) = -1$ → vůle okna je $1$.
Kdy rozvrh existuje? Rozhodne kladný cyklus
U okna výše vyšel cyklus záporný a vše fungovalo. Co kdyby vyšel kladný — třeba $l_{12} = 4$ a $l_{21} = -3$?
Zkus sám (klíčová otázka): sečti nerovnosti $s_i + l_{ij} \le s_j$ podél libovolného cyklu v grafu $G$. Co dostaneš?
Každý start se na levé i pravé straně objeví právě jednou, takže se všechny vykrátí a zbude $\;\sum_{\text{cyklus}} l_{ij} \le 0$: délka každého cyklu musí být $\le 0$, jinak dostaneš spor typu $s_1 + 1 \le s_1$. Pro dvojici $4$ / $-3$: $s_2 \ge s_1 + 4$ a zároveň $s_2 \le s_1 + 3$ — prázdné okno, rozvrh neexistuje. Kladný cyklus = certifikát nerozvrhnutelnosti. Nulový cyklus je v pořádku — vynucuje rovnost (přesně tak modelujeme „starts exactly…“).
Schedulability (slide 64, EN 1:1)“Absence of a positive cycle in graph $G$
- is a necessary condition for schedulability of $PS1 \,|\, temp \,|\, C_{max}$,
- is a necessary and sufficient condition for schedulability of the instance with unlimited capacity of resources. The schedule, which is restricted only by the temp. constraints, can be found in pol. time — by LP, or by the longest paths.”
K nejdelším cestám slide dodává: pro $G$ sestrojíme $G'$, “a complete digraph of longest paths”, kde váha $l'_{ij}$ = délka nejdelší orientované cesty z $T_i$ do $T_j$ v $G$ (neexistuje-li cesta, $l'_{ij} = -\infty$); pak “a start time of $T_j$ is lower bounded by the longest path from arbitrary node, i.e. $s_j \ge \max_{\forall i} l'_{ij}$.”
Intuice: každá orientovaná cesta do $T_j$ je řetěz nerovností, který se sečte na $s_i + (\text{délka cesty}) \le s_j$ — start tlačí nahoru ta nejdelší z nich. Nejdřívější starty = nejdelší cesty z počátečního uzlu; a nejdelší cesty s detekcí kladného cyklu spočítáš Bellman-Fordem z [L2.12] Bellman-Ford + detekce záporného cyklu — stačí otočit znaménka vah ($l \to -l$): nejdelší cesta se stane nejkratší a kladný cyklus záporným cyklem, který B-F umí ohlásit.
Nebezpečná polopravda: „špatný je záporný cyklus“U nejkratších cest v K2 škodil záporný cyklus. Tady jsme ale ve světě nejdelších cest (omezení tlačí starty nahoru) — škodí KLADNÝ cyklus; záporné cykly jsou naopak užitečné (relativní okna — slide 59 výslovně píše „may include negative cycles“) a nulový cyklus vynucuje rovnost startů. Na otázku „Is this instance schedulable? Why?“ odpovídej přes (ne)existenci kladného cyklu.
Druhá půlka pravdy: bez kapacitního omezení je absence kladného cyklu i postačující, ale jakmile zdroj unese jen jednu úlohu najednou ($PS1$), je to jen podmínka nutná — úlohy se navíc nesmí překrývat a problém je NP-hard (slide 54). Proto se $PS1 \,|\, temp \,|\, C_{max}$ řeší time-indexed ILP — příští lekce [L5.3].
Graf TC ze slovního zadání: dummy Start a End
Zkouškové zadání nedává hrany — dává věty („B must start exactly 1 time unit after start of A“, „the maximum duration of the project is 12“). Recept na převod:
- Uzly = aktivity; přidej dummy (fiktivní) uzly Start a End s $p = 0$ (začátek a konec projektu) — přesně to radí zkouškový hint: “Add ‘dummy’ activities with zero duration for beginning and end of the project.”
- Každou větu přepiš na nerovnost tvaru $s_i + l_{ij} \le s_j$ → jedna hrana. Věta s „exactly“ = rovnost = dvě hrany ($+l$ tam, $-l$ zpět — nulový cyklus).
- Pozor na slova „completion / after the completion“: měří se od konce úlohy, takže ke zpoždění přičti $p_i$ (start + $p_i$ + odstup).
- Start „drž“ hranami $Start \to T_j$ s $l = 0$ (nic nezačne před projektem) — release time $r_j$ by dal hranu s $l = r_j$; konec projektu hranami $T_j \to End$ s $l = p_j$ (vše musí doběhnout).
Zkus sám: jak jednou hranou zakódovat „maximální délka projektu je 12“?
Chceme $s_{End} \le s_{Start} + 12$. Převedeno na povinný tvar $s_i + l \le s_j$: $\;s_{End} + (-12) \le s_{Start}$ — tedy zpětná hrana $End \to Start$ s délkou $-12$. Horní mez (deadline) vždy vyrobí zápornou hranu v protisměru. A hned vidíš mechaniku feasibility: cesta $Start \rightsquigarrow End$ delší než 12 spolu s touto hranou uzavře kladný cyklus.
Nejčastější chyba: směr záporné hrany„$T_j$ nejpozději $k$ po $T_i$“ je $s_j \le s_i + k$, tedy hrana $T_j \to T_i$ s $l = -k$ — z $T_j$ do $T_i$, ne naopak! Mnemotechnika: nerovnost si vždy nejdřív napiš, pak ji mechanicky srovnej do tvaru $s_{\text{odkud}} + l \le s_{\text{kam}}$ — levý index = odkud hrana vede, pravý = kam. Kdo kreslí hrany „po směru času“ i pro deadliny, vyrobí nesmyslný graf.
Stejným receptem funguje i redukce $1 \,|\, r_j, \tilde{d}_j \,|\, C_{max} \to PS1 \,|\, temp \,|\, C_{max}$ (dummy $T_0$, hrany $r_i$ tam a $-(\tilde{d}_i - p_i)$ zpět) — jen zmínka, detail v [L5.13]. Obyčejný precedenční graf (jen hrany $l_{ij} = p_i$, případně bez vah u Muntze&Coffmana [L5.10]) je speciální případ grafu TC.
Key takeaways — L5.2- Temporální omezení (generalized precedence / positive-negative time lag) = jedna nerovnost $s_i + l_{ij} \le s_j$ = jedna hrana $T_i \to T_j$ délky $l_{ij}$ v digrafu $G$. Běžná precedence $T_i \prec T_j$ je speciální případ $l_{ij} = p_i$.
- Katalog $l_{ij}$: $= p_i$ precedence; $> p_i$ odstup po dokončení (dry); $0 < l < p_i$ částečné výsledky (cut-through); $= 0$ start nejpozději zároveň; $< 0$ relativní deadline. Dvojice $l_{ij} \ge 0$, $l_{ji} < 0$ = relativní časové okno; vůle okna = |délka záporného cyklu|.
- Stavba grafu TC: uzly = úlohy + dummy Start/End s $p=0$; každá věta zadání = jedna nerovnost = jedna hrana („exactly“ = dvě hrany); „po dokončení“ = přičti $p_i$; horní mez (deadline, max. délka projektu $D$) = záporná hrana v protisměru (např. $End \to Start$ s $-D$).
- Rozvrhnutelnost: součet nerovností podél cyklu dá $\sum l \le 0$ ⟹ kladný cyklus = instance NENÍ rozvrhnutelná (nutná podmínka; bez kapacitního omezení i postačující). Nejdřívější starty $s_j$ = nejdelší cesty ze Startu; výpočet/detekce Bellman-Fordem na $-l$ [L2.12].
- S kapacitou zdroje ($PS1 \,|\, temp \,|\, C_{max}$) je absence kladného cyklu jen nutná — problém je NP-hard a řeší se time-indexed ILP [L5.3].
A construction company has obtained a contract on a project consisting of 4 non-preemptive activities A, B, C and D. The following temporal constraints apply:
a) Activity durations are $p_A = 1$, $p_B = 2$, $p_C = 3$ and $p_D = 2$.
b) B must start exactly 1 time unit after start of A.
c) C can start at least 2 time units after start of A.
d) After the completion of C, there are at least 3 more time units before D can start.
e) D can be started not later than 7 units after start of C.
f) We suppose that the project can be terminated 3 time units after the completion time of D.
g) The maximum duration of the project is 12 time units.
a) Draw a directed graph with temporal constraints for this problem.
b) Is this instance schedulable? Why?
Hint: Add “dummy” activities with zero duration for beginning and end of the project.
a) Co je v zadání?
Stavební projekt se 4 nepreemptivními aktivitami a sedmi větami-omezeními: jedna rovnost („exactly“), dolní odstupy (z toho jeden „after the completion“ — pozor na $p_C$), jedna horní mez mezi aktivitami a jedna horní mez na délku celého projektu. Úkol (a) chce graf TC, úkol (b) verdikt o rozvrhnutelnosti se zdůvodněním.
b) Co k tomu budeme potřebovat?
- Tato lekce — recept na stavbu grafu (dummy Start/End, „exactly“ = 2 hrany, „completion“ = +$p_i$, horní mez = záporná hrana) a kritérium kladného cyklu (takeaways).
- [L5.1] Grahamova notace — parametry $p_j$, proměnné $s_j$.
- [L0.4] Strom, kostra, les, DAG — orientovaný cyklus.
c) Jak nad úlohou uvažovat?
Každou větu b)–g) přepiš nejdřív na nerovnost mezi starty (u f) a g) použij dummy uzly), teprve pak ji srovnej do tvaru $s_i + l \le s_j$ a zakresli hranu. U d) nezapomeň, že „after the completion of C“ znamená $s_C + p_C + 3$. U g) si rozmysli, mezi kterými uzly a kterým směrem hrana povede. Pro (b) pak hledej kladný cyklus — kde se může vzít? Jedině přes jedinou „velkou“ zápornou hranu.
d) Úplné řešení
(a) Stavba grafu. Překlad vět na nerovnosti a hrany (Start a End jsou dummy aktivity s $p = 0$; $s_{Start} = 0$):
| věta | nerovnost | hrana (délka) |
|---|---|---|
| b) „exactly 1 after start of A“ | $s_A + 1 \le s_B$ a $s_B - 1 \le s_A$ | $A \to B$ ($+1$), $B \to A$ ($-1$) |
| c) „at least 2 after start of A“ | $s_A + 2 \le s_C$ | $A \to C$ ($+2$) |
| d) „completion of C + at least 3“ | $s_C + \underbrace{3}_{p_C} + 3 \le s_D$ | $C \to D$ ($+6$) |
| e) „not later than 7 after start of C“ | $s_D - 7 \le s_C$ | $D \to C$ ($-7$) |
| f) „terminated 3 after completion of D“ | $s_D + \underbrace{2}_{p_D} + 3 \le s_{End}$ | $D \to End$ ($+5$) |
| g) „maximum duration 12“ | $s_{End} - 12 \le s_{Start}$ | $End \to Start$ ($-12$) |
| dummy | $s_{Start} + 0 \le s_X$ pro $X \in \{A,B,C,D\}$ | $Start \to X$ ($0$) |
Proklikej si stavbu (krok 8 = odpověď na (b)):
Pozn.: pro úplnost lze přidat i hrany $A \to End$ ($+1$), $B \to End$ ($+2$), $C \to End$ ($+3$) — „každá aktivita skončí před koncem projektu“. Verdikt nezmění (nejdelší je stejně větev přes D), v obrázku je kvůli čitelnosti vynecháváme; ruční zkouškové řešení je také nemá. Hodnoty hran v dochovaném ručním řešení jsou zčásti nečitelné/přeškrtané — tabulka výše je vlastní pečlivé odvození z definice $s_i + l_{ij} \le s_j$.
(b) Is this instance schedulable? — NE. V grafu je kladný cyklus
$Start \xrightarrow{0} A \xrightarrow{+2} C \xrightarrow{+6} D \xrightarrow{+5} End \xrightarrow{-12} Start$, délka $\;0 + 2 + 6 + 5 - 12 = \mathbf{+1} > 0,$
a součet nerovností podél něj dá spor $s_{Start} + 1 \le s_{Start}$. Ekvivalentně přes nejdelší cesty: nejdřívější starty jsou $s_A = 0$, $s_B = 1$, $s_C = 2$, $s_D = s_C + 6 = 8$ a $s_{End} = s_D + 5 = 13$ — projekt nejde stihnout dřív než za 13 > 12 časových jednotek, omezení g) nelze splnit. (Okno mezi C a D je přitom v pořádku: cyklus $C \to D \to C$ má délku $6 - 7 = -1 \le 0$.) Ruční zkouškové řešení dochází ke stejnému verdiktu (✗).
Consider the instance from T01 with constraint g) relaxed to: “The maximum duration of the project is 14 time units.” Assume unlimited capacity of resources (activities may run in parallel).
(i) List all directed cycles in the temporal-constraint graph and compute their lengths. Is the instance schedulable now?
(ii) Compute the earliest start time of every activity (longest paths from Start) and the earliest project completion.
(iii) Draw the Gantt chart of the earliest-start schedule.
(iv) What is the relative time window for the start of D (relative to the start of C), and what is its “clearance”?
a) Co je v zadání?
Stejný graf TC jako v T01, jen zpětná hrana $End \to Start$ má nově délku $-14$. Drilluje se kompletní rutina: cykly → verdikt, nejdelší cesty → nejdřívější starty, rozvrh → Gantt, dvojice hran tam/zpět → okno. Předpoklad neomezené kapacity je tu klíčový — právě pro něj je „žádný kladný cyklus“ i postačující podmínka.
b) Co k tomu budeme potřebovat?
- Tato lekce — kritérium kladného cyklu, nejdřívější starty = nejdelší cesty, relativní okno (takeaways).
- [L2.12] Bellman-Ford — kdyby cyklů bylo moc na ruční výčet.
- [L5.1] — Gantt chart.
c) Jak nad úlohou uvažovat?
Cykly hledej přes záporné hrany — jiné se uzavřít nemohou (proč?). Nejdřívější starty počítej topologicky „zleva“: $s_X = \max$ přes vstupní hrany ($s_i + l_{iX}$); záporné hrany pak už jen zkontroluj. V Ganttu se aktivity smí překrývat (neomezená kapacita!) — každé dej vlastní řádek.
d) Úplné řešení
(i) Každý cyklus musí použít aspoň jednu zápornou hranu ($B \to A$, $D \to C$, nebo $End \to Start$ — kladné hrany vedou „zleva doprava“ a samy se neuzavřou). Cykly jsou tři:
- $A \to B \to A$: $\;1 + (-1) = 0$ — nulový, vynucuje rovnost $s_B = s_A + 1$ („exactly“),
- $C \to D \to C$: $\;6 + (-7) = -1$ — záporný (relativní okno),
- $Start \to A \to C \to D \to End \to Start$: $\;0 + 2 + 6 + 5 - 14 = \mathbf{-1}$ — záporný (v T01 byl $+1$).
Žádný kladný cyklus + neomezená kapacita ⟹ instance JE rozvrhnutelná.
(ii) Nejdelší cesty ze Startu ($s_{Start} = 0$): $s_A = 0$; $s_B = s_A + 1 = 1$; $s_C = s_A + 2 = 2$; $s_D = s_C + 6 = 8$; $s_{End} = s_D + 5 = 13$. Kontrola záporných hran: $s_B - 1 = 0 \le s_A$ ✓ (těsně, rovnost platí), $s_D - 7 = 1 \le s_C = 2$ ✓, $s_{End} - 14 = -1 \le 0$ ✓. Nejdřívější konec projektu = 13 ≤ 14.
(iii) Gantt (každá aktivita na svém řádku, B a C se překrývají — to neomezená kapacita dovoluje):
(iv) Hrany $C \to D$ ($+6$) a $D \to C$ ($-7$) dávají $\;s_C + 6 \le s_D \le s_C + 7$: D smí začít mezi 6 a 7 po startu C (zde $[8, 9]$). Vůle (clearance) okna = |délka záporného cyklu| $= |{-1}| = 1$.