Time-indexed ILP pro PS1 |temp| Cmax
V [L5.2] Precedence a temporální omezení; graf TC jsme skončili u špatné zprávy: jakmile zdroj unese jen jednu úlohu najednou, je $PS1 \,|\, temp \,|\, C_{max}$ NP-hard a kladný cyklus už nestačí. Dnes ten problém vyřešíme — přesně, jako ILP. Je to nejdoloženější zkoušková úloha kapitoly: chtěli ji 25. 5. 2026 (oba termíny) i 2. 6. 2021, vždy se stejným zněním „Formulate $PS1\,|temp|\,C_{max}$ problem as a time-indexed ILP.“ Stavebnici binárek $x_{it}$ už máš z [L1.15] Časově/pozičně indexované proměnné — dnes z ní poskládáme celý model.
Dvě cesty k ILP (slide 65)
Slide 65 (EN 1:1) — Task can be represented in two ways- “Time-indexed — ILP model is based on variable $x_{it}$, which is equal to 1 iff $s_i = t$. Otherwise, it is equal to zero. Processing times are assumed to be positive integers.”
- “Relative-order — ILP model is based on the relative order of tasks given by variable $x_{ij}$, which is equal to 1 iff task $T_i$ precedes task $T_j$. Otherwise, it is equal to zero. The processing times are nonnegative real numbers (tasks with zero processing time may be used to represent events).”
- “Both models contain two types of constraints: temporal constraints; resource constraints — prevent overlapping of tasks.”
Pořadové proměnné $x_{ij}$ (relative-order) potkáme u $1\,|\,prec\,|\,\sum w_j C_j$ v [L5.6a] Relative-order ILP pro 1|prec|Σw_jC_j; dnešní lekce je celá o první cestě. Podmínka „processing times are positive integers“ není drobnost: time-indexed model diskretizuje čas na okamžiky $t \in \{0, 1, \ldots, UB-1\}$, takže celočíselné musí být doby $p_i$ i délky hran $l_{ij}$ — jinak by optimum mohlo ležet mimo mřížku.
Poskládej si model sám
Z [L1.15] už umíš celou stavebnici: binárku $x_{it}$, „začíná právě jednou“ $\sum_t x_{it} = 1$, čtení startu $s_i = \sum_t t \cdot x_{it}$ (funguje jen ve dvojici s „právě jednou“!) a zdrojové omezení přes okna startů. Z [L5.2] máš vstup: digraf $G$ temporálních omezení $s_i + l_{ij} \le s_j$.
Zkus sám: napiš temporální omezení hrany $T_i \xrightarrow{l_{ij}} T_j$ pomocí binárek $x_{it}$. A rozmysli, co v modelu PS1 |temp| Cmax ještě pořád chybí.
Dosadíš čtení startu za oba starty:
$$\sum_{t=0}^{UB-1} t \cdot x_{it} \;+\; l_{ij} \;\le\; \sum_{t=0}^{UB-1} t \cdot x_{jt} \qquad \text{pro každou hranu } (i,j) \text{ grafu } G.$$Jedna hrana = jedna lineární nerovnost, žádné big-M. Chybí ještě dvě věci: kritérium (zatím nic neminimalizujeme — $C_{max}$ není proměnná modelu) a horizont $UB$ (bez něj nevíme, kolik binárek vůbec založit).
Zkus sám: kritérium je $C_{max} = \max_i (s_i + p_i)$ — maximum není lineární. Jak se minimalizace maxima linearizuje?
Stejný trik jako u [L1.8] max/min množiny: zaveď novou proměnnou $C_{max}$ a přitlač ji shora na všechny konce:
$$\min C_{max} \qquad \text{s omezeními} \qquad s_i + p_i \le C_{max} \quad \forall i.$$Minimalizace pak sama stáhne $C_{max}$ přesně na největší $s_i + p_i$. V řeči binárek: $\sum_t t \cdot x_{it} + p_i \le C_{max}$.
Zkus sám: navrhni bezpečný horizont $UB$ (horní mez $C_{max}$), když znáš $p_i$ a délky hran $l_{ij}$.
Bezpečné (hrubé) je „všechno popořadě a po každém kroku počkej nejdelší možný odstup“: slide 66 navrhuje
$$UB = \sum_{i=1}^{n} \max\Big\{p_i,\; \max_{i,j \in \{1,\ldots,n\}} l_{ij}\Big\}.$$Každá úloha „spotřebuje“ nejvýš $\max\{p_i, l_{max}\}$ času, než smí odstartovat další. Na verdiktu nezáleží, jestli je $UB$ těsné — jen nesmí být menší než optimální $C_{max}$ (jinak optimum odřízneš). Čím menší ale $UB$ je, tím menší model — viz počítání níže.
Celý model (slide 66 = vzorové zkouškové řešení)
Time-indexed Model for $PS1\,|\,temp\,|\,C_{max}$ (slide 66, EN 1:1)“variables: $x_{it} \in \{0, 1\}$, $C_{max} \in \{0, \ldots UB\}$.
$UB$ — upper bound of $C_{max}$ (e.g. $UB = \sum_{i=1}^n \max\{p_i, \max_{i,j \in \{1, \ldots, n\}} l_{ij}\}$).
Start time of $T_i$ is $s_i = \sum_{t=0}^{UB-1} (t \cdot x_{it})$.
Model contains $n \cdot UB + 1$ variables and $|E| + UB + 2n$ constraints. Constant $|E|$ represents the number of temporal constraints (edges in $G$).”
Čtení po řádcích: zápis „$\forall l_{ij} \ne -\infty$“ je jen slidová konvence pro „pro každou existující hranu grafu $G$“ (neexistenci hrany kóduje $l_{ij} = -\infty$) — temporálních nerovností je tedy $|E|$. Zdrojové omezení sčítá pro každý okamžik $t$ okna startů: úloha $T_i$ v čase $t$ běží, právě když odstartovala v některém $k$ s $t - p_i + 1 \le k \le t$ (ořezáno zdola nulou) — to je přesně okno z [L1.15]. Třetí řádek je „právě jednou“, čtvrtý $C_{max}$.
Nebezpečná polopravda: „$x_{it} = 1$ znamená, že $T_i$ v čase $t$ běží“NE — $x_{it} = 1$ znamená, že $T_i$ v čase $t$ začíná ($s_i = t$); každý řádek tabulky má jen jednu jedničku, i když $p_i = 5$. Kdo to splete, napíše zdrojové omezení jako $\sum_i x_{it} \le 1$ — to ale zakazuje jen společné starty, a úlohy s $p_i > 1$ se vesele překryjí (přesně past z [L1.15]). Vnitřní suma přes okno $k \in \{\max(0, t-p_i+1), \ldots, t\}$ je to, co dělá z tabulky startů hlídač obsazenosti — u zkoušky ji nezapomeň a umět vysvětlit.
Proklikej si všechny čtyři skupiny omezení na instanci ze slidu 67 — $\mathcal{T} = \{T_1, T_2, T_3\}$, $p = (1, 2, 1)$, $UB = 5$:
A dekódování výsledku: solver vrátí jedničky, ty z nich přečteš starty $s_i = \sum_t t \cdot x_{it}$ a nakreslíš Gantt — na jediném zdroji se bloky nesmí překrývat:
Cena modelu: $UB$ je číslo, ne velikost vstupu
Zkus sám: spočítej proměnné a omezení modelu obecně (a ověř na instanci výše: $n = 3$, $UB = 5$, jedna hrana v $G$).
Proměnné: $n \cdot UB$ binárek $x_{it}$ + jedna proměnná $C_{max}$ = $n \cdot UB + 1$. Omezení: $|E|$ temporálních + $UB$ zdrojových (jedno na každý okamžik) + $n$ „právě jednou“ + $n$ pro $C_{max}$ = $|E| + UB + 2n$. Na instanci: $3 \cdot 5 + 1 = 16$ proměnných a $1 + 5 + 6 = 12$ omezení.
Všimni si, že velikost modelu roste s hodnotou $UB$ (tedy s velikostí čísel $p_i$, $l_{ij}$), ne s počtem úloh — stejná „pseudopolynomiální“ daň, jakou platí DP Rothkopf [L5.11]. Proto se vyplatí těsný horizont; a protože $PS1\,|\,temp\,|\,C_{max}$ je NP-hard ([L5.2]; redukcí z $1\,|\,r_j, \tilde{d}_j\,|\,C_{max}$, resp. ze 3-Partition, detail v [L5.13]), nic „chytřejšího“ než ILP + solver se ani nečeká.
Key takeaways — L5.3- Time-indexed model: binárka $x_{it} = 1 \iff s_i = t$ (úloha začíná, ne běží!); čas diskretizovaný na $t \in \{0, \ldots, UB-1\}$, doby $p_i$ kladná celá čísla. Druhá reprezentace = relative-order $x_{ij}$ [L5.6a].
- Čtyři skupiny omezení: ① „právě jednou“ $\sum_t x_{it} = 1$ a čtení startu $s_i = \sum_t t \cdot x_{it}$ [L1.15]; ② temporální $\sum_t t\,x_{it} + l_{ij} \le \sum_t t\,x_{jt}$ pro každou hranu $G$ [L5.2]; ③ zdroj: $\sum_i \sum_{k=\max(0,t-p_i+1)}^{t} x_{ik} \le 1$ pro každý čas $t$ — sčítají se okna startů, ne starty; ④ $\sum_t t\,x_{it} + p_i \le C_{max}$, kritérium $\min C_{max}$.
- Proměnné: $x_{it} \in \{0,1\}$, $C_{max} \in \{0, \ldots, UB\}$; horizont $UB$ = libovolná horní mez $C_{max}$, např. $UB = \sum_i \max\{p_i, \max l_{ij}\}$ — menší než optimum být nesmí.
- Velikost: $n \cdot UB + 1$ proměnných, $|E| + UB + 2n$ omezení — roste s hodnotou $UB$ (pseudopolynomiálně), proto těsný horizont pomáhá.
- Řešení dekóduješ $s_i = \sum_t t \cdot x_{it}$ a kreslíš Gantt; samotný problém je NP-hard [L5.2], time-indexed ILP je pro něj zkouškový standard (tabulka volby metody v [L5.14]).
FOTO checkpoint
zdroj: zkouška 25.5.2026 (oba termíny) + 2.6.2021 = bank #35, EN 1:1
Formulate $PS1\,|temp|\,C_{max}$ problem as a time-indexed ILP.
- Input: The number of non-preemptive tasks $n$ and processing times $[p_1, p_2, \ldots, p_n]$. The temporal constraints defined by digraph $G$.
- Output: $n$-element vector $s$, where $s_i$ is the start time of $T_i$
a) Co je v zadání?
Čistě formulační úloha bez čísel: vypsat kompletní time-indexed ILP — proměnné s doménami, kritérium, všechny čtyři skupiny omezení a říct, co je $UB$ a jak se z jedniček přečte výstup $s$. Žádný běh algoritmu, žádný Gantt; boduje se úplnost a správnost modelu.
b) Co k tomu budeme potřebovat?
- Tato lekce — celý model (takeaways).
- [L1.15] Časově/pozičně indexované proměnné — $x_{it}$, „právě jednou“, čtení startu, okna.
- [L5.2] Temporální omezení — co znamená hrana $l_{ij}$ grafu $G$.
- [L5.1] Grahamova notace — co říká $PS1 \,|\, temp \,|\, C_{max}$.
c) Jak nad úlohou uvažovat?
Piš model v pevném pořadí, ať nic nevypadne: ① proměnné + domény (a hned definuj $UB$), ② kritérium, ③ „$T_i$ is scheduled“, ④ temporální omezení (dosazené čtení startů), ⑤ zdrojové omezení (okna! — u něj čekej doplňující otázku „why?“), ⑥ věta „$s_i = \sum_t t \cdot x_{it}$“ — bez ní jsi formálně nevydal požadovaný výstup $s$. Nakonec se hodí velikost modelu — snadné body navíc.
d) Úplné řešení
Proměnné. $x_{it} \in \{0,1\}$ pro $i \in \{1,\ldots,n\}$, $t \in \{0,\ldots,UB-1\}$, s významem $x_{it} = 1 \iff s_i = t$; a $C_{max} \in \{0, \ldots, UB\}$. Zde $UB$ je libovolná horní mez makespanu, např. $UB = \sum_{i=1}^n \max\{p_i, \max_{i,j} l_{ij}\}$; doby $p_i$ jsou kladná celá čísla (diskretizace času).
Model (= slide 66; dochované vzorové zkouškové řešení z fotek je s ním shodné 1:1):
$$ \begin{aligned} \min \, & C_{max} \\ \sum_{t=0}^{UB-1} (t \cdot x_{it}) + l_{ij} & \le \sum_{t=0}^{UB-1} (t \cdot x_{jt}) && \forall l_{ij} \ne -\infty \text{ a } i \ne j \ \text{(temp. const.)} \\ \sum_{i=1}^{n} \Bigg( \sum_{k = \max(0,\, t - p_i + 1)}^{t} x_{ik} \Bigg) & \le 1 && \forall t \in \{0, \ldots UB - 1\} \ \text{(resource)} \\ \sum_{t=0}^{UB-1} x_{it} & = 1 && \forall i \in \{1, \ldots n\} \ (T_i \text{ is scheduled}) \\ \sum_{t=0}^{UB-1} (t \cdot x_{it}) + p_i & \le C_{max} && \forall i \in \{1, \ldots n\} \end{aligned} $$Komentáře, které u zkoušky řekni nahlas:
- Temp. const.: jedna nerovnost na každou hranu $(i,j) \in E(G)$ — je to $s_i + l_{ij} \le s_j$ z [L5.2] s dosazeným $s_i = \sum_t t\,x_{it}$ ($l_{ij} = -\infty$ značí „hrana neexistuje“).
- Resource: úloha $T_i$ běží v čase $t$ $\iff$ odstartovala v $k \in \{t-p_i+1, \ldots, t\}$ (ořez na $k \ge 0$); součet oken přes všechny úlohy $\le 1$ = kapacita jednoho zdroje. Pouhé $\sum_i x_{it} \le 1$ NESTAČÍ (hlídá jen starty).
- Výstup: $s_i = \sum_{t=0}^{UB-1} t \cdot x_{it}$ — díky „is scheduled“ čte přesně polohu jedničky.
- Velikost: $n \cdot UB + 1$ proměnných, $|E| + UB + 2n$ omezení ($|E|$ = počet temporálních hran).
Pozn. (varianta z banky): horizont jde zúžit per úloha — start $T_i$ má smysl jen pro $t \le UB - p_i$, takže binárky $x_{it}$ s $t > UB - p_i$ lze vynechat (resp. položit 0). Slidová verze s plným rozsahem $t \in \{0,\ldots,UB-1\}$ je u zkoušky plně uznávaná.
FOTO checkpointTohle je doložená zkoušková úloha z 25. 5. 2026 — napiš celý model NA PAPÍR z hlavy (bez koukání do řešení), včetně domén proměnných, definice $UB$, věty o čtení $s_i$ a počtu proměnných/omezení. Pošli mi fotku — zkontroluju ti ji a vytknu chyby (nejčastější: zdrojové omezení bez oken).
Consider the construction-project instance from L5.2 (activities A, B, C, D with $p = (1, 2, 3, 2)$, dummy activities Start and End with $p = 0$, and the temporal-constraint graph with 11 edges: Start→A,B,C,D ($0$), A→B ($+1$), B→A ($-1$), A→C ($+2$), C→D ($+6$), D→C ($-7$), D→End ($+5$), End→Start ($-14$)). Now the activities share a single resource (no two activities may overlap), i.e. solve $PS1\,|temp|\,C_{max}$ by the time-indexed ILP.
(i) Using the generic bound from the lecture, compute $UB$ and the number of variables and constraints of the model.
(ii) Write the temporal constraint for the edge C→D ($l_{CD} = +6$) in terms of the variables $x_{it}$.
(iii) Write the resource constraint for time $t = 2$ (which $x_{ik}$ appear in it?). Show that the earliest-start schedule $s = (0, 1, 2, 8)$ from L5.2 violates it.
(iv) Find an optimal schedule on the single resource and draw its Gantt chart. What is the project duration?
a) Co je v zadání?
Stejný graf TC jako v [L5.2] T02 (limit projektu 14), ale tentokrát s kapacitou zdroje 1 — tedy přesně situace, pro kterou je time-indexed model stavěný. Drilluje se dosazení modelu na konkrétní čísla: velikost, jedna temporální nerovnost, jedno zdrojové omezení a dekódování/oprava rozvrhu.
b) Co k tomu budeme potřebovat?
- Tato lekce — model a počty (takeaways).
- [L5.2] T02 — instance, cykly, nejdřívější starty $s = (0,1,2,8)$.
- [L1.15] — okna startů.
c) Jak nad úlohou uvažovat?
U (i) jen dosazuj: kolik je uzlů včetně dummy aktivit? Jaké je největší $l_{ij}$? U (iii) projdi úlohy jednu po druhé a vypiš okno $k \in \{\max(0, 2-p_i+1), \ldots, 2\}$ — co vyjde pro dummy aktivity s $p = 0$? U (iv) si rozmysli, proč C nemůže začít dřív než v čase 3, když B běží $[s_A+1, s_A+3)$ a zároveň $s_C \ge s_A + 2$.
d) Úplné řešení
(i) Úloh včetně dummy je $n = 6$, největší délka hrany $\max l_{ij} = 6$ (C→D). Obecná mez: $UB = \sum_i \max\{p_i, 6\} = 6 + 6 + 6 + 6 + 6 + 6 = 36$. Model pak má $n \cdot UB + 1 = 6 \cdot 36 + 1 = \mathbf{217}$ proměnných a $|E| + UB + 2n = 11 + 36 + 12 = \mathbf{59}$ omezení. (Těsněji — vlastní úvaha: hrana End→Start ($-14$) dává $s_{End} \le 14$ a přes hrany $D \to End$, $C \to D$, … se pod 14 vejdou všechny starty, takže stačí $UB = 15$ → $91$ proměnných, $38$ omezení. Vidíš, jak horizont škáluje celý model.)
(ii) Hrana C→D ($+6$), tedy $s_C + 6 \le s_D$, po dosazení čtení startů:
$$\sum_{t=0}^{UB-1} t \cdot x_{C,t} \;+\; 6 \;\le\; \sum_{t=0}^{UB-1} t \cdot x_{D,t}.$$(iii) Okna pro $t = 2$: A ($p=1$): $k \in \{2\}$; B ($p=2$): $k \in \{1,2\}$; C ($p=3$): $k \in \{0,1,2\}$; D ($p=2$): $k \in \{1,2\}$; Start a End mají $p = 0$, takže jejich okno $k \in \{3, \ldots, 2\}$ je prázdné — dummy aktivity zdroj nespotřebovávají a v omezení se neobjeví. Celkem:
$$x_{A,2} + x_{B,1} + x_{B,2} + x_{C,0} + x_{C,1} + x_{C,2} + x_{D,1} + x_{D,2} \;\le\; 1.$$Earliest-start rozvrh z [L5.2] má $s_B = 1$ a $s_C = 2$, tedy $x_{B,1} = 1$ a $x_{C,2} = 1$ → levá strana $= 2 > 1$. Porušeno — B běží $[1,3)$ a C $[2,5)$, v čase 2 by na jednom zdroji běžely obě. (V [L5.2] T02 to nevadilo jen díky předpokladu neomezené kapacity.)
(iv) C musí na zdroj počkat, až doběhne B. Celá úvaha (vlastní): C nemůže běžet před B — to by chtělo $s_C + 3 \le s_B = s_A + 1$, tedy $s_C \le s_A - 2$, ve sporu s $s_C \ge s_A + 2$. Takže $s_C \ge s_B + 2 = s_A + 3 \ge 3$, a odtud $s_{End} \ge s_C + 6 + 5 \ge 14$. Rozvrh $s = (s_A, s_B, s_C, s_D) = (0, 1, 3, 9)$, $s_{End} = 14$ všechno splní: $s_B = s_A + 1$ ✓, $s_C = 3 \ge 2$ ✓, $s_D = 9 \in [s_C + 6, s_C + 7] = [9, 10]$ ✓, $s_{End} = 14 \ge s_D + 5$ ✓, limit $14 \le 14$ ✓, žádné překryvy ✓ — je tedy optimální; trvání projektu je přesně 14 (limit max. délky projektu 14 je těsný; poslední skutečná aktivita D končí v čase 11, zbytek do 14 je povinný odstup 3 j. po dokončení D, viz f) z [L5.2]). Proč model nevrátí makespan 11 (konec D), když $C_{max}$ minimalizuje? Protože dummy End je v (i) započítán jako jedna z $n = 6$ úloh, takže do omezení $s_i + p_i \le C_{max}$ vstupuje i $s_{End} + 0 \le C_{max}$ (End má $p = 0$). Deadline-hrana End→Start ($-14$) přitom tlačí $s_{End} = 14$, a tím i $C_{max} \ge 14$. Kritérium modelu: $C_{max} = s_{End} + 0 = 14$.