Rozvrhování s omezujícími podmínkami (dokončení) 21. března 2022 1 Podmínky pro zdroje (pokračování) 2 Globální omezení 3 Prohledávání a rozvrhovací strategie Alternativní zdroje Jak modelovat alternativní zdroje pro danou aktivitu? Pro každý zdroj uděláme duplikát aktivity duplikát se účastní příslušných zdrojových podmínek, ale neomezuje další aktivity na daném zdroji „neúspěch” u duplikátu znamená odstranění zdroje z domény proměnné resource(A) příslušné aktivity odstranění zdroje z domény proměnné resource(A) znamená „smazání” odpovídajícího duplikátu původní aktivita se účastní precedenčních podmínek (např. v rámci multi-operační úlohy) omezení časů u duplikátu se propaguje do originálu aktivity a naopak Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 2 21. března 2022 Alternativní zdroje: odvozovací pravidla Nechť Au reprezentuje duplikát aktivity A na zdroji u∈resource(A), pak probíhají následující propagace: u∈resource(A) ⇒ start(A) ≤ start(Au) u∈resource(A) ⇒ end(Au) ≤ end(A) start(A) ≥ min{start(Au): u ∈ resource(A)} end(A) ≤ max{end(Au): u ∈ resource(A)} neúspěch pro Au ⇒ resource(A)\{u} Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 3 21. března 2022 Kumulativní zdroje Každá aktivita využívá jistou kapacitu zdroje cap(A) Aktivity mohou být zpracovány paralelně, pokud není překročena kapacita zdroje Kapacita zdroje může být v čase proměnná takové zdroje lze modelovat pomocí v čase neměnné kapacity, od které se odečte kapacita pevně umístěných aktivit, čímž se v každém čase dosáhne požadované kapacity pevně umístěné aktivity vytvoří kapacitní profil zdroje volnákapacita pevná kapacita čas Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 4 21. března 2022 Agregované požadavky Baptiste et al. 2001 Kdy je dostatečná kapacita pro zpracování aktivity?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ využitákapacita čas agregované požadavky kapacita zdroje Jak se konstruuje graf agregovaných požadavků?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢¢¢£ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ využitákapacita čas kapacita zdroje agregované požadavky tady aktivita určitě poběží Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 5 21. března 2022 Podmínka tabulky (timetable constraint) Uvažujeme diskrétní čas Jak zajistit, že v žádném čase není překročena maximální kapacita? ∀t start(Ai )≤t≤end(Ai ) cap(Ai ) ≤ MaxCapacity Tabulka (timetable) pro aktivitu A je množina boolovských proměnných X(A, t) udávajících, zda A běží v čase t ∀t Ai X(Ai , t)cap(Ai ) ≤ MaxCapacity (∗) ∀t, i start(Ai ) ≤ t ≤ end(Ai ) ⇔ X(Ai , t) Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 6 21. března 2022 Podmínka tabulky: př. s odvozovacími pravidly Počáteční stav Některé pozice zakázány vzhledem ke kapacitě zdroje Nový stav Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 7 21. března 2022 Podmínka tabulky: odvozovací pravidla Jak realizovat filtraci přes omezení ∀t, i start(Ai ) ≤ t < end(Ai ) ⇔ X(Ai , t) ? Problém: t je zároveň index a také proměnná start(A) ≥ min{t | 1 ∈ X(A,t)} end(A) ≤ 1+max{t | 1 ∈ X(A,t)} X(A,t)=0 ∧ t < ect(A) ⇒ start(A)>t X(A,t)=0 ∧ lst(A)≤t ⇒ end(A)≤t lst(A)≤t ∧ t < ect(A) ⇒ X(A,t)=1 Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 8 21. března 2022 Cvičení: podmínka tabulky Máme zadány zdroj s kapacitou 2 a aktivity j cap(j) est(j) lct(j) p(j) A 2 1 6 3 B 1 3 9 4 C 1 0 3 2 1 Jak jsou inicializovány proměnné X(j,t)? 2 Jak se jejich hodnoty mění při použití odvozovacích pravidel podmínky tabulky? 3 Jak by mohly vypadat výsledné rozvrhy po aplikaci pravidel? Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 9 21. března 2022 Cvičení: podmínka tabulky 1 Jak jsou inicializovány proměnné X(j,t)? X(A, 1) až X(A, 5) jsou {0, 1}, X(B, 3) až X(B, 8) jsou {0, 1}, X(C, 0) až X(C, 2) jsou {0, 1}, ostatní proměnné nulové 2 Jak se jejich hodnoty mění při použití odvozovacích pravidel podmínky tabulky? 1 dle (∗) B může začít nejdříve v čase 4 kvůli A, tj. X(B, 3) = 0 a A musí být před B, tj. A nejpozději skončí v čase 5 a X(A, 5) = 0 2 dále z (∗) X(C, 2) = 0, C začne v čase 0 X(A, 1) = 0 a A začne v čase 2 a také B musí začít až v čase 5 a X(B, 4) = 0 a máme jediné řešení Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 10 21. března 2022 Cvičení: podmínka tabulky Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 11 21. března 2022 Cvičení: podmínka tabulky Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 12 21. března 2022 Unární a kumulativní zdroje: shrnutí a možná rozšíření Disjunktivní omezení známe: unarní zdroje, nepřerušitelné aktivity rozšíření: přerušitelné aktivity, kumulativní zdroje Hledání hran známe: unarní zdroje, nepřerušitelné aktivity rozšíření: přerušitelné aktivity, kumulativní zdroje Ne-první/ne-poslední známe: unarní zdroje, nepřerušitelné aktivity rozšíření: kumulativní zdroje Podmínka tabulky známe: kumulativní zdroje, nepřerušitelné aktivity rozšíření: přerušitelné aktivity Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 13 21. března 2022 Globální podmínky Pro reprezentaci zdrojů využívány v programovacích jazycích tzv. globální podmínky definované pro libovolný konečný počet proměnných komplexní podmínky s vlastním propagačním algoritmem Základní globální podmínky (pro rozvrhování) příklady z IBM ILOG OPL (Optimization Programming Language) všechny proměnné různé allDifferent disjunktivní zdroj dvar interval, dvar sequence noOverlap kumulativní zdroj cumuFunction, pulse Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 14 21. března 2022 Všechny proměnné různé Proměnné v poli Array jsou různé reprezentace unárního zdroje s jednotkovou dobou trvání všech aktivit dvar int Array[Interval]; globální podmínka: allDifferent(Array) učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Příklad: učitelé musí učit v různé hodiny Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr ∈ {3, 4}, Eva ∈ {3, 4} Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 15 21. března 2022 Intervalové proměnné Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivity) hodnotou intervalové proměnné je celočíselný interval [start, end) příklad: dvar interval x in 0..1000000 size 100..200; Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 16 21. března 2022 Disjunktní rozvrhování Sekvenční proměnná p definována na množině intervalových proměnných x dvar interval x[i in 1..n] ...; dvar sequence p in x; hodnota intervalové proměnné p je permutace přítomných intervalů pozor, permutace t ještě neimplikuje žádné uspořádání v čase Omezení noOverlap(p) vyjadřuje, že sekvenční proměnná p reprezentuje řetězec nepřekrývajících se intervalových proměnných pro vyjádření rozvrhování na unárním/disjunktivním zdroji, kde se intervaly/úlohy nepřekrývají Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 17 21. března 2022 Precedence, účelová funkce Mezi intervalovými proměnnými můžeme definovat precedenční podmínky: dvar interval i; dvar interval j; endBeforeStart(i, j); startBeforeStart(i, j); startAtStart(i, j); ... Pro vytváření účelových funkcí nebo definici omezení startOf(x) endOf(x) sizeOf(x, V) Příklad: minimalizace makespanu minimize max(i in 1..n) endOf(x[i]) Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 18 21. března 2022 Příklad: rozvrhování problému job-shop tuple Operation { int mch; // machine int pt; // processing time }; Operation Ops[j in Jobs][p in Pos] = ...; op[j][p] odkazuje operaci úlohy j, která je zpracovávána v rámci úlohy jako p-tá Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 19 21. března 2022 Kumulativní zdroj pomocí kumulativní funkce Hodnota výrazu kumulativní funkce reprezentuje vývoj kvantity v čase, která může být inkrementálně změněna (snížena nebo navýšena) intervalovými proměnnými. Intervalové proměnné x[i] přispívají do kumul. funkce po dobu svého provádění int capacity[1..5] = [1,3,2,4,1]; cumulFunction y = sum(i in 1..5) pulse(x[i],capacity[i]); Omezení na výrazech kumulativní funkce: pro omezení kapacity zdroje int h = ... cumulFunction f= ... f<=h Příklad: job-shop a omezení celkového počtu strojů cumulFunction allMachines = sum(j in Jobs, p in Pos) pulse(op[j][p],1); allMachines <= m; Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 20 21. března 2022 Prohledávání/přiřazování (opakování) Konzistenční techniky jsou (obvykle) neúplné ⇒ potřeba prohledávací algoritmus, který vyřeší "zbytek" Přiřazovaní (labeling) prohledávání do hloubky (DFS/BT) přiřaď hodnotu do proměnné propaguj = udělěj problém lokálně konzistentní vrať se v případě neúspěchu Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 21 21. března 2022 Způsoby větvení Jaká proměnná má být ohodnocena první? princip prvotního neúspěchu (first-fail) preferuj proměnnou, jejíž přiřazení je nejobtížnější např. proměnné s nejmenší doménou: doména se snadněji vyprázdní nebo proměnné s nejvíce podmínkami: pro proměnné s více podmínkami je obecně obtížnější nalézt hodnotu proměnné definuje tvar prohledávacího stromu výběr proměnné s malou velikostí domény: malé větvení na této úrovni výběr proměnné s velkou velikostí domény: velké větvení na této úrovni Jaká hodnota má být vyzkoušena první? princip prvotního úspěchu (succeed-first) preferuj hodnoty, které nejspíše patří do řešení např. hodnoty s nejvíce podporami v okolních proměnných tato heuristika je obvykle problémově závislá definuje pořadí procházení větví Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 22 21. března 2022 Schémata větvení Větvení = řešení disjunkcí Tradiční rozvrhovací přístupy kritická rozhodnutí se dělají první vyřeš kritická místa (bottlenecks), . . . definuje tvar prohledávacího stromu podobně jako princip prvního neúspěchu (first-fail) preferuj alternativy s větší flexibilitou definuje pořadí větví pro prozkoumání podobně jako princip prvního úspěchu (succeed-first) Jak popsat, co je kritické a co je flexibilní? Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 23 21. března 2022 Rezerva (slack) Smith&Cheng 1993 Rezerva (slack) je formální popis flexibility Rezerva pro dané pořadí dvou aktivit „volný čas pro posunování aktivit” A B slack for A<