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.
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í: , kde:
Příkladem je pro paralelní stroje.
Existuje mnoho algortimů pro řešení problému rozvrhování:
Dána je množina doménových proměnných a konečná množina hodnot (doména) . Omezení na je podmnožina (omezuje hodnoty, kterých mohou proměnné nabývat současně). Omezení definováno na je splněno, pokud pro platí .
Je dána konečná množina proměnných , konečná množina hodnot (doména) a konečná množina omezení definovaných na podmnožině . Problém splňování podmínek je trojice (constraint satisfactory problem - CSP).
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 .
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í.
Ř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:
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).
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í.
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 je hranově konzistentní právě když pro každou hodnotu z aktuální domény existuje hodnota z aktuální domény tak, že ohodnocení splňuje všechny binární podmínky nad .
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 z , které nejsou konzistentní s doménou .
Pro hranovou konzistenci existuje několik algoritmů:
Cesta je konzistentní právě tehdy, když pro každou dvojici hodnot splňující binární podmínky na hraně existuje ohodnocení proměnných takové, že všechny binární podmínky mezi sousedy 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 do přes : Pro každou dvojici proměnných vyřadíme dvojici z relace pokud neexistuje taková hodnota , že je konzistentní pro a je konzistentní pro .
Pro konzistenci po cestě existuje několik algoritmů:
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.
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 proměnné má intervalovou podporu v jestliže a platí .
Omezení má konzistentní meze, jestliže každá hodnota proměnné má intervalovou podporu v .
CSP má konzistentní meze práve tehdy, když všechna jeho omezení mají konzistentní meze.
CSP vyřešíme bez navracení vzhledem k uspořádání proměnných jestliže pro každé může být každé částečné řešení konzistentně rozšířeno o proměnou .
Pro libovolné uspořádání proměnných potřebujeme silnou n-konzistenci pro graf s n vrcholy.
Prohledávají stavový prostor řešení.
Prohledávání stavového prostoru do hloubky. Backtracking má 2 fáze:
Algoritmus kontroluje podmínky dopředu.
Známé algoritmy:
Algoritmy:
Algoritmus prohledává pouze některé části stavového prostoru.
Známé algoritmy:
Algoritmy využívající heuristiky:
Algoritmy typu generuj a testuj, lokální prohledávání nebo population-based search.
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í různých proměnných rozšířit do libovolné -té proměnné. CSP je silně k-konzistentní právě tehdy, když je j-konzistentní pro každé .
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.
-
DevelX - Martin Jurča
stav - 100 %