Rezervace 9. května 2022 Q Úvod Q Intervalové rozvrhování Q Rezervační systém s rezervou Rezervační systém • m strojů zapojených paralelně • n úloh s • dobou provádění pi,..., pn • termíny dostupnosti ri,..., rn termíny dokončení c/i,..., dn 9 váhy í/i/i, • • • 5 wn • Úloha musí být prováděna v rámci daného časového intervalu • termín dostupnosti a dokončení nelze porušit • Nemusí být možné realizovat všechny úlohy • Cíl: vyber podmnožinu úloh, • pro kterou existuje konzistentní rozvrh • která maximalizuje danou objektivní funkci • maximalizace počtu prováděných úloh • maximalizace celkového množství provádění • maximalizace profitu realizovaných úloh (zadané váhy) Hana Rudová, Fl MU: Rezervace 2 9. května 2022 Základní modely • Systém bez rezervy • úlohy trvají od termínu dostupnosti do termínu dokončení, tj. P j = dj ~ rJ • mluvíme o pevných intervalech nebo o intervalovém rozvrhování • Systémy s rezervou • interval mezi termínem dostupnosti a dokončení může mít nějakou rezervu, tj. pj < dj — rj Hana Rudová, Fl MU: Rezervace 3 9. kvetná 2022 Aplikace rezervačních systémů • Pronájem aut • čtyři typy aut: subcompact, střední velikost, plná velikost, sportovní typ • pevné množství každého typu • stroj = typ auta • úloha = zákazník požadující auto • zákazník může požadovat určitý(é) typ(y) auta • úloha může být prováděna na podmnožině strojů • v případě nedostatku některého typu auta může být nabídnut v některých případech silnější typ auta • Rezervace pokojů v hotelu • Rezervace strojů v továrně Hana Rudová, Fl MU: Rezervace 4 9. května 2022 Intervalové rozvrhování • m strojů zapojených paralelně • n úloh, pro úlohu j zadán • termín dostupnosti rj • termín dokončení dj • doba provádění pj = dj — rj • množina Mj strojů, na kterých může být úloha j prováděna • Wij\ profit z provádění úlohy j na stroji / • Cíl: maximalizovat profit z prováděných úloh • w,j = 1: maximalizovat počet realizovaných úloh • w,j = wy. maximalizovat vážený počet realizovaných úloh Hana Rudová, Fl MU: Rezervace 5 9. května 2022 Formulace celočíselného programování • Časové periody 1,..., H • J\\ množina úloh, která potřebuje provádění v čase / (známe předem!) • Xjj = 1 pokud je úloha j prováděna na stroji / Xjj — 0 jinak a Maximalizace m n i=i j=i za předpokladu: úloha běží nejvýše na jednom stroji m ^2xíj<1 J = 1,...,A7 /=1 v každém čase běží na každém stroji nejvýše jedna úloha ^2> Cj* then nezařazuj j do J else přiřaď j stroji 7* Hana Rudová, Fl MU: Rezervace 8 9. května 2022 Příklad: jednotková váha & identické stroje j 1 2 3 4 5 6 7 8 2 stroje a 8 úloh: 0 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Iterace 1: 7 = 1 Iterace 2: j = 2 Iterace 4: J = 4 M1 M2 0 M1 M2 0 M1 Iterace 3: j = 3, j* = 1 M2 0 M1 M2 0 T 5 5 T 5 5 "T* 10 10 "T* 10 10 Hana Rudová, Fl MU: Rezervace 9. května 2022 Příklad: jednotková váha & identické stroje j 1 2 3 4 5 6 7 8 2 stroje a 8 úloh: 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Iterace 5: 7 = 5 Iterace 7: j = 7 M1 M2 0 M1 Iterace 6: j = 6J* =4 M2 0 M1 M2 0 M1 Iterace 8: j = 8,j* =7 M2 0 Hana Rudová, Fl MU: Rezervace 5 5 10 10 3 5 2 CD I - 10 3 5 7 2 6 i • 10 3 5 8 2 6 i • 10 9. května 2022 Jednotková váha a nelimitovaný počet identických stroju • w;j = 1 pro všechna i j • Všechny úlohy musí být realizovány • Cíl: použít minimální počet strojů • Algoritmus dávající optimální řešení Předpokládejme: r\ < • • • < rn M = 0 (M množina použitých strojů) i := 0 for j = 1 to n do if stroj z M je volný v rj then přiřaď j na volný stroj else / := / + 1 M := M U {i} přiřaď úlohu j na stroj / Hana Rudová, Fl MU: Rezervace 11 9. května 2022 Příklad: jednotková váha a nelimitovaný počet identických strojů M3 M2 M1 ■ 0 M3 M2 M1 ■ 0 M3 M2 M1 1 0 5 Hana Rudová, Fl MU: Rezervace 10 I ~ 10 T 10 j i 2 3 4 5 6 7 8 n 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 12 9. května 2022 Příklad: jednotková váha a nelimitovaný počet identických strojů M3 M2 M1 0 M3 M2 M1 0 M3 M2 M1 1 0 5 Hana Rudová, Fl MU: Rezervace 10 i 10 10 j i 2 3 4 5 6 7 8 n 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 13 9. května 2022 Příklad: jednotková váha a nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 ľj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Hana Rudová, Fl MU: Rezervace 14 9. května 2022 Barvení grafu Problém barvení grafu • Je možné obarvit vrcholy grafu s použitím n barev tak, aby žádné dva sousední vrcholy nebyly obarveny stejnou barvou? Chromatické číslo grafu • Minimální počet barev n nutný k obarvení grafu tak, by žádné dva sousední vrcholy nebyly obarveny stejnou barvou. NP-úplný problém Hana Rudová, Fl MU: Rezervace 15 Reformulace na problém barvení grafu Problém s jednotkovou vahou a nelimitovaným počtem identických strojů lze reformulovat na problém barvení grafu • vrchol = úloha • hrana (y, k) znamená, že se úlohy j a k překrývají v čase • každá barva odpovídá jednomu stroji • přiřaď barvu (tj. stroj) každému vrcholu tak, že dva sousední vrcholy (překrývají se v čase) mají různou barvu (tj. stroje) Poznámky: • obecný problém existence obarvení grafu m barvami je NP-úplný • uvažovaný rezervační problém je speciálním (jednodušším) případem problému barvení grafu 9 heuristiky diskutovány v kapitole o timetabling Hana Rudová, Fl MU: Rezervace 16 9. května 2022 Příklad: reformulace j 1 2 3 4 5 6 7 8 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Odpovídající řešení problému barvení grafu: Hana Rudová, Fl MU: Rezervace 17 9. května 2022 Rezervační systém s rezervou • Rezervační systém s rezervou: pj < dj — rj • Triviální případ • doby provádění = 1, identické váhy identické stroje • řešení opět dekompozicí v čase • Maximalizace váženého počtu aktivit • NP-těžký problém řešení heuristikami • kompozitní řídící pravidlo • předzpracování: určení flexibility úloh a strojů • algoritmus: nejméně flexibilní úloha na nejméně flexibilním stroji první Hana Rudová, Fl MU: Rezervace 18 9. května 2022 Předzpracování ípit\ počet úloh, které mohou být přiřazeny na stroj / během intervalu [t — 1, t] 9 možné využití stroje / v čase t 9 čím vyšší hodnota, tím je zdroj / v tomto čase flexibilnější Mj\\ počet strojů, které mohou být přiřazeny úloze j • čím vyšší hodnota, tím je úloha j flexibilnější Hana Rudová, Fl MU: Rezervace 19 9. května 2022 Prioritní indexy 9 Prioritní index pro úlohu j\ lj = f(wj/pj, \ Mj\) • uspořádání úloh podle: l\ < I2 < • • • < ln • čím menší je \Mj\, tím nižší je lj • čím vyšší je wj/pj, tím nižší je lj • snažíme se dát přednost kratším úlohám, protože maximalizujeme počet vážených provedených aktivit a delší úlohy jsou náročnější • např. /; = • Prioritní index pro stroj • vybírá stroj pro úlohu • jestliže úloha potřebuje stroj v [ŕ, t + pj\ pak výběr stroje / záleží na funkci s faktory V^t+i?...,tj. na g(ýi,t+i,---,ýi,t+Pj) • např. g(il>i,t+u • • >^i,t+Pj) = ^Xľ^/,t+/^ /Pj nebo g(ý;,t+i, • • •, ^/,t+Pi) = max(^jt+i5..., ^i,t+Pi) Hana Rudová, Fl MU: Rezervace 20 9. května 2022 Algoritmus maximalizace váženého počtu aktivit O 7 = 1 Q Vyber úlohu j s nejnižším lj a vyber mezi stroji a dostupnými časy zdroj a čas s nejnižší £(Vv+i>--->Vv+p/) Zruš úlohu j jestliže nemůže být přiřazena ani jednomu stroji v žádném čase O Jestliže j = n STOP jinak nastav j = j + 1 a běž na krok 2 Hana Rudová, Fl MU: Rezervace 21 9. května 2022 Cvičení: maximalizace váženého počtu aktivit • Nalezněte rozvrh pro daný problém Úlohy 1 2 3 4 5 6 7 Pj 3 10 9 4 6 5 3 Wj 2 3 3 2 1 2 3 n 5 0 2 3 2 4 5 dj 12 10 20 15 18 19 14 Mj {1,3} {1,2} {1,2,3} {2,3} {1} {1} {1,2} I lv'l 9 pro // = ^-r- a K J Wj/Pj g{lpi,t+U ■ ■ ■ , VV+p/) = (E/Li /Py a Rešení: Úlohy 7 6 1 4 5 2 Stroje 2 13 3 12 Casy 11-14 14-19 5-8 11-15 2-8 0-10 úlohu 3 nelze umístit Hana Rudová, Fl MU: Rezervace 22 9. kvetná 2022 Shrnutí Rezervace • Intervalové rozvrhování (rezervační systém bez rezervy) celočíselné programování • jednotková doba trvání: formulace problému přiřazení (řešení pro každou čas. jednotku zvlášť) • jednotková váha & identické stroje (maximalizace počtu provedených aktivit) • jednotková váha & nelimitovaný počet identických strojů 9 Rezervační systém s rezervou • kompozitní řídící pravidlo Hana Rudová, Fl MU: Rezervace 23 9. května 2022 Rozvrhování jako timetabling 9. května 2022 O Úvod Q Rozvrhování s operátory Q Rozvrhování s pracovní sílou Rozvrhování = timetabling • Doposud: rozvrhování = scheduling Nyní: rozvrhování = timetabling • důraz kladen na časové umístění objektů • vazby na časové uspořádání mezi objekty hrají malou roli 9 Omezení operátorů/nástrojů (operator/tool) • mnoho operátorů 9 úloha potřebuje jeden nebo více odlišných operátorů • úlohy vyžadující stejné operátory nemohou běžet zároveň • možné cíle: rozvržení všech úloh v rámci časového horizontu H nebo minimalizace makespan • Omezení pracovní síly • R identických pracovníků = jeden zdroj kapacity R • každá úloha potřebuje několik pracovníků • celkový počet pracovníků nesmí být nikdy překročen Hana Rudová, Fl MU: Rozvrhování jako timetabling 25 9. května 2022 Rozvrhování jako problém plánování projektu s omezenými zdroji • Problém plánování projektu s omezenými zdroji resource-co n st rained projed scheduling problem (RCPSP) • n úloh • N zdrojů • R; kapacita zdroje / • pj doba provádění úlohy j • Rij požadavek úlohy j na zdroj / • Precj (přímí) předchůdci úlohy j • Rozvrhování s operátory • R; = 1 pro všechna i = 1... N • Rozvrhování s pracovní sílou • N = 1 • Oba problémy rozvrhování stále velmi obtížné • i při pj = 1 NP-těžké operátoři = barvení grafu pracovní síla = bin-packing Hana Rudová, Fl MU: Rozvrhování jako timetabling 26 9. května 2022 Rozvrhování s operátory jako barvení grafu Omezíme se na problém s jednotkovou dobou trvání • Úloha = uzel o Úlohy potřebují stejného operátora = hrana mezi uzly 9 Přiřazení barev (= času) uzlům • sousední uzly musí mít různé barvy tj. úlohy se stejným operátorem musí být prováděny v různých časech o Problém existence řešení o tj. zadán časový horizont H a hledám rozvrh v rámci horizontu • může být graf obarven H barvami? • Optimalizační problém • tj. minimalizace makespan 9 jaký nejmenší počet barev je třeba? • chromatické číslo grafu Hana Rudová, Fl MU: Rozvrhování jako timetabling 27 9. května 2022 Heuristiky pro barvení grafu • Stupeň uzlu • počet hran spojených s uzlem • Úroveň saturace • počet různých barev spojených s uzlem • Intuice • obarvi uzly s vyšším stupněm dříve obarvi uzly s vyšší úrovní saturace dříve • Algoritmus O uspořádej uzly v klesajícím pořadí podle jejich stupně O použij barvu 1 pro první uzel O vyber neobarvený uzel s maximální úrovní saturace v případě volby z nich vyber uzel s maximálním stupněm v neobarveném podgrafu O obarvi vybraný uzel s nejmenší možnou barvou O jestliže jsou všechny uzly obarveny STOP jinak běž na krok 3 Hana Rudová, Fl MU: Rozvrhování jako timetabling 28 9. května 2022 Příklad: rozvrhování schůzek Vytvoř rozvrh pro 5 schůzek se 4 lidmi • schůzka = úloha, člověk = operátor • všechny schůzky trvají jednu hodinu 1 2 3 4 5 Joe Lisa Jane Larry 110 11 1110 0 10 10 0 0 10 11 Můžeme vybrat buď úlohu 1 nebo úlohu 2 Např. vybereme 1 a obarvíme barvou 1 Hana Rudová, Fl MU: Rozvrhování jako timetabling 29 9. května 2022 Příklad: rozvrhování schůzek (dokončení) Úroveň saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení V posledním kroku obarvi 3 stejnou barvou jako 4 =>celkem 4 barvy, tj. makespan=4 Hana Rudová, Fl MU: Rozvrhování jako timetabling 30 9. května 2022 Příklad: rezervace vs. rozvrhování s operátory Předpokládejme, že máme rezervační systém Úloha 1 2 3 Pj 2 3 1 rJ 0 2 3 dj 2 5 4 Lze přeformulovat na rozvrhování s operátory Úloha 12 3 Operátor 1 Operátor 2 Operátor 3 Operátor 4 Operátor 5 1 0 0 1 0 0 0 1 0 0 11 0 1 0 úloha 1 běží v čase [0,2] úloha 2 běží v čase [2,5] úloha 3 běží v čase [3,4] Hana Rudová, Fl MU: Rozvrhování jako timetabling 31 9. května 2022 Vztah k rezervačním systémům 9 Rozvrhování s operátory blízké rezervačnímu systému bez rezervy 9 Oba problémy reformulovány na problém barvení grafu • rezervace: hrana = dvě úlohy se překrývají v čase • rozvrhování: hrana = dvě úlohy požadují stejného operátora • Rozdíl ve složitosti • rezervace: překrývající se časové jednotky jdou po sobě • rozvrhování: úlohy často nevyžadují pouze sousední operátory rozvrhování s operátory je obtížnější problém Hana Rudová, Fl MU: Rozvrhování jako timetabling 32 9. května 2022 Rozvrhování s pracovní sílou: aplikace o Řízení projektu ve stavebním průmyslu 9 dodavatel má realizovat n aktivit • doba trvání aktivity j je pj 9 aktivita j požaduje pracovní skupinu velikosti Wj 9 precedenční omezení na aktivity • dodavatel má W pracovníků • cíl: dokončit všechny aktivity v minimálním čase • Rozvrhování zkoušek 9 všechny zkoušky mají stejnou dobu trvání • všechny zkoušky jsou v místnosti s W sedadly • počet studentů předmětu j, kteří skládají zkoušku, je Wj 9 několik zkoušek může být narozvrhováno ve stejné místnosti, pokud je postačující počet sedadel • cíl: zkonstruovat rozvrh tak, že jsou všechny zkoušky narozvrhovány v minimálním čase Hana Rudová, Fl MU: Rozvrhování jako timetabling 33 9. května 2022 Reformulace pomocí problému plnění košů (bin-packing) Problém plnění košů každý koš má kapacitu W předměty velikosti Wj • cíl: naplnit minimální počet košů Uvažujme speciální problém rozvrhování s pracovní silou • předpokládejme jednotkovou dobu trvání • nelimitovaný počet strojů • minimalizace makespan Rozvrhování s pracovní silou jako problém plnění košů • předmět = úloha (s počtem pracovníků Wj) 9 kapacita koše = celkový počet pracovníků W • 1 koš = 1 časová jednotka • minimalizace počtu košů = minimalizace makespan Řešení problému plnění košů • NP-těžký problém • vyvinuta řada heuristik heuristika prvního padnoucího (first fit FF) koše Víme' Že: Cmax(FF) < ^Cmax(OPT) + 2 10 Hana Rudová, Fl MU: Rozvrhování jako timetabling 34 9. května 2022 Příklad: heuristika prvního padnoucího koše (FF) • Předpokládejme 18 úloh a l/l/=2100 • úloha 1-6 požaduje 301 jednotek zdroje • úloha 7-12 požaduje 701 jednotek zdroje • úloha 13-18 požaduje 1051 jednotek zdroje • FF heuristika: • přiřadíme prvních 6 úloh na jeden zdroj (301x6=1806) • pak přiřadíme vždy dvě úlohy na další tři zdroje (701x2=1402) • pak přiřadíme právě jednu úlohu na každý zdroj • Velmi nekvalitní řešení vzhledem k uspořádání úloh Hana Rudová, Fl MU: Rozvrhování jako timetabling 35 9. května 2022 Heuristika prvního padnoucí koše se zmenšováním úloh • Zlepšení FF heuristiky • Uspořádání úloh od nejdelší k nejkratší 9 První padnoucí koš se zmenšováním úloh (first fit decreasing FFD) • Řešení příkladu: • seřadíme úlohy dle požadovaných jednotek zdroje, tj. 13,14,15,16,17,18,7,8,9,10,11,12,1,2,3,4,5,6 • úlohy bereme postupně a dáváme je na první zdroj, kam se vejdou 13 dáme na zdroj 1, 14 dáme na zdroj 2, 18 dáme na zdroj 6 7 dáme na zdroj 1, 8 dáme na zdroj 2, 12 dáme na zdroj 6 1 dáme na zdroj 1, 2 dáme na zdroj 2, 6 dáme na zdroj 6 • Víme, že Cmax{FFD) < ^Cmax(OPT)+4 o FF i FFD mohou být rozšířeny o různé termíny dostupnosti Hana Rudová, Fl MU: Rozvrhování jako timetabling 36 9. května 2022 Diskuse • Uvažovali jsme reprezentanty různých problémů 9 V praxi • obecnější problémy (kombinace všech uvažovaných rysů problémů zároveň) • dynamické rezervační problémy • uvažování ceny (management zisku) • přerušení aktivit • . .. Hana Rudová, Fl MU: Rozvrhování jako timetabling 37 9. května 2022 Shrnutí Rezervace • Intervalové rozvrhování (rezervační systém bez rezervy) celočíselné programování • jednotková doba trvání: formulace problému přiřazení (řešení pro každou čas. jednotku zvlášť) • jednotková váha & identické stroje (maximalizace počtu provedených aktivit) • jednotková váha & nelimitovaný počet identických strojů • Rezervační systém s rezervou • kompozitní řídící pravidlo Timetabling o plánování projektu s omezenými zdroji (RCPSP) • rozvrhování s operátory a barvení grafu • heuristika pro barvení grafu 9 rozvrhování s pracovní silou a problém plnění košů • heuristika prvního padnoucího koše • heuristika prvního padnoucího koše se zmenšováním úloh Hana Rudová, Fl MU: Rozvrhování jako timetabling 38 9. května 2022