Obsah

Zadání

Plánování a rozvrhování: Problém rozvrhování, obecné řešící metody. Problém splňování podmínek, reprezentace a složitost. Algoritmy a konzistence podmínek, řešení vícenásobných podmínek.

Vypracování

Problém rozvrhování

Problém rozvrhování je nalezení optimální alokace / přiřazení zdrojů množině úloh v čase. Množství zdrojů je omezené a cílem je maximalizace zisku za daných omezení.

Rozvrh je dán umístěním úloh do konkrétního času a na konkrétní zdroje, kde mají být úlohy prováděny. Úplný rozvrh má umístěny všechny úlohy ze zadání problému, zatímco v částečném rozvrhu některé úlohy nejsou umístěny.

V konzistentním rozvrhu jsou splněny všechny podmínky pro zdroje a uzly (precedenční podmínky, na jednom stroji neběží víc úloh než je jeho kapacita najednou).

Optimální rozvrh je takový, kterého umístění úloh na stroje je optimální vzhledem k zadanému optimalizačnímu kritériu, např. čas dokončení poslední úlohy má být minimální.

Rozvrhovací problémy se označují Grahamovou klasifikací: \alpha | \beta | \gamma, kde:

Příkladem je Pm|r_j|\sum w_j C_j pro paralelní stroje.

Obecné řešící metody

Existuje mnoho algortimů pro řešení problému rozvrhování:

Problém splňování podmínek

Dána je množina doménových proměnných Y = \{y_1, ..., y_k\} a konečná množina hodnot (doména) D = D_1 \cup ... \cup D_k. Omezení c na Y je podmnožina D_1 \times ... \times D_k (omezuje hodnoty, kterých mohou proměnné nabývat současně). Omezení c definováno na y_1, ..., y_k je splněno, pokud pro d_1 \in D_1, ..., d_k \in D_k platí (d_1, ..., d_k) \in c.

Je dána konečná množina proměnných V = \{v_1, ..., v_n\}, konečná množina hodnot (doména) D = D_1 \cup ... \cup D_n a konečná množina omezení C = \{c_1, ..., c_m\} definovaných na podmnožině V. Problém splňování podmínek je trojice (V, D, C) (constraint satisfactory problem - CSP).

Reprezentace a složitost

CSP problém je reprezentován jako sada (seznam, množina) omezení. Omezení je možné reprezentovat výčtem možných n-tic povolených hodnot, nebo matematickou notací, naříklad x < y.

Alternativní způsob reprezentace CSP problému je multi-graf, ve kterém uzly představují proměnné a multi-hrany (mohou procházet více vrcholy) představují omezení na těchto proměnných.

Pokud CSP obsahuje pouze binární podmínky (každá podmínka omezuje právě dvě proměnné), postačí graf. CSP je možné tranformovat na binární CSP.

CSP je NP-těžký problém, pomocí heuristik je ale obvykle možné dosáhnout skoro polynomiální časovou složitost pro ne-moc složité sady omezení.

Algoritmy a konzistence podmínek

Řešením CSP je nalezení přiřazení proměnných konzistentní s všemi podmínkami.

Při řešení je možno využít následovné algoritmy:

Algoritmy propagace omezení

Zjednodušují problém odstraňováním nekonzistentních hodnot z domén proměnných a udržují ekvivalenci s původním problémem. Používají se pro výpočet lokální konzistence, čímž aproximují globální konzistenci. Ve zřídkavých případech jsou schopny poskytnout (nějaké) řešení, ale obvykle je nutno je skombinovat s prohledávacími algoritmy (viz níže).

Vrcholová konzistence

Převod unárních podmínek do domén proměnných. CSP je vrcholově konzistentní když je každý jeho vrchol vrcholově konzistentní.

Hranová konzistence

Hrana představuje (binární) podmínku mezi dvěma vrcholy v grafu CSP. Více podmínek na jedné hraně převedeme do jedné podmínky.

Hrana (V_i, V_j) je hranově konzistentní právě když pro každou hodnotu x z aktuální domény D_i existuje hodnota y z aktuální domény D_j tak, že ohodnocení [V_i = x, V_j = y] splňuje všechny binární podmínky nad V_i, V_j.

Pozn.: hranová konzistence je směrová.

CSP je hranově konzistentní právě tehdy když jsou všechny jeho hrany v obou směrech konzistentní.

Hranu je možné udělat konzistentní pomocí revize hrany: odstranění takových hodnot x z D_i, které nejsou konzistentní s doménou D_j.

Pro hranovou konzistenci existuje několik algoritmů:

Konzistence po cestě

Cesta (V_0, V_1, ..., V_m) je konzistentní právě tehdy, když pro každou dvojici hodnot x \in D_0, y \in D_m splňující binární podmínky na hraně V_0, V_m existuje ohodnocení proměnných V_1, ..., V_{m - 1} takové, že všechny binární podmínky mezi sousedy V_j, V_{j + 1} jsou splněny. CSP je konzistentní po cestě právě když jsou všechny cesty konzistentní.

Stačí ověřit konzistenci cest délky 2. CSP je konzistentní po cestě právě tehdy, když každá cesta délky 2 je konzistentní (důkaz indukcí).

Pozn.: Z konzistence po cestě vyplývá hranová konzistence, ale konzistence po cestě neřeší konzistenci uzlů.

Revize cesty z V_i do V_j přes V_m: Pro každou dvojici proměnných V_i, V_j vyřadíme dvojici (a, b) z relace R_{ij} pokud neexistuje taková hodnota c \in V_m, že (a, c) je konzistentní pro R_{im} a (c, b) je konzistentní pro R_{mj}.

Pro konzistenci po cestě existuje několik algoritmů:

Omezená konzistence po cestě

Jedná se o oslabení konzistence po cestě za účelem neměnění grafu podmínek, snížení paměťových nároků a uchování toho, že je silnější než AC.

PC hrany se testuje pouze tehdy, pokud vyřazaní dvojice může vést k vyřazení některého z prvků z domény příslušné proměnné. Pozná se to tak, že se jedná o jedinou vzájemnou podporu.

Algoritmus je založen na PC-4 a využívá seznam cest pro PC.

Konzistence mezí

Je slabší než obecná hranová konzistence. K propagaci dochází pouze při změně minimální nebo maximální hodnoty v doméně proměnné (změna mezí domény proměnné).

Hodnota a proměnné x \in scope(c) má intervalovou podporu \vec{t} v c jestliže \vec{t} \in c \land a = \vec{t}[x] a \forall y \in scope(c) platí \vec{t}[y] \in [min(D_y), max(D_y)].

Omezení má konzistentní meze, jestliže každá hodnota a proměnné x \in scope(c) má intervalovou podporu v c.

CSP má konzistentní meze práve tehdy, když všechna jeho omezení mají konzistentní meze.

Konzistence pro nalezení řešení

CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (x_1, ..., x_n) jestliže pro každé i \leq n může být každé částečné řešení (x_1, ..., x_i) konzistentně rozšířeno o proměnou x_{i + 1}.

Pro libovolné uspořádání proměnných potřebujeme silnou n-konzistenci pro graf s n vrcholy.

Prohledávací algoritmy

Prohledávají stavový prostor řešení.

Backtracking

Prohledávání stavového prostoru do hloubky. Backtracking má 2 fáze:

Pohled dopředu (propagace omezení)

Algoritmus kontroluje podmínky dopředu.

Známé algoritmy:

Pohled zpět (inteligentní vracení)

Algoritmy:

Neúplná stromová prohledávání

Algoritmus prohledává pouze některé části stavového prostoru.

Známé algoritmy:

Algoritmy využívající heuristiky:

Prochádzení úplných nekonzistentních přiřazení

Algoritmy typu generuj a testuj, lokální prohledávání nebo population-based search.

Řešení vícenásobných podmínek

Jedná se o zobecnění principů NC, AC a PC směrem ke k-konzistenci, t.j. pracuje se s libovolnými k-ticemi proměnných. V praxi se k-konzistence vzhledem k paměťové a časové složitosti nevyužívá.

Obecné typy konzistence pracují s n-árními podmínkami. Specifickým typem omezení jsou globální omezení, například „všechny proměnné jsou různé“.

CSP je k-konzistentní právě tehdy, když můžeme libovolné konzistentní ohodnocení k - 1 různých proměnných rozšířit do libovolné k-té proměnné. CSP je silně k-konzistentní právě tehdy, když je j-konzistentní pro každé j \leq k.

Předměty

FI:PA167 Rozvrhování (jaro 2011), doc. Mgr. Hana Rudová, Ph.D.

FI:PA163 Programování s omezujícími podmínkami (podzim 2011), doc. Mgr. Hana Rudová, Ph.D.

Použitá literatura

-

Vypracoval

DevelX - Martin Jurča

stav - 100 %