Rozvrhování s omezujícími podmínkami (dokončení) 21. března 2023 1 Podmínky pro zdroje (pokračování) 2 Globální omezení 3 Prohledávání a rozvrhovací strategie Produkovatelné/spotřebovatelné zdroje Zdroj = rezervoár Aktivita konzumuje nějaké množství zdroje cap(A)<0 nebo aktivita produkuje nějaké množství zdroje cap(A)>0 Požadována minimální kapacita zdroje (při konzumaci) a maximální kapacita zdroje nemůže být překročena (produkcí) −1 −1 +1 Kumulativní zdroj může být chápan jako speciální případ rezervoáru každá aktivita konzumuje cap(A) při startu a produkuje cap(A) na konci Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 2 21. března 2023 Relativní uspořádání Pokud je čas relativní (uspořádání aktivit) potom techniky edge ﬁnding a agregovaných požadavků nic neodvodí Pořád ale můžeme používat informace o uspořádání aktivit a spotřebě/produkci daného zdroje Příklad: reservoár: aktivity konzumují a produkují zdroj −1−1−1 +1 lze odvodit nezbytnost přídavné aktivity produkující jednotku zdroje Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 3 21. března 2023 Optimistický zdrojový proﬁl (orp) Cesta&Stella 1997 orp(A): maximální možná úroveň zdroje v čase, kdy se A začne zpracovávat Aktivity, které musí být před A, se vezmou dohromady s produkčními aktivitami, které mohou být před A orp(A) = InitLevel + cap(A) + B<0 cap(B) Příklad: B??A znamená, že pořadí A a B ještě není známé Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 4 21. března 2023 orp odvozovací pravidla I. orp(A) < MinLevel ⇒ fail i když je veškerá produkce plánována před A není dosažena minimální požadovaná úroveň zdroje orp(A) = InitLevel + cap(A) + B<0 cap(B) Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 5 21. března 2023 orp odvozovací pravidla II. orp(A) − cap(D) − D<0 cap(B) < MinLevel ⇒ D << A Uvažujme časový okamžik, kdy začne aktivita A pro libovolné D takové, že D??A a cap(D) > 0: pokud je produkce v D plánována za A a minimální požadovaná úroveň zdroje není dosažena, pak musí být D před A Příklad: Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 6 21. března 2023 Odvozovací pravidla pro orp orp(A) = InitLevel + prod(A) + B<0 prod(B) orp(A) < MinLevel ⇒ fail přestože veškerá produkce je plánována před A, pořád ještě není dosažena požadovaná minimální úroveň zdroje orp(A) − prod(D) − D<0 prod(C) < MinLevel ⇒ D << A pro libovolné D takové, že D??A a prod(D) > 0 pokud je produkce v D plánována za A a minimální požadovaná úroveň zdroje není dosažena ani když všechny ostatní produkční aktivity jsou před A (které tam být mohou), potom D musí být před A tedy odečteme produkci C, které musí být až po D (tudíž tato produkce není k dispozici pro A) ⇒ v orp(A) je zahrnuta produkce D a produkce aktivit C, které musí být po D. Proto tyto produkce odečítáme od orp(A) a dostáváme se k novému požadavku na MinLevel. Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 7 21. března 2023 Optimistický zdrojový proﬁl: cvičení orp(A) = InitLevel + cap(A) + B<0 cap(B) orp(A) − cap(D) − D<0 cap(B) < MinLevel ⇒ D << A Máme dány aktivity A, B, C, X, Y , Z a jejich požadované kapacity jsou po řadě 1, 2, 3, 4, 5, −1 Jsou dány precedence: A << B << C, X << Y InitLevel = MinLevel = 0 Jaká je hodnota orp(A)? orp(A) = 0 + cap(A) + 0 + (cap(X) + cap(Y )) = 0 + 1 + 0 + (4 + 5) = 10 Může být X naplánováno po A? 10 − 4 − 5 = 1, tj. ano Co se změní, pokud bychom přidali aktivitu D s následujícími vlastnostmi? cap(D) = −2 D << A orp(A) = 0 + 1 + (−2) + (4 + 5) = 8 a dále 8 − 4 − 5 = −1, tj. X nesmí být po A Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 8 21. března 2023 Pesimistický zdrojový proﬁl (prp) Cesta&Stella 1997 prp(A): minimální možná úroveň zdroje v čase, kdy se A začne zpracovávat Aktivity, které musí být před A, se vezmou dohromady s konzumačními aktivitami, které mohou být před A prp(A) = InitLevel + cap(A) + B< MaxLevel ⇒ fail i když je veškerá konzumace plánována před A, maximální povolená kapacita zdroje je překročena InitLevel cap(B): all B with B??A and cap(B)<0 cap(B): all B with B< MaxLevel ⇒ D << A Uvažujme časový okamžik, kdy začne aktivita A: pro libovolné D takové, že D??A a cap(D) < 0: jestliže je konzumace v D plánována po A a je překročena maximální povolená úroveň zdroje, pak musí být D před A Příklad: InitLevel cap(B): all B with B??A and cap(B)<0 cap(B): all B with B< MaxLevel ⇒ fail přestože veškerá konzumace je plánována před A, je maximální úroveň zdroje (kapacita) překročena prp(A) − prod(D) − D< MaxLevel ⇒ D << A pro libovolné D takové, že D??A a prod(D) < 0 pokud je konzumace v D plánována za A a maximální úroveň zdroje je překročena i když všechny ostatní konzumační aktivity jsou před A (které tam být mohou), potom D musí být před A tedy přičteme konzumaci C, které musí být až po D (tudíž se tato konzumace neodehraje před A) ⇒ v prp(A) je zahrnuta konzumace D a konzumace aktivit C, které musí být po D. Proto tyto konzumace přičítáme k prp(A) a dostáváme se k novému požadavku na MaxLevel. Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 12 21. března 2023 Globální podmínky Pro reprezentaci zdrojů využívány v programovacích jazycích tzv. globální podmínky deﬁnované 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í) 13 21. března 2023 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í) 14 21. března 2023 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í) 15 21. března 2023 Disjunktní rozvrhování Sekvenční proměnná p deﬁnová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í) 16 21. března 2023 Precedence, účelová funkce Mezi intervalovými proměnnými můžeme deﬁnovat 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 deﬁnici 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í) 17 21. března 2023 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í) 18 21. března 2023 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í) 19 21. března 2023 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í) 20 21. března 2023 Způsoby větvení (opakování) Jaká proměnná má být ohodnocena první? princip prvotního neúspěchu (ﬁrst-fail) preferuj proměnnou, jejíž přiřazení je nejobtížnější (hrozí u ní nebezpečí failu) Jaká hodnota má být vyzkoušena první? princip prvotního úspěchu (succeed-ﬁrst) preferuj hodnoty, které nejspíše patří do řešení Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 21 21. března 2023 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), . . . deﬁnuje tvar prohledávacího stromu podobně jako princip prvního neúspěchu (ﬁrst-fail) preferuj alternativy s větší ﬂexibilitou deﬁnuje pořadí větví pro prozkoumání podobně jako princip prvního úspěchu (succeed-ﬁrst) Jak popsat, co je kritické a co je ﬂexibilní? Hana Rudová, FI MU: Rozvrhování s omezujícími podmínkami (dokončení) 22 21. března 2023 Rezerva (slack) Smith&Cheng 1993 Rezerva (slack) je formální popis ﬂexibility Rezerva pro dané pořadí dvou aktivit „volný čas pro posunování aktivit” A B slack for A<