Omezující podmínky (pokračování)
14. března 2022
Q Problém splňování podmínek
Q Rozvrhování jako problém splňování podmínek
Q Podmínky pro zdroje
Prohledávání/přiřazování
Konzistenční techniky jsou (obvykle) neúplné =4> potřeba prohledávací algoritmus, který vyřeší "zbytek"
• př. X in 1..2, Y in 1..2, Z in 1..2, X^Y, Y^Z, X^Z AC neodstraní žádnou hodnotu ale problém je nekonzistentní
Přiřazovaní (labeling)
• prohledávání do hloubky (DFS/BT)
přiřaď hodnotu do proměnné
• propaguj = udělej problém lokálně konzistentní
• vrať se v případě neúspěchu
• X in 1..5    =    X=l V X=2 V X=3 V X=4 V X=5
Obecně: prohledávací algoritmus řeší zbylé disjunkce o X=l V X^l       standardní přiřazování
• X<3 V X>3       dělení domén
• X<Y V X>Y      uspořádání proměnných
Hana Rudová, Fl MU: Omezující podmínky (pokračování) 2 14. března 2022
O oo oo oo o
Kostra ohodnocování
• Prohledávání do hloubky je kombinováno s AC, které omezuje prohledávaný prostor
• Technika pohledu dopředu (MAC)
• procedure labeling(V,D,C)
if (všechny proměnné z V přiřazeny) then return V vyber dosud nepřiřazenou proměnnou x z V for (každou hodnotu v z Dx) do
(TestOk.D') := consistent(V,D,C U {x=v})
if TestOk=true then R := labeling(V,D\C)
if R^fail then return R return fail end labeling
• Před labeling je spuštěn iniciální běh konzistenčních algoritmů, aby byla zajištěna iniciální konzistence
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
3
14. března 2022
Rozvrhování jako CSP: čas
Aktivita A: entita vyžadující prostor (zdroje) a čas
Proměnné a jejich domény pro časové přiřazení aktivity
• start(A): startovní čas aktivity
• aktivita nemůže začít před svým termínem dostupnosti
• est(A) = min(start(A)), earliest start time/nejdřívější startovní čas
• end(A): čas skončení aktivity
• aktivita musí skončit před svým deadline
• lct(A) = max(end(A)), latest completion time/nejpozdější koncový čas
• p(A): doba provádění aktivity
• start(A) = {est(A), ..., (lct(A)-p(A))} o end(A) = {(est(A)+p(A)), ..., lct(A)}
est(A)
P(A)
lct(A)
time
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
4
14. března 2022
Rozvrhování jako CSP: základní omezení I.
• Nepřerušitelná aktivita: žádné přerušení během jejího zpracování • start(A) + p(A) = end(A)
p(A)
start(A)
end(A) time
012345678   9 10
Přerušitelná aktivita: může být přerušena během svého zpracování 9 start(A) + p(A) < end(A)
A[l]		\[2	]	A[3]		A[4]
í
start(A)
end(A)
time ->■
0123456789 10 11 12 p(A) = p(A[l]) + p(A[2]) + p(A[3]) + p(A[4])
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
5
14. března 2022
Rozvrhování jako CSP: základní omezení II.
o Seřazení A<<B aktivity A,B
(také: precedenční omezení mezi aktivitami A,B)
9 end(A) < start(B)
A		B	time	
0  1  2  3  4 5	i  6 "	7  8  9 10		
• Disjunktivní omezení: nepřekrývání aktivit A a B
• nepřerušitelné aktivity
• A<<B or B<<A
• end(A) < start(B) or end(B) < start(A)
• viz dále unární zdroje
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
6
14. března 2022
Rozvrhování jako CSP: zdroje
Doménové proměnné pro zdroje:
• cap(A): požadovaná kapacita zdroje aktivitou A
• unární/disjunktivní zdroje
v daném čase může být zpracována maximálně jedna aktivita
• kumulativní zdroje
• několik aktivit se může zpracovávat paralelně, ovšem za předpokladu, že není překročena kapacita zdroje
• produkovatelné/spotřebovatelné zdroje
• aktivita konzumuje (snižuje) nebo produkuje (navyšuje) aktuální množství zdroje
• na zdroji musí zbýt nějaká minimální volná kapacita a maximální kapacita zdroje nemůže být překročena
• příklad: reservoár
• resource(A): alternativní zdroje pro A
• pro zpracování A vybereme jeden z alternativních zdrojů
• jednotlivé hodnoty z domény resource(A) odkazují na konkrétní zdroje
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
7
14. března 2022
Značení
Ist(A) lct(A)
est(A) ect(A)
9 est(A) nejdřívějsí startovní čas aktivity A (earliest start time)
• ect(A) nejdřívějsí koncový čas aktivity A (earliest completion time)
• Ist(A) nejpozdější startovní čas aktivity A (latest start time)
9 lct(A) nejpozdější koncový čas aktivity A (latest completion time)
• Q je množina aktivit
• P(fi) = EAen P(A)
• est (Q) = m\n{est(A) \A<=Q.}
• /ct(fi) = max{lct(A) | A e Q}
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
8
14. března 2022
Unární zdroje
• Aktivivity se nemohou překrývat
a v daném čase běží maximálně jedna aktivita, proto se těmto zdrojům říká unární
• Grahamova klasifikace: jeden stroj
• Předpokládáme, že aktivity jsou nepřerušitelné
• nepřerušitelná aktivita zabírá zdroj od svého startu až do ukončení 9 Jednoduchý model s disjunktními omezeními
• A<<B V B<<A end(A)<start(B) V end(B)<start(A)
• těmto zdrojům se proto někdy říká disjunktní
D
B
time
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
9
14. března 2022
Hledání hran (edge finding)
• Baptisté & Le Pape (1996)
• Co se stane, pokud nebude aktivita A zpracována jako první?
16
A(
B(4)
16
7
C(5)
15
Pro A,B,C není dost času, a tedy aktivita A musí být první
4|—| A(2) W 7 6hi"
B(4)
16
7
C(5)
15
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
10
14. března 2022
Hledání hran: příklad s odvozovacími pravidly
lct(Q U {A}) - esf(ft) < p(fi U {A}) =>- A « Q
16
A(
Q = {B, C}
B(4)
16
7
C(5)
15
• >4 « íí =>■ end(A) < min{/ct(Q/) - p(ft') | Q' C Q}
všechny podmnožiny Q. musí stihnout své zpracování
4 \~\ A(2) H 7 6h-U
B(4)
16
C(5)
115
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
11
14. března 2022
Hledání hran: všechna odvozovací pravidla
• Zopakujme tedy odvozovací pravidla: pro end(A)
(co se stane, pokud nebude aktivita A zpracována jako první?)
• lct(Q U {A}) - esŕ(ft) < p(ft U {A})
^A«Q
• A « Q
end(A) < min{/cŕ(ft') - p(ft') | Q/ C Q}
• Symetrická odvozovací pravidla: pro start(A)
(co se stane, pokud nebude aktivita A zpracována jako poslední?)
• /cŕ(ft) - esŕ(ft U {A}) < p(ft U {A})
Q << A
• Q << A
start(A) > max{esŕ(ft') + p(ft') | Q/ C Q}
• V praxi:
o celkem existuje n-2n párů A,Q (příliš mnoho!)
• Carlier & Pinson 1994, Vilím & Barták & Čepek 2004
algoritmus s časovou složitostí 0(nlogA7)
(je nutné kontrolovat pouze některé páry A,Q)
Hana Rudová, Fl MU: Omezující podmínky (pokračování) 12 14. března 2022
Ne-první/ne-poslední (not-first/not-last)
• Torres & Lopez 2000
• Co se stane, pokud aktivita A bude zpracována jako první?
A(2)
116
B(5)
J15 16
C(4)
4|-i-
Pro B a C není dost času, a tedy aktivita A nemůže být první
8
A(2)
16
B(5)
15
C(4)
16
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
13
14. března 2022
Ne-první/ne-poslední: př. s odvozovacími pravidly
o p(Q U {A}) > /ct(ft) - est(A) =>- -1/4 << Q
A(2)
16
Q = {B, C}
7
B(5)
4h
^15 16
C(4)| |
• ^A«Q^ start(A) > m\n{ect(B)\B e Q}
8
A(2)
16
B(5)
15
C(4)
16
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
14
14. března 2022
Odvozovací pravidla pro ne-první/ne-poslední
• Zopakujme Ne-první pravidla:
(co se stane, pokud aktivita A bude zpracována jako první?)
• /cŕ(ft) - est(A) < p(Q U {A})
• -VI << ft start(A) > min{ecŕ(6)|e G Q}
• Ne-poslední (symetrická) pravidla:
(co se stane, pokud aktivita A bude zpracována jako poslední?)
• lct(A) - esŕ(ft) < p(Q U {A})
^^Q«A
• -nft << A
end (A) < max{/sŕ(B)|B G Q}
• V praxi:
• Vilím 2004: algoritmus s časovou složitostí 0(nlogA7)
Hana Rudová, Fl MU: Omezující podmínky (pokračování) 15 14. března 2022
Produkovatelné/spotřebovatelné zdroje
• Zdroj = rezervoár
• Aktivita konzumuje nějaké množství zdroje cap(A)<0 nebo aktivita produkuje nějaké množství zdroje cap(A)>0
• Požadována minimální kapacita zdroje (při konzumaci)
a maximální kapacita zdroje nemůže být překročena (produkcí)
9 Kumulativní zdroj může být chápan jako speciální případ rezervoáru
• každá aktivita konzumuje cap(A) při startu a produkuje cap(A) na konci
Hana Rudová, Fl MU: Omezující podmínky (pokračování) 16 14. března 2022
Relativní uspořádání
• Pokud je čas relativní (uspořádání aktivit)
potom techniky edge finding a agregovaných požadavků nic neodvodí
• Pořád ale můžeme používat informace o uspořádání aktivit a spotřebě/produkci daného zdroje
• Příklad:
reservoár: aktivity konzumují a produkují zdroj
'Ä
ze odvodit nezbytnost přídavné aktivity produkující jednotku zdroje
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
17
14. března 2022
Optimistický zdrojový profil (orp)        Cesta&Steiia 1997
orp(A): maximálni možná úroveň zdroje v čase, kdy se A začne zpracovávat
Aktivity, které musí být před A, se vezmou dohromady s produkčními aktivitami, které mohou být před A
orp(A) = InitLevel + cap(A) + Y,b«a c3p(b) + Ee??/\^caP(e)>o caP(e) Příklad (opravdu pouze příklad jsou i jiné možnosti!):
orp(A)
cap(B): all B with B??A and cap(B)>0
cap(B): all B with B<<A
cap(A)
InitLevel
Bil A znamená, že pořadí A a B ještě není známé
Hana Rudová, Fl MU: Omezující podmínky (pokračování) 18
14. března 2022
orp odvozovací pravidla I.
orp(A) < MinLevel =4> fail
• i když je veškerá produkce plánována před A
není dosažena minimální požadovaná úroveň zdroje
-1-orp(A)
cap(B): all B with B??A and cap(B)>0
1 cap(B): all B with B<<A
é cap(A) -1- InitLevel
orp(A) = InitLevel + cap(A) + J2b«a cap(B) + Ee??y\&caP(B)>o cap(B)
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
19
14. března 2022
orp odvozovací pravidla II.
orp(A) - cap(D) - Eo«e        &caP(£)>o cap(B) < MinLevel D « A
Uvažujme časový okamžik, kdy začne aktivita A 9 pro libovolné D takové, že Dli A a cap(D) > 0:
pokud je produkce v D plánována za A a minimální požadovaná úroveň zdroje není dosažena, pak musí být D před A
Příklad:
orp(A)
cap(B): all B with B??A and cap(B)>0
cap(B): all B with B<<A
cap(A)
InitLevel
cap(D)
orp (A)
.....................MinLevel
cap(B): all B with B??A and cap(B)>0
and D<<B
InitLevel
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
20
14. března 2022
Optimistický zdrojový profil: cvičení
orp(A) = InitLevel + cap{Ä) + Y,b«a c3PÍb) + Ee??/\^caP(e)>o cap{B)
orp(A) - cap(D) - J2d«b & b??a&cap(b)>o cap{B) < MinLevel D «A
• Máme dány aktivity A, B, C, X, Y, Z
a jejich požadované kapacity jsou po řadě 1, 2, 3,4, 5, —1
• Jsou dány precedence: A « B « C, X << Y
• InitLevel = MinLevel = 0
• Jaká je hodnota orp(A)l
orp(A) = 0 + cap(A) + 0 + (cap(X) + cap(V)) = 0 + l + 0 + (4 + 5) = 10
• Může být X naplánováno po A? 10 — 4 — 5 = 1, tj. ano
• Co se změní, pokud bychom přidali aktivitu D s následujícími vlastnostmi?
• cap(D) = -2
* D «A
orp(A) = 0 + 1 + (-2) + (4 + 5) = 8a dále 8 - 4 - 5 = -1, tj. X nesmí být po A
Hana Rudová, Fl MU: Omezující podmínky (pokračování) 21 14. března 2022
Pesimistický zdrojový profil (prp) Cesta&Steiia 1997
prp(Ä)\ minimálni možná úroveň zdroje v čase, kdy se A začne zpracovávat
Aktivity, které musí být před A, se vezmou dohromady s konzumačními aktivitami, které mohou být před A
prp(A) = InitLevel + cap(A) + Y,b«a caP(e) + Ee??/\^caP(e)<o cap{B) Příklad:
TI
cap(B): all B with B??A and cap(B)<0
i
t............prp(A)
cap(B): all B with B<<A
cap(A)
InitLevel
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
22
14. března 2022
prp odvozovací pravidla I.
prp(A) > MaxLevel =4> fail
• i když je veškerá konzumace plánována před A, maximální povolená kapacita zdroje je překročena
cap(B): all B with B??A and cap(B)<0
t
t............_prp(A)
cap(B): all B with B<<A
cap(A)
InitLevel
prp(A) = InitLevel + cap(A) + J2b«a cap(B) + Ee??y\&cap(B)<o cap(B)
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
23
14. března 2022
prp odvozovací pravidla II.
prp{Ä) - cap{D) - Y,D«BkBiiAkcaP{B)<Q cap(B) > MaxLevel D «A
Uvažujme časový okamžik, kdy začne aktivita A:
9 pro libovolné D takové, že Dl?A a cap(D) < 0:
jestliže je konzumace v D plánována po A a je překročena maximální povolená úroveň zdroje, pak musí být D před A
Příklad:
TJ
cap(B): all B with B??A and cap(B)<0
...........prp (A)
w cap(B): all B with B<<A
| cap(A)
InitLevel
a cap(B): all B with B??A and cap(B)<0
and D<<B
cap(D)
MaxLevel
prp(A)
InitLevel
Hana Rudová, Fl MU: Omezující podmínky (pokračování)
24
14. března 2022