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 %

mgr-szz/in-psk/10-psk.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0