Řešení vybraných příkladů ze sbírky k předmětu PA167 Rozvrhování Hana Rudová Fakulta informatiky, Masarykova univerzita 11. dubna 2022 Poděkování Řešení příkladů jsou převzata z domácích úkolů studentů předmětu. Všem děkuji za pěkná řešení, která jsou zde použita. 1 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 3.5 Máme 4 úlohy s dobami trvania operácií v jednolivých fázach: • 1. úloha: pii = 3,p2i = 2,P3i = l,pu = 2 • 2.úloha:pi2 = 2,p22 = 3,p32 = 6,p42 = 4 • 3.úloha:pi3 = 2,p23 = 3,p33 = 4,p43 = 3 • 4.úloha:pi4 = 2,p24 = 2,^34 = 2,^44 = 3 Máme 4 paralelné stroje - 1. fáza: Mil + M12, 2. fáza: M21 + M22 + M23, 3. fáza: M31 + M 32,4. fáza: M41 + M42. Úlohy prechádzajú všetkými fázami v rovnakom poradí. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Jl J3 Jl J3 r n U! Ba J3 Jl Mll M12 M21 M22 M23 M31 M32 M41 M42 Hana Rudová, Fakulta informatiky, Masarykova univerzita 2 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 5.4 Pravidlo minimální rezervy-jsme v určitém čase ŕ (například na začátku, kdy t = 0) a potřebujeme rozhodnout, kterou úlohu z dosud neprovedených úloh (tzn. na začátku úplně ze všech) máme spustit. Pro každou neprovedenou úlohu (tzn. na začátku úplně pro každou) se vypočítá rezerva A, = max(eŕj — p j — t, 0). Je spuštěna ta úloha, jejíž rezerva je nejmenší. t = 0 Ai = max(7 - 2 - 0, 0) = 5 A2 = max(7 - 3 - 0, 0) = 4 Aa = max(4 - 3 - 0, 0) = 1 A4 = max(ll - 1 - 0,0) = 10 A5 = max(12 - 3 - 0, 0) = 9 Úloha 3 poběží v čase (0, 3). t = 3 Ai = max(7 - 2 - 3, 0) = 2 A2 = max(7 - 3 - 3, 0) = 1 AA = max(ll - 1 - 3,0) = 7 A5 = max(12 - 3 - 3, 0) = 6 Úloha 2 poběží v čase (3, 6). t = 6 Ai = max(7 - 2 - 6, 0) = 0 AA = max(ll - 1 - 6,0) = 4 A5 = max(12 - 3 - 6, 0) = 3 Úloha 1 poběží v čase (6, 8). t = 8 A4 = max(ll - 1 - 8,0) = 2 A5 = max(12 - 3 - 8, 0) = 1 Úloha 5 poběží v čase (8,11) a úloha 4 poběží v čase (11,12). Celkový rozvrh je znázorněn následujícím Ganttovým diagramem: stroje 3 2 1 5 4 012: i 4 5 ( } 7 í i 9 10 1 1 1 2 13 14 ímoi = max(Li, L2, L3,L4, L5) = max(Ci - di, C2 - eÍ2, C3 - cř3, C4 - d4, C5 - d5) = = max(8 - 7, 6 - 7, 3 - 4,12 - 11,11 - 12) = max(l, -1, -1,1, -1) = 1 Hana Rudová, Fakulta informatiky, Masarykova univerzita 3 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 = max(Ci — cíi, 0) + max(C2 — c?2, 0) + max(C3 — c?3, 0) + max(C4 — c?4, 0) + max(C5 — d$, 0) = = max(8 - 7, 0) + max(6 - 7, 0) + max(3 - 4, 0) + max(12 - 11, 0) + max(ll - 12, 0) = = max(l, 0) + max(-l, 0) + max(-l, 0) + max(l, 0) + max(-l, 0) = 1 + 0 + 0+1 + 0 = 2 Příklad 5.5 (1) Minimum Slack čas dostupné úlohy výběr 0 úloha 4 s rezervou 11 4 1 - - 2 úloha 1 s rezervou 0 úloha 3 s rezervou 1 1 7 úloha 3 s rezervou 0 úloha 2 s rezervou 1 úloha 5 s rezervou 0 3 8 úloha 2 s rezervou 0 úloha 5 s rezervou 0 2 11 úloha 5 s rezervou 0 5 (2) Earliest Due Date tmax = max(0, 0, 4, -11, 6) = 6 J2j WjTj = 1 • 4 + 1 • 6 = 10 čas dostupné úlohy výběr 0 úloha 4 4 1 - - 2 úloha 1 úloha 3 3 3 úloha 1 úloha 2 úloha 5 1 8 úloha 2 úloha 5 5 11 úloha 2 2 tmax = max(l, 3, —1, —11, 3) = 3 •£j w3T3 = 2-1 + 1- 3 + 1- 3 = 8 Hana Rudová, Fakulta informatiky, Masarykova univerzita 4 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 5.9 Pravidlo WSPT vybírá úlohy podle doby trvání s váhami. Budeme úlohy řadit podle vzrůstajícího Pj/wj, protože chceme nejdříve brát úlohy s kratším časem a větší váhou. Minimalizuje tedy vážený součet časů konců úloh. V čase 0 máme jedinou úlohu 4. Proto ji můžeme vybrat. Doběhne v čase 3 a musíme vybrat další úlohu. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Vybíráme z úloh 3 a 5 , jejichž vážené doby trvání jsou 1/'ž a 4/i, proto vybereme úlohu 3. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Znovu vybíráme v čase 4, tentokrát z úloh 2 a 5 . Jejich vážené doby trvání jsou 5/3 a 4/i, proto vybíráme úlohu 2 . 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 V čase 9 musíme vybrat další úlohu. Máme jedinou možnost: úlohu H. Po jejím doběhnutí v čase 13 nemáme žádnou další dostupnou úlohu. Musíme tedy počkat do času 15, kdy přijde úloha |, kterou můžeme hned spustit. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Výsledný rozvrh tedy bude (4, 3, 2 , 5 , 1 ) s celkovou hodnotou účelové funkce 5-3 + 2- 4 + 3- 9 + l-13 + 3-17 = 114. Kdybychom neměli termíny dostupnosti, mohli bychom na začátku naplánovat celý rozvrh a najít 1 optimální řešení. Pro úlohu 1 bychom navíc nemuseli čekat na její zadání a zbavili bychom se tedy intervalu, kdy stroj nic nedělá. Vážené doby trvání pro úlohy 1-5 by byly postupně 2/z, 5/3, 1/2, 3/5, 4/i. Vytvořený rozvrh tedy bude (3,4,1, 2, 5) s hodnotou účelové funkce 2 • 1 + 5 • 4 + 3 • 6 + 3 • 11 + 1 • 15 = 88. Hana Rudová, Fakulta informatiky, Masarykova univerzita 5 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 6.7 Iniciálny rozvrh: S0 = (2, 3,4, 5,1) I Sbest = (2, 3,4, 5,1) I best_cost = Cmax = 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 □ 3 4 Okolie N(S0) = {(3,2,4, 5,1), (2,4, 3, 5,1), (2, 3, 5,4,1), (2, 3,4,1, 5)} Rozvrh Cmax (3,2,4,5,1) 17 (2,4,3,5,1) 15* (2,3,5,4,1) 16 (2,3,4,1,5) 16 56est = (2,4, 3, 5,1) I Si = (2,4, 3, 5,1) I best_cost = 15 Okolie AT(Si) = {(4,2, 3, 5,1), (2, 3,4, 5,1), (2,4, 5, 3,1), (2,4,3,1, 5)} Rozvrh vmax (4,2,3,5,1) 15 (2,3,4,5,1) 16 (2,4,5,3,1) 15 (2,4,3,1,5) 15 best_cost = 15 I 56est = (2,4, 3, 5,1) Žiaden rozvrh nezlepšil hodnotu optimalizačného kritéria, algoritmus končí. Hana Rudová, Fakulta informatiky, Masarykova univerzita 6 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 7.4 1. iterace 5i = (1,2,3,4) d = 1, Ca = 3, C*3 = 6, C*4 = 7 Ti = 0, T2 = 2, T3 = 4, T4 = 0 = J2 wjtj = l- 0 + 2- 2 + 5- 4 + 3- 0 = 24 = F(Sbest) AT(5i) = {(2,1,3,4), (1,3,2,4), (1,2,4, 3)} F(2,l,3,4) C2 = 2, Ci = 3, C3 = 6, C4 = 7 T2 = l,Ti = 1,T3 = 4,T4 = 0 F(2,1, 3,4) = 2 • 1 + 1 • 1 + 5 • 4 + 3 • 0 = 23 F(l, 3,2,4) Ci = 1, C3 = 4, C2 = 6, C4 = 7 Ti = 0, T3 = 2, T2 = 5, T4 = 0 F(l, 3,2,4) = l- 0 + 5- 2 + 2- 5 + 3- 0 = 20 F(l, 2,4,3) Ci = 1, C2 = 3, C4 = 4, C3 = 7 Ti = 0, T2 = 2, T4 = 0, T3 = 5 F(l, 2,4,3) = l- 0 + 2- 2 + 3- 0 + 5- 5 = 29 Nejlepší rozvrh z okolí: (1, 3, 2,4); F(l, 3, 2,4) = 20 = F(S6est) Tabu seznam: ((2, 3)) 2.iterace S2 = (1,3,2,4) jV(S2) = (3,1, 2,4), (1, 2, 3,4), (1, 3,4, 2) F(3,l,2,4) C3 = 3, Ci = 4, C2 = 6, C4 = 7 T3 = l,Ti = 2,T2 = 5,T4 = 0 F(3, l,2,4) = 5- l + l- 2 + 2- 5 + 3- 0=17 F(l,2,3,4) TABU F(l, 3,4,2) Ci = 1, C3 = 4, C4 = 5, C2 = 7 Ti = 0, T3 = 2, T4 = 0, T2 = 6 F(l, 3,2,4) = l- 0 + 5- 2 + 3- 0 + 2- 6 = 22 Nejlepší rozvrh z okolí: (3,1, 2,4); F(3,1, 2,4) = 17 = F(56est) Tabu seznam: ((1, 3), (2, 3)) Hana Rudová, Fakulta informatiky, Masarykova univerzita 7 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 8.5 Sbest = S1 = (3,1,4,2) F(Sí) = YJwJTj = 1 - 7+ 14 • 11 + 12 - 0 + 12 - 25 = 461 = F(Sbest) t0 = 0.99 jV(Si) = {(1,3,4,2), (3,4,1,2), (3,1,2,4)} F((l, 3,4, 2)) = 14 • 0 + 1 • 16 + 12 • 0 + 12 • 25 = 316 F((3,4,1, 2)) = 1 • 7 + 12 • 0 + 14 • 14 + 12 • 25 = 503 F((3,1, 2,4)) = 1 • 7 + 14 • 11 + 12 • 22 + 12 • 5 = 485 Snew = (1,3,4,2) F(Snew) = 316 < F(56est) Sbest = S2 = (1,3,4,2) í = 0.99 -0.9 = 0.891 jV(S2) = {(3,1,4,2), (1,4,3,2), (1,3,2,4)} F((3,1,4, 2)) = 461 F((l, 4, 3, 2)) = 14 • 0 + 12 • 0 + 1 • 19 + 12 • 25 = 319 F((l, 3, 2,4)) = 0 + 16 + 12 • 22 + 12 • 5 = 340 Snew = (1,4,3,2) F(Snew) > F(S2) U2 = 0.02 < e(316-319)/0.891 S3 = (1,4,3,2) t = 0.891 -0.9 = 0.8019 N(S3) = {(4,1,3, 2), (1, 3,4,2), (1,4, 2, 3)} F((4,1, 3, 2)) = 12 • 0 + 14 • 2 + 1 • 19 + 12 • 25 = 347 F((l,3,4, 2)) = 316 F((l, 4, 2, 3)) = 0 + 0 + 12 • 13 + 28 = 184 Snew = (1,4,2,3) F(Snew) = 184 < F(Sbest) Sbest = S4 = (1,4,2,3) t = 0.72171 Hana Rudová, Fakulta informatiky, Masarykova univerzita 8 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 9.5 Potomek 1 Rodič 1:81126497135 Rodič 2: 56 I 79123 148 Krok Výpočet Potomek Zkopírování pásu alel První chybějící prvek: 8 Další chybějící prvek: 5 Další chybějící prvek: 1 Poslední chybějící prvek: 3 4 už je v pásu 679 už jsou v pásu 2 už je v pásu __26497_ __264978_ „2649785 1_2649785 132649785 Potomek 2 Rodič 2: 56 I 79123 148 Rodič 1:81126497135 Krok Výpočet Potomek Zkopírování pásu alel První chybějící prvek: 5 Další chybějící prvek: 8 Další chybějící prvek: 6 Poslední chybějící prvek: 4 3 už je v pásu 12 už jsou v pásu _79123_ _791235_ _7912358 6_7912358 647912358 Hana Rudová, Fakulta informatiky, Masarykova univerzita 9 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 9.12 Modře zbarvený potomek bude nahrazovat zeleně zbarveného jedince v populaci. 0. populace: populace 3421 2314 4231 vhodnost 17 15 potomci 4321 3241 3412 3214 2134 2341 2431 4321 4213 vhodnost 17 15 14 14 13 16 18 17 16 1. populace: populace 2314 2134 vhodnost 15 13 potomci 4321 3241 3412 3214 2134 2341 1234 2314 2143 vhodnost 17 15 14 14 13 16 9 15 14 2. populace: populace 1234 2314 2134 vhodnost 9 15 13 Rozvrh s nejlepší vhodností po dvou iteracích: 1234. Hana Rudová, Fakulta informatiky, Masarykova univerzita 10 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 11.8 Iniciální domény: A e {1..4}, B e {1..4}, C e {1..4} Iniciální fronta: Q = {A, B, C} 1. výběr A z fronty (a) revise(ci): beze změn (b) revise(c3) -> Ae {1..3}, B e {1..3} Q = {B, C} u {A} = {B, C, A} (B už ve frontě je, nepřidáváme) 2. výběr B z fronty (a) revise(ci): beze změn (b) revise(c2): beze změn (c) revise(c3): beze změn (d) revise(c4) —> B e {1..2}, C e {1..2} Q = {C, A} u {B} = {C, A, B} (C už ve frontě je, nepřidáváme) 3. výběr C z fronty (a) revise(c2): beze změn (b) revise(c4): beze změn Q = {A, B} 4. výběr A z fronty (a) revise(ci): beze změn (b) revise(c3) -> Ae {2..3} Q = {B} u {A} = {B, A} (B už ve frontě je, nepřidáváme) 5. výběr B z fronty (a) revise(ci): beze změn (b) revise(c2): beze změn (c) revise(c3): beze změn (d) revise(c4): beze změn Q = {A} 6. výběr A z fronty (a) revise(ci): beze změn (b) revise(c3): beze změn Q = {] Finální domény: A e {2, 3}, B e {1, 2}, C e {1, 2} Hana Rudová, Fakulta informatiky, Masarykova univerzita 11 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 11.13 Algoritmus MAC postupně přiřazuje proměnným hodnoty. Při každém přiřazení kontroluje, jestli jsou proměnné konzistentní. Pokud ne, zkusí jinou hodnotu. Když některé proměnné dojdou hodnoty, algoritmus oznámí neexistenci řešení. Nejprve provedeme konzistenční algoritmus. Podmínky 1, 2,4 jsou konzistentní. Pro podmínku 3 ale hodnota 0 proměnné B nemá podporu a proto ji můžeme odstranit. Nové domény tedy jsou A in 0 ... 1, B in 1... 3, C in 0 ... 2. Nyní můžeme spustit vlastní prohledávací algoritmus. První krok: vybereme proměnnou. A má dvě možné hodnoty, B a C po třech hodnotách. Proto vybereme A. Nyní musíme vybrat některou její hodnotu. Pro hodnotu 0 máme 3 + 2 + 3 + 2 = 10 podpor (postupně pro jednotlivé podmínky {1,2, 3}, {1,2}, {1, 2, 3}, {(2, 2), (3,1)}). Pro hodnotu 1 máme 2 + 2 + 2 + 3 = 9 podpor ({2, 3}, {0, 2}, {2, 3}, {(1,2), (2,1), (3, 0)}). Vezmeme hodnotu 0 jako první a přiřadíme A = 0. Nyní musíme zrevidovat domény ostatních proměnných. První a třetí podmínka neodstraní žádné hodnoty. Druhá podmínka odstraní hodnotu 0 proměnné C. Poslední podmínka odstraní hodnotu 1 z domény proměnné B. Nové domény tedy jsou A = 0, B in 2 ... 3, C in 1... 2. Vybereme další proměnnou. Obě zbývající proměnné mají po dvou hodnotách, zvolíme tedy například proměnnou B. Její hodnoty mají po jedné podpoře v doméně C. Jako první tedy zkusíme například hodnotu 2 a budeme propagovat omezení. Čtvrté omezení nám odstraní hodnotu 1 z domény C. Tím se doména poslední proměnné zmenšila na jedinou hodnotu a dostali jsme řešení. Výsledek tedy je A = 0, B = 2, C = 2. Hana Rudová, Fakulta informatiky, Masarykova univerzita 12 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 13.8 Hladanie hrán: end(A) : lct(íl U {Ä}) - est(íl) < p(íl U {A}) => A « íl, A « íl ==> end(A) < mm{lct(íl') - p(íl') \íl' Cíl} start(A) : lct(íí) - est(íl U {A}) < p(íl U {A}) => íl « A íl«A=> start(A) > max{esí(íľ) + p(íl') \íl' Cíl} Krok íl Výpočet Výsledok end(l) {2,3,4} let = 16, est = 0,p = 15 žiadna zmena end(2) {1,3,4} let = 16, est = 0,p = 15 žiadna zmena end(3) {1,2,4} let = 16, est = 0,p = 15 žiadna zmena end{A) {1,2,3} let = 16, est = 0,p = 15 žiadna zmena start(l) {2,3,4} let = 16, est = 0,p = 15 žiadna zmena start(2) {1,3,4} let = 16, est = 0,p = 15 žiadna zmena start(3) {1,2,4} let = 13, est = 0,p = 15 {1, 2, 4} « 3; start(3) > max{13, 9,10, 7, 6, 3, 4} > start(á) {1,2,3} let = 16, est = 0,p = 15 žiadna zmena end(l) {2,4} let = 13, est = 0,p = 13 žiadna zmena end(2) {1,4} let = 13, est = 0,p = 13 žiadna zmena end{A) {1,2} let = 13, est = 0,p = 13 žiadna zmena start(l) {2,4} let = 13, est = 0,p = 13 žiadna zmena start(2) {1,4} let = 10, est = 0,p = 13 {1, 4} << 2; start(2) > max{10, 6, 4} > 10 tj. start(2) = 10, end(2) = 13 start(á) {1,2} let = 13, est = 0,p = 13 žiadna zmena end(l) {4} let = 10, est = 0,p = 10 žiadna zmena end{A) {1} let = 10, est = 0,p = 10 žiadna zmena start(l) {4} let = 10, est = 0,p = 10 žiadna zmena start(á) {1} let = -- 8, est = 0,p = = 10 {1} << 4; štarty) > max{6} > 6 tj. starty) = 6, end(A) = 10 a start(l) = 0, end(l) = 6 Celkom teda: !<<4<<2<<3a máme dve možné riešenia: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 1 4 2 Hana Rudová, Fakulta informatiky, Masarykova univerzita 13 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Ne-první/ne-poslední: start(A) : p(íl U {A}) > lct(íl) - est(A) ->A « íl, ->A « íl start(A) > min{ecí(B) \B e fi} end(Á) : p(Q, U {A}) > let (A) - esí(íí) -.fi « A -ifi << A eneř(A) < max{kí(B) B e fi} Krok n Výpočet Výsledok start(l) 2,3,4 P = 15, let = 16, esí = 0 žiadna zmena start(2) 1,3,4 P = 15, let = 16, esí = 0 žiadna zmena start(3) 1,2,4 P = 15, let = 13, est = 0 -.3 « {l,2,4};síarí(3) > 3 start(á) 1,2,3 P = 15, let = 16, esí = 0 žiadna zmena start(l) 2,4 P = 13, let = 13, est = 0 žiadna zmena start(2) 1,4 P = 13, let = 10, esí = 0 -.2 « {l,4};start(2) > 4 start(á) 1,2 P = 13, kí = 13, esí = 0 žiadna zmena start(l) 4 P = 10, let = 10, est = 0 žiadna zmena start(á) 1 P = --10, let = -- 8, esí = = 0 -.4 « {1}; štarty) = 6 a end(4) = 10 end(l) 2,3,4 P = --15, let = = 8, est -- = 0 -.{2,3,4} « l;end(l) < 14 end(2) 1,3,4 P = 15, kí = 13, est = 0 -.{1,3,4} « 2;end(2) < 14 end(l) 2 P = 9, Zcí = 8, esí = 0 -.{2} << í;end(l) < 10 end(l) 3 P = 8, let = 8, est = 4 ^{3} « l;end(l) < 14 end(l) 4 P = 10, kí = 10, esí = 6 -.{4} << 1; end(l) = 6 a síarí(l) = 0 tj. start(2) = 10, end(2) = 13 a síarí(3) > 13 Celkom teda: !<<4<<2<<3a máme dve možné riešenia: 0 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 4 2 Hana Rudová, Fakulta informatiky, Masarykova univerzita 14 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 13.9 Nejprve určíme domény proměnných start(Á) a end(Á) a dobu provádění p(A) pro všechny úlohy z íl: Dále zkoušíme aplikovat odvozovací pravidla pro každou kombinaci (A, íl — {A}). Hledání hran (X,{Y,Z,V}),end(X) lct({Y, Z, V} U {X}) - est({Y, Z, V}) = 12 - 1 = 11 p({Y,Z,V}U{X}) = 12 11 < 12 => X « {Y,Z,V} => end(X) < min(Zcí({Y, Z, F})-p({Y, Z, V}), lct({Y, Z})-p({Y, Z}), lct({Z, V})-p({Z, V}), lct({Y, V}) — p({Y, V}), lct({Y}) - p({Y}), lct({Z}) - p({Z}), lct({V}) - p({V})) => end(X) < min(12 - 9,12 - 7,12 - 6,10 - 5,10 - 3,12 - 4, 9 - 2) end(X) < min(3, 5, 6, 5, 7, 8, 7) end(X) < 3 end(X) e {3} (X, {Y, Z,V}), start(X) lct({Y, Z, V}) - est({Y, Z, V} U {X}) = 12 - 0 = 12 p({Y,Z,V}U{X}) = 12 12 > 12 žádná změna (Y,{X, Z,y}),end(r) Zcí({X, Z, F} U {Y}) - est({X, Z, V}) = 12 - 0 = 12 p({X,Z,V}U{Y}) = 12 12 > 12 žádná změna (Y,{X, Z,y}),Síarí(F) Zcí({X, Z, V}) - est({X, Z, V} U {Y}) = 12 - 0 = 12 Z, K} U {y}) = 12 12 > 12 žádná změna (Z,{X,y,V}),end(Z) Zcí({X, Y, F} U {Z}) - esí({X, Y, K}) = 12 - 0 = 12 p({X,r,F}U{Z}) = 12 12 > 12 žádná změna (Z,{X, Y, V}),síarí(Z) Zcí({X, y, k}) - esí({X, y, F} U {Z}) = 10 - 0 = 10 p({x,y,f}u{z}) = 12 10 < 12 => {x,y,f} « 2t^ start(X) e (0, 7) end(X) e (3,10) p(X) = 3 síarí(r) e (2, 7) end(r) e (5,10) p(Y) = 3 start(Z) e (3, 8) end(Z) e (7,12) p(Z) = 4 síarí(F) e (1,7) end(F) e (3,9) p(K) = 2 Hana Rudová, Fakulta informatiky, Masarykova univerzita 15 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 start(Z) > max(esí({X, Y, Y, K}), esí({X, Y})+p({X, Y}), esí({Y, K})+p({Y, K}), esí({X, V}), est({X}) + p({X}), est({Y}) + p({Y}), est({V}) + p({V})) => start(Z) > max(0 + 8, 0 + 6,1 + 5, 0 + 5, 0 + 3, 2 + 3,1 + 2) start(Z) > max(8, 6, 6, 5, 3, 5, 3) start(Z) > 8 start(Z) e {8} (y,{x,r,z}),end(y) Zcí({X, Y, Z} U {F}) - esí({X, Y, Z}) = 12 - 0 = 12 p({X,Y,Z}U{V}) = 12 12 > 12 => žádná změna (V,{X,Y,Z}),«ŕarŕ(V) Zcí({X, Y, Z}) - est({X, Y, Z} U {V}) = 12 Y, Z} U {V}) = 12 12 > 12 => žádná změna Ne-první/ne-poslední (X, {Y, Z,V}), start(X) p({Y,Z,V}U{X}) = 12 lct({Y, Z, V}) - est(X) = 12 - 0 = 12 12 < 12 => žádná změna (X,{Y,Z,V}),end(X) p({Y,Z,V}U{X}) = 12 Zcí(X) - est({Y, Z, V}) = 10 — 1 = 9 12 > 9 => -.{Y, Z, F} << X end(X) < max(Zsí(Y),Zsí(Z),Zsí(VO) end(X) < max(7, 8, 7) end(X) < 8 end(X) e (3, 8) (Y,{X, Z,V}),Síarí(F) p({X,Z,F}U{Y}) = 12 Zcí({X, Z, K}) - esí(Y) = 12 - 2 = 10 12 > 10 => -.Y « {X, Z, F} => síarí(Y) > min(ecí(X),ecí(Z),ecí(F)) síarí(Y) > min(3, 7, 3) start(Y) > 3 start(Y) e (3, 7) (Y,{X, Z,y}),end(r) p({X,Z,F}U{Y}) = 12 Zcí(Y) - esí({X, Z, K}) = 10 - 0 = 10 12 > 10 => -.{X, Z, V} « Y => end(Y) < max(lst(X),lst(Z),lst(V)) => end(Y) < max(7, 8, 7) => end(Y) < 8 end(Y) e (5, 8) Hana Rudová, Fakulta informatiky, Masarykova univerzita 16 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 (Z,{X,Y,V}),start(Z) p({X,Y,V}U{Z}) = 12 lct({X, Y, V}) - est(Z) = 10 - 3 = 7 12 > 7 => -.Z « {X, Y, V} => start(Z) > mm(ect(X),ect(Y),ect(V)) start(Z) > min(3, 5, 3) start(Z) > 3 start(Z) € (3, 8) (ve skutečnosti žádná změna) (Z,{X,Y,V}),end(Z) p({x,y,f}u{z}) = 12 Zcí(Z) - esí({X, y, K}) = 12 - 0 = 12 12 < 12 => žádná změna (V,{X,F,Z}),Síarí(V) r, z} u {V}) = 12 Zcí({X, Y, Z}) - est(V) = 12 - 1 = 11 12 > 11 => -^V « {X, Y, Z} => síarí(y) > min(ecí(X),ecí(y),ecí(z)) síarí(y) > min(3, 5, 7) síarí(y) > 3 síarí(y) e (3, 7) (V,{X,Y,Z}),end(V) p({x, y, z} u {V}) = 12 Zcí(K) - est({X, Y, Z}) = 9 — 0 = 9 12 > 9 => -.{X, Y, Z} « V end(y) < max(ZsípO,Zsí(y),Zsí(Z)) => end(y) < max(7, 7, 8) => end(y) < 8 => end(V) e (3,8) Příklad 13.13 V nejlepším možném případě budou úlohy B a E naplánovány před úlohou C. orp(C) = InitLevel +cap(C) + > cap(X) + > cap(X) V ' V ' ^X«C V ' ^—>X??C kcap(X)>0 v ' = 4 +(-4) +0 +1 + 1 = 2 Může být úloha C naplánována po úloze A? orp(C\A « C) = InitLevel +cap(C) + can(X) + cap(X) = 4 +(-4) +(-3) +1 + 1 = -1 To znamená, že pokud by úloha A byla spuštěna před úlohou C, tak by úloze C v době jejího spuštění chyběla jedna jednotka zdroje. Tedy C nemůže být naplánováno po A. Hana Rudová, Fakulta informatiky, Masarykova univerzita 17 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 19.5 i) • P j = p™ax pro j {1,...,9} • Určení kritických cest 0+4=4 6-4 = 2 6 + 9 =15 15 - 9 =6 15 +■ S = 23 23 - S = 15 23 -H S = 31 31-S = 23 0+3=3 3-3=0 3 + 3=6 6-3 = 3 6 + 6 = 12 12 - 6 = 6 3 12 + 3 = 15 15 - 3 = 12 15 + 6 = 21 31-6 = 25 Horní rovnice u každé úlohy představuje S j + p j = Cj při dopředně proceduře, spodní rovnice ukazuje C" — p j = S" při zpětné proceduře. Červeně vybarvené šipky značí hrany kritických cest. • Minimální řezy grafu kritických cest: {3}, {4}, {2, 5}, {2, 8}, {6}, {7} • Minimální řez s nejnižší cenou je {2, 5}. • Redukce dob provádění: p-2 = 8, ps = 5 • Určení nových kritických cest 0+4=4 6-4 = 2 6 + S = 14 14 - S = 6 0+3=3 3-3=0 3 + 3=6 6-3 = 3 6 +■ 5 = 11 11 - 5 = 6 14 + S = 22 22 - S = 14 22 + 3 = 30 30 - S = 22 3 11+3 =14 14 - 3 = 11 14 +■ 6 = 20 30 - 6 = 24 Iniciální cena Fixní režijní náklady: C, max^O 9 31 - 4 = 124 Cena za provádění úloh: J2j=i cj = 4 + 7 + 5 + 4 + 5 + 8 + 9 + 7 + 6 55 ?Jmax) = 124 + 55 179 f(pjmax) Cena po jednom kroku algoritmu Fixní režijní náklady: 30 • 4 = 120 Hana Rudová, Fakulta informatiky, Masarykova univerzita 18 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Cena za provádění úloh naroste o c2 + C5 = 2. F(pj) = 120 + 57 = 177 Algoritmus skončí, když v grafu kritických cest neexistuje minimální řez R takový, že V j € R : p j > p™m, nebo když cena minimálního řezu s nejnižší cenou není menší než fixní režijní náklady cq . Hana Rudová, Fakulta informatiky, Masarykova univerzita 19 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 19.5 ii) iniciální kritické cesty: •1^2^4^5^6^7 •1^2^4^5^8 Gcp minimální řezy {1} {2} {4} {5} {6,8} {7,8} lze vylepšit? Ano Ano Ano Ano Ano Ano cena 3 2 3 3 5 2 Jeden z řezů s nejmenší cenou je {2}. Zredukování doby provádění všech úloh v tomto řezu, tedy pouze úlohu 2 na p2 = 1- nové kritické cesty: •1^2^4^5^6^7 •1^2^4^5^8 •3^4^5^6^7 •3 ^ 4 ^ 5 ^ 8 revidovaný Gcp Iniciální cena: F(Pj) = F(pfax) = Cmaxc0 + £^ = 21- 5 + 9 + 7 + 5 + 6 + 7 + 9 + 9 + 6 = 163 Cena po jednom kroku: F(pj) = F(pfax) - c0 + c2{pV?ax - p2) = 163 - 5 + 2 = 160 Hana Rudová, Fakulta informatiky, Masarykova univerzita 20 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 21.8 Pravidlo EDD vybírá prioritně úlohy s nejdřívějším termínem dokončení. Protože máme termíny dostupnosti, není možné rozvrh vytvořit jednorázově na začátku. V čase 0 máme dostupnout pouze úlohu 3, musíme ji tedy vybrat. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Znovu se rozhodujeme po dokončení úlohy 3 v čase 3. Nemáme ale žádné dostupné úlohy. V čase 4 přijdou úlohy 2 a 4 . Vybereme tu s menším dir tedy úlohu |. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 V čase 6 se rozhodujeme mezi úlohami Jal, vybíráme úlohu 1. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Další rozhodování následuje v čase 8, vybíráme z úloh 4 a 5 . Úloha 4 má dřívější termín dokončení a proto ji vybereme. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 V čase 9 už nám zbývá pouze poslední úloha 5 , proto ji vybereme. -1-1-1-1-1-1-1-1-1-1-1-1-> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Koncové časy tedy jsou C\ = 8, C2 = 6, C3 = 3, C4 = 9 a C5 = 12. Hodnota účelové funkce tmax = max({d -dl\l* = 1 t=Tj V každém čase běží nejvýše jedna úloha (v rozvrhu ale mohou vzniknout mezery kvůli termínům dostupnosti). Suma přes všechny úlohy stačí, díky jednotkovému trvání úloh (tj. nemohou se překrývat, pokud nezačínají ve stejném čase. Překrývání by tedy způsobilo, že tato suma bude větší než 1). n Víe{0,.,/ř}:^a;ít (2,1) (1,1) - J2: (1,2) (3,2) (2,2) - J3: (2,3) -> (1,3) • Doby provádění: - pn = l,p2i = 2,p3i = 4, - Pl2 = 3,p22 = l,ř>32 = 3, " Pl3 = 4,P23 = 2 Hana Rudová, Fakulta informatiky, Masarykova univerzita 25 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 27.3 Nejprve je třeba provést inicializaci: íl := {(2,1), (1,2), (3, 3)} nj := 0 V(i,;/)€íí Nyní začínáme s prázdným rozvrhem. V první iteraci musíme určit, kdy nejdříve může nějaká úloha z íl skončit. t(íl) := min^j^nirij + pij} = mm{4+0,2 + 0,3 + 0}=2 Minimum je realizováno úlohou (1,2), tedy na stroji i* = 1. Nyní musíme určit množinu íl' C íl úloh, které přidáme do rozvrhu. íl' := {(i*,j)|ri.J-<í(íí)} = {(l,2)} Do rozvrhu tedy přidáme úlohu (1,2), která poběží od času 0 do času 2 na stroji 1. Zároveň musíme aktualizovat množinu úloh s narozvrhovanými předchůdci, tedy odstraníme rozvrhnutou úlohu a přidáme její následníky. íl := íl \ {(1,2)} U {(2, 2)} = {(2,1), (2, 2), (3, 3)} r22 := 2 Nyní můžeme jít znovu na výběr první úlohy, která by měla skončit. t(íl) := min^j^nirij + pij} = mm{4 + 0,1 + 2,3 + 0} = 3 Nyní je minimum dosaženo na strojích 2 a 3. Vybereme z nich pro větvení stroj s nejnižším identifikátorem, tedy stroj 2. Určíme množinu úloh pro přidání do rozvrhu: íl' := {(2,j)\r2j < 3} = {(2,1), (2, 2)} Do jednoho rozvrhu přidáme úlohu (2,1), která poběží od času 0 do času 4 na stroji 2 a aktualizujeme množinu íl. íl := íí\ {(2,1)} U {(3,1)} = {(3,1), (2, 2), (3, 3)} r3i := 4 Do druhého rozvrhu přidáme úlohu (2,2), která poběží na stroji č. 2 od času 2 do času 3. Opět aktualizuje množinu dostupných úloh a počátečních časů. íl := íl \ {(2, 2)} U {(3, 2)} = {(2,1), (3, 2), (3, 3)} T32 ■= 3 Nyní bychom mohli pro každý částečný rozvrh pokračovat dál. Hana Rudová, Fakulta informatiky, Masarykova univerzita 26 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 29.8 Rozvrh pro první úlohu: 1 T T" I 10 T 0123456789 10 11 Označíme -/Vijfe jako neproduktivní dobu na stroji i pro úlohu, která je kandidátem na pozici k. 2. pozice Rozvrh pro kandidátní úlohu 2 na druhou pozici (J2 = 2) 1 01234567 Rozvrh pro kandidátní úlohu 3 na druhou pozici (J2 = 3) 1 10 11 1 1 1 i 3 1 1 1 1 1 1 1 10 11 Hana Rudová, Fakulta informatiky, Masarykova univerzita 27 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Rozvrh pro kandidátní úlohu 4 na druhou pozici (J2 = 4) —i-r 10 11 Výpočet neproduktivní doby pro výše uvedené kandidátní úlohy na druhou pozici: h i 12 3 i 12 3 Eli Nij3 2 3 5 5 8 2 3 7 0 3 2 110 5 2 4 2 4 4 0 0 1 3. pozice Rozvrh pro kandidátní úlohu 2 na třetí pozici (jz = 2) 1 I 10 01234567 Rozvrh pro kandidátní úlohu 3 na třetí pozici (jz = 3) 11 1 1 4 ■1 2 1 4 3 1 3 1 1 1 1 1 1 1 10 11 Hana Rudová, Fakulta informatiky, Masarykova univerzita 28 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Výpočet neproduktivní doby pro výše uvedené kandidátní úlohy na třetí pozici: h i 12 3 i 12 3 Eli NiJa 2 6 6 9 0 2 2 4 3 4 4 8 2 0 0 2 4. pozice Rozvrh pro poslední úlohu 2 na čtvrtou pozici (J4 = 2) 1 1 4 ■1 mu 2 2 1 4 3 1 3 2 1 1 1 1 1 1 0123456789 10 11 Výpočet neproduktivní doby pro poslední úlohu na čtvrté pozici: 34 i 12 3 i 12 3 ELi NiiU 2 8 8 11 0 4 0 4 Výsledný rozvrh Pořadí úloh při použití heuristiky padnoucího profilu při fixované první úloze je 1, 4, 3 a 2. Ml 1 4 3 2 1 4 4 3 2 1 4 4 M2 1 4 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 M3 1 3 2 1 3 2 í 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 doba cyklu = 9 Hana Rudová, Fakulta informatiky, Masarykova univerzita 29 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 32.5 Řešíme problém intervalového rozvrhování. Všechny úlohy mají jednotkovou váhu a máme dva identické stroje. Máme k dispozici optimální algoritmus. Nejprve musíme seřadit úlohy podle času dostupnosti. Dostaneme stejné pořadí jako v zadání. Nyní můžeme začít s jednotlivými iteracemi: j = 1: V čase r\ = 1 máme dostupný stroj, proto úlohu 1 rozvrhneme na stroj 1 i -1-1-1-1-1-1-1-1-1-1-*■ 123456789 10 11 j = 2: V čase r 2 = 2 máme volný druhý stroj, proto i úlohu 2 můžeme rovnou rozvrhnout, a to na stroj 2 2 1 -1-1-1-1-1-1-1-1-1-1-> 123456789 10 11 j = 3: V čase r 3 = 3 není volný žádný stroj. Poslední dokončenou úlohou bude úloha 2 (tedy j* = 2) v čase 5. Úloha 3 končí ve stejný čas, podle algoritmu tedy rozvrhneme úlohu 3 místo úlohy 2, protože neplatí podmínka, že C3 > C2 ■ Optimální řešení bychom ovšem získali i v případě, že bychom ponechali rozvrhnutou úlohu 2 (maximální počet realizovaných úloh by byl stejný), navíc je však v tomto řešení obsazený interval 2-3. 3 1 -1-1-1-1-1-1-1-1-1-1-* 123456789 10 11 j = 4: V čase r4 = 6 je opět volný stroj, úlohu 4 můžeme rozvrhnout. 1 4 -1-1-1-1-1-1-1-1-1-1-> 123456789 10 11 j = 5: V čase r 5 = 6 máme volný i druhý stroj, proto úlohu 5 máme kde rozvrhnout. 3 5 1 4 -1-1-1-1-1-1-1-1-1-1-> 123456789 10 11 j = 6: V čase r§ = 8 nemáme žádný volný stroj. Poslední úlohou je úloha 4 končící v čase 11. Úloha 8 končí dřív, už v čase 9, proto ji rozvrhneme místo úlohy 4. 3 5 1 6 -1-1-1-1-1-1-1-1-1-1-> 123456789 10 11 Hana Rudová, Fakulta informatiky, Masarykova univerzita 30 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 j = 7: V čase r-j = 9 máme dostupný stroj, proto úlohu 7 můžeme rozvrhnout. 3 5 1 6 7 -1-1-1-1-1-1-1-1-1-1— 123456789 10 11 Množina všech rozvržených úloh J = {1,3, 5, 6, 7}. Hana Rudová, Fakulta informatiky, Masarykova univerzita 31 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Příklad 33.3 Máme zadané úlohy s časovou rezervou a váhami, chceme je rozvrhnout na dva stroje. Použijeme prioritní index Ij = J/^J . Následující diagram znázorňuje intervaly, ve kterých je možné jednotlivé úlohy rozvrhnout. Červené úlohy vyžadují stroj 1, modré stroj 2 a fialové stroj 1 nebo 2 (v dalších diagramech už barvy nenesou žádný význam). úloha 6 (p6 = 2) úloha 5 (p5 = 4) úloha 4 (p4 = 3) úloha 3 (j>3 = 2) úloha 2 (p2 = 3) úloha 1 (p! = 3) 0123456789 10 Nyní můžeme spočítat priority pro jednotlivé úlohy: úloha 1 2 3 4 5 6 h 3 6 V2 V2 2 2/3 Dále budeme potřebovat počty úloh, které lze přiřadit stroji i v intervalu [t — 1, í], tj. tp^ čas 1 2 3 4 5 6 7 8 9 10 3 3 4 4 3 3 2 1 1 1 Í>2t 1 2 3 4 4 3 1 1 1 1 Prioritní index stroje budeme počítat jako g(ip^t+i,tpi,t+Pj) = (J2iíi i>i,t+i)/Pj 1. Vybereme úlohu s nejnižším indexem, tj. úlohu 3 (pz = 2) (úloha 4 má stejný prioritní index, ale vyšší identifikátor). Nyní pro ni musíme vybrat stroj a čas, tedy určit jejich priority. Úloha 3 vyžaduje stroj 1, takže stačí uvažovat startovní časy 0,1 a 2 na tomto stroji. 5(^1,1^1,2) = (3 + 3)/2 = 3 5(^1,2,^1,3) = (3 + 4)/2 = 3,5 ff(^i,3,^i,4) = (4 + 4)/2 = 4 Minimum vyjde pro čas 0. Proto úlohu 3 rozvrhneme v čase 0-2 na stroji 1. 3 -1-1-1-1-1-1-1-1-1-1-> 0123456789 10 2. Vybereme další úlohu s nejnižší prioritou, tj. úlohu 4 (p4 = 3). Tato úloha musí běžet na stroji 2. Opět musíme vybrat čas. 5(^2,2,..., ^2,4) = (2 + 3 + 4)/3 = 3 5(^2,3, ...,^2,5) = (3 + 4 + 4)/3^3,7 Hana Rudová, Fakulta informatiky, Masarykova univerzita 32 PA167 Rozvrhování: řešení vybraných příkladů 11. dubna 2022 Minimum vyjde pro počáteční čas 1. Proto úlohu 4 rozvrhneme na stroj 2 v čase 1-4. 4 0123456789 10 3. Vybereme další úlohu, tentokrát úlohu 6 (pe = 2). Ta musí také běžet na stroji 2. Stroj 2 se uvolní až v čase 4, úloha 6 musí skončit v čase 6, zbývá tedy jediná možnost, jak úlohu rozvrhnout, a to je interval 4-6 na stroji 2. 0123456789 10 4. Další úloha k rozvrhnutí je úloha 5 (ps = 4), která musí běžet na stroji 1. Potenciální startovní časy jsou 2 a 3 (po dokončení úlohy 3). g(il>i,3,...,il>i,6) = (4 + 4 + 3 + 3)/4 = 3.5 fl(^i,4,..., ^i.t) = (4 + 3 + 3 + 2)/4 = 3 Zvolíme tedy čas 3 a úlohu 5 rozvrhneme na stroji 1 v intervalu 3-7. 4 6 0123456789 10 5. Další úloha je číslo 1 (pi = 3), která může běžet na libovolném stroji. V možném čase 0-6 jsou ovšem volné pouze intervaly délky 1, kam se tato úloha nemůže vejít a proto nebude rozvržena. 6. Poslední úlohou je číslo 2 (j>2 = 3), která také může běžet na libovolném stroji. Může být poprvé na stroji 1 rozvržena až v čase 7, což je také poslední možný čas. Pro stroj 2 připadají v úvahu časy 6 a 7. = (1 + 1 + l)/3 = 1 = (1 + 1 + l)/3 = 1 = (1 + 1 + l)/3 = 1 Zjevně jsou všechny možnosti totožné, proto z nich vybereme stroj 2 a čas 7, který minimalizuje čas dokončení poslední úlohy. Výsledný rozvrh tedy bude vypadat následovně. Úlohu 1 se nepodařilo rozvrhnout. 4 6 2 9(^1,8, ■ ■ ■■,Í>2$) 9(^2,8, ■■ ■,^2,10) 10 Hana Rudová, Fakulta informatiky, Masarykova univerzita 33