Omezující podmínky pro rozvrhování 14. března 2023 Q Rozvrhování jako problém splňování podmínek Q Podmínky pro zdroje Rozvrhování jako CSP: čas Aktivita A: entita vyžadující prostor (zdroje) a čas Proměnné a jejich domény pro časové přiřazení aktivity • start(A): startovní čas aktivity • aktivita nemůže začít před svým termínem dostupnosti • est(A) = min(start(A)), earliest start time/nejdřívější startovní čas • end(A): čas skončení aktivity • aktivita musí skončit před svým deadline • lct(A) = max(end(A)), latest completion time/nejpozdější koncový čas • p(A): doba provádění aktivity • start(A) = {est(A), ..., (lct(A)-p(A))} o end(A) = {(est(A)+p(A)), ..., lct(A)} est(A) P(A) lct(A) time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 2 14. března 2023 Rozvrhování jako CSP: základní omezení I. Nepřerušitelná aktivita: žádné přerušení během jejího zpracování 9 start(A) + p(A) = end(A) P(A) start(A) end(A) time 012345678 9 10 • Přerušitelná aktivita: může být přerušena během svého zpracování 9 start(A) + p(A) < end(A) A[l] \[2 ] A[3] A[4] í start(A) end(A) time 0123456789 10 11 12 p(A) = p(A[l]) + p(A[2]) + p(A[3]) + p(A[4]) Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 3 14. března 2023 Rozvrhování jako CSP: základní omezení II. o Seřazení A< A « D. 16 A( Q = {B,C} B(4) 16 7 C(5) 15 A « Q ^> ení/(yA) < min{/ct(Q') - p(fi') | Q' C Q} každá podmnožina Q musí stihnout své zpracování 4 h| A(2) \\ 7 6h-U B(4) 16 C(5) 115 Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 9 14. března 2023 Hledání hran: všechna odvozovací pravidla • Zopakujme tedy odvozovací pravidla: pro end(A) (co se stane, pokud nebude aktivita A zpracována jako první?) • lct(Q U {A}) - esŕ(ft) < p(Q U {A}) ^A«Q • A « Q end(A) < min{/cŕ(ft') - p(ft') | Q/ C Q} • Symetrická odvozovací pravidla: pro start(A) (co se stane, pokud nebude aktivita A zpracována jako poslední?) • /cŕ(ft) - est(Q U {A}) < p(ft U {A}) Q << A • Q << A start(A) > max{esŕ(ft') + p(ft') | Q/ C Q} • V praxi: • celkem existuje n-2" párů A,Q (příliš mnoho!) • Carlier & Pinson 1994, Vilím & Barták & Čepek 2004 algoritmus s časovou složitostí 0(A7logA?) (je nutné kontrolovat pouze některé páry A,Q) Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 10 14. března 2023 Ne-první/ne-poslední (not-first/not-last) • Torres & Lopez 2000 • Co se stane, pokud aktivita A bude zpracována jako první? A(2) 116 7 B(5) -115 16 Cffll I 4|-1- Pro B a C není dost času, a tedy aktivita A nemůže být první 8 A(2) 16 B(5) 15 C(4) 16 Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 11 14. března 2023 Ne-první/ne-poslední: př. s odvozovacími pravidly p(Q U {A}) > /ct(ft) - est(A) =4> ->A « Q A(2) 16 Q = {B,C} B(5) 4 |15 16 C(4) ] i/4 << Q ^> starty) > min{ecř(e)|e G Q} 8 A(2) 16 B(5) 15 C(4) 16 Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 12 14. března 2023 Odvozovací pravidla pro ne-první/ne-poslední • Zopakujme Ne-první pravidla: (co se stane, pokud aktivita A bude zpracována jako první?) • /cŕ(ft) - est(A) < p(Q U {A}) -íA « Q • -i A « Q sřarř(>4) > min{ecŕ(6)|e G Q} • Ne-poslední (symetrická) pravidla: (co se stane, pokud aktivita A bude zpracována jako poslední?) • lct(A) - esŕ(ft) < p(Q U {A}) ^^Q«A • -nft << A eA7c/(/l) < max{/sŕ(6)|e G Q} • V praxi: • Vilím 2004: algoritmus s časovou složitostí 0(A7logA?) Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 13 14. března 2023 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 o 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á, Fl MU: Omezující podmínky pro rozvrhování 14 14. března 2023 Alternativní zdroje: odvozovací pravidla Nechť Au reprezentuje duplikát aktivity A na zdroji uGresource(A), pak probíhají následující propagace: • uGresource(A) =4> start(A) < start(Aw) • uGresource(A) =4> end(Aw) < end(A) o start(A) > min{start(Aw): u £ resource(A)} 9 end(A) < max{end(Aw): u £ resource(A)} • neúspěch pro Au =4> resource(A)\{u} Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 15 14. března 2023 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 pevná kapacita Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 16 14. března 2023 Agregované požadavky Baptisté et al. 2001 Kdy je dostatečná kapacita pro zpracování aktivity? kapacita zdroje agregované požadavky • Jak se konstruuje graf agregovaných požadavků? B Q_ > kapacita zdroje agregované požadavky — tady aktivita určitě poběží cas Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 17 14. března 2023 9999999 Podmínka tabulky (timetable constraint) • Uvažujeme diskrétní čas • Jak zajistit, že v žádném čase není překročena maximální kapacita? V t cap(Aj) < MaxCapacity start{Ai) min{t 11 e X(A,t)} • end(A) < l+max{t 11 e X(Aft)} 9 X(A,t)=0 A t start(A)>t • X(Aft)=0 A lst(A)4, 5) jsou {0,1}, X(6, 3) až X(6, 8) jsou {0,1}, X(C, 0) až X(C, 2) jsou {0,1}, ostatní proměnné nulové O Jak se jejich hodnoty mění při použití odvozovacích pravidel podmínky tabulky? O 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(/4, 5) = 0 © dále z (*) X(C, 2) = 0, C začne v čase 0 X(/4,1) = 0 a >4 začne v čase 2 a také B musí začít až v čase 5 a X(6,4) = 0 a máme jediné řešení Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 22 14. března 2023 Cvičení: podmínka tabulky 3 —L- H A 1 I I i i i i 1 j '—h Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 23 14. března 2023 Cvičení: podmínka tabulky o 3 —L- H f 1—f—I—1—'—f—1—I—h-!—* AC ■f Hana Rudová, Fl MU: Omezující podmínky pro rozvrhování 24 14. března 2023 Unární a kumulativní zdroje: shrnutí a možná rozšíření Disjunktivní omezení a známe: unární zdroje, nepřerušitelné aktivity • rozšíření: přerušitelné aktivity, kumulativní zdroje Hledání hran a známe: unární zdroje, nepřerušitelné aktivity • rozšíření: přerušitelné aktivity, kumulativní zdroje Ne-první/ne-poslední a známe: unární 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á, Fl MU: Omezující podmínky pro rozvrhování 25 14. března 2023