Obsah

Zadání
Vypracování
Předměty
Použitá literatura
Vypracoval

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:

$\alpha$ jsou charakteristiky stroje - popisuje způsob alokace úloh na stroje
$\beta$ jsou charakteristiky úloh - popisují omezení aplikovaná na úlohy
$\gamma$ jsou optimalizační kritéria

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í:

lokální prohledávání (s tabu prohledávání, simulované žíhání) - zvolíme stav, vybíráme vždy lepší stav z okolí aktuálního stavu
genetické algoritmy - pracují s populací stavů
matematické (lineární, nelineární, celočíselné) programování - vyjádření problému pomocí (ne)lineárních rovnich, řešitelné simplexovým algoritmem, elipsoidovým algoritmem nebo metodou vnitřních bodů
programování s omezujícími podmínkami (CSP - constrain satisfactory programming) - vyjádření problému jako sady omezujících podmínek, které musí být splněny, např. programování v Sicstus Prologu

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ů:

AC-1 - opakovaně provádí revizi všech hran dokud se zmenšuje doména alespoň jedné proměnné
AC-3 - pracuje s frontou hran, které je nutno ještě revidovat (vedou do uzlu, kterého doména se zmenšila)
AC-4 - pamatuje si které hodnoty domény $D_j$ „podporují“ které hodnoty domény $D_i$
AC-5 - generický algortimus, dá se redukovat na AC-3, AC-4; může funkcionálně využít sémantiku podmínek
AC-6 - drží si pouze jednu „podporu“, další hledá až při strátě
AC-7 - jako AC-4 a AC-6, ale využívá dvousměrnost podmínky
AC-3.1 - pro každou hodnotu si pamatuje poslední nalezenou podporu v každém směru a hledání začíná od ní
AC-2001 (AC-8) - AC-3 s frontou proměnných, pracuje s rozdílovými množinami (pro každou proměnnou si pamatuje hodnoty smazány od poslední revize)

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ů:

PC-1 - princip jako u AC-1
PC-2 - cesty bere pouze s jednou operací, do fronty dává pouze zasažené cesty (jako AC-3)
PC-4 - založený na počítání podpor

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:

dopředná fáze - proměnné jsou postupně vybírány, rozlišuje se částečné řešení přiřazením konzistentní hodnoty (pokud existuje) pro další proměnnou.
zpětná fáze - pokud neexistuje konzistentní hodnota pro aktuální proměnnou algoritmus se vrací k předchozí přiřazené hodnotě

Pohled dopředu (propagace omezení)

Algoritmus kontroluje podmínky dopředu.

Známé algoritmy:

FC (forward checking) - zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami.
RFLA (real full look ahead) - využívá AC pro zajíštění konzistence mezi aktuální proměnnou a budoucími proměnnými
FLA (full look ahead) - využívá pouze jeden průchod AC cyklem
PLA (partial loook ahead) - FLA, který budoucí proměnné porovnává pouze s těmi, které následují (DAC - directed AC).
FFLA (first fail look ahead) - LA, který vybírá proměnnou, která má nejmenší doménu (first-fail)

Pohled zpět (inteligentní vracení)

Algoritmy:

backjumping - algoritmus se vrací k původci chyby
constrain recording, no-good learning - přidáme další omezení, které zakazují nalezená chybná přiřazení
dynamický backtracking - měníme hodnoty pouze u minulých proměnných s konfliktem pomocí přeuspořádání proměnných
backmarking - pamatuje si kde testy na konzistenci neuspěly, eliminuje opakování dříve provedených konzistenčních testů

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

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

Známé algoritmy:

randomizovaný backtracking (s učením)
omezení počtu návratů - omezený počet navštívených listů
omezení hloubky (depth bounded search) - do dané hloubky se zkouší všechny alternativy, od zbytku se použije jiná metoda
credit search - omezený kredit, rovnoměrně se delí mezi alternativní větve prohledávání, jednotkový kredit zakazuje možnost volby
iterativní rozšiřování (iterative broadening) - omezený maximální počet voleb hodnot při každém výběru

Algoritmy využívající heuristiky:

limited discrepancy search (LDS) - omezený maximální počet diskrepancí na cestě
imporved LDS (ILDS) - cesty s diskrepancemi na konci jsou prozkoumány dříve
depth-bounded discrepancy search (DDS) - diskrepance povolené pouze do dané hloubky

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 %