Rezervace 2. května 2023 1 Úvod 2 Intervalové rozvrhování 3 Rezervační systém s rezervou Rezervační systém m strojů zapojených paralelně n úloh s dobou provádění p1, . . . , pn termíny dostupnosti r1, . . . , rn termíny dokončení d1, . . . , dn váhy w1, . . . , 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á, FI MU: Rezervace 2 2. května 2023 Základní modely Systém bez rezervy úlohy trvají od termínu dostupnosti do termínu dokončení, tj. pj = 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á, FI MU: Rezervace 3 2. května 2023 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á, FI MU: Rezervace 4 2. května 2023 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 i Cíl: maximalizovat profit z prováděných úloh wij = 1: maximalizovat počet realizovaných úloh wij = wj : maximalizovat vážený počet realizovaných úloh Hana Rudová, FI MU: Rezervace 5 2. května 2023 Formulace celočíselného programování Časové periody 1, . . . , H Jl : množina úloh, která potřebuje provádění v čase l (známe předem!) xij = 1 pokud je úloha j prováděna na stroji i xij = 0 jinak Maximalizace m i=1 n j=1 wij xij za předpokladu: úloha běží nejvýše na jednom stroji m i=1 xij ≤ 1 j = 1, . . . , n v každém čase běží na každém stroji nejvýše jedna úloha j∈Jl xij ≤ 1 i = 1, . . . , m l = 1, . . . , H provádění úlohy j na stroji i: xij ∈ {0, 1} Hana Rudová, FI MU: Rezervace 6 2. května 2023 Jednotková doba trvání Každá úloha je dostupná přesně 1 časovou jednotku Co z toho plyne? Problém lze rozdělit na nezavislé problémy víme přesně, které úlohy i jsou prováděny v každé časové jednotce jeden podproblém pro každou časovou jednotku Výsledný problém pro časovou jednotku l: Maximalizace m i=1 n j=1 wij xij za předpokladu m i=1 xij ≤ 1 j = 1, . . . , n j∈Jl xij ≤ 1 i = 1, . . . , m xij ∈ {0, 1} Jedná se o problém přiřazení (assignment problem) problém řešitelný v polynomiálním čase Hana Rudová, FI MU: Rezervace 7 2. května 2023 Jednotková váha & identické stroje wij = 1; Mj = {1, . . . , m} pro všechna i, j; obecná pj tedy stroje jsou identické a cíl je maximalizovat počet realizovaných úloh nejednotková pj , nelze tedy řešit rozkladem v čase Algoritmus dávající optimální řešení Předpokládejme: r1 ≤ · · · ≤ rn J = ∅ (J je množina už vybraných úloh pro provádění) for j = 1 to n do if existuje stroj dostupný v čase rj then přiřaď j tomuto stroji J := J ∪ {j} else urči úlohu j∗ takovou, že Cj∗ = maxk∈J Ck = maxk∈J (rk + pk ) if Cj = rj + pj > Cj∗ then nezařazuj j do J else přiřaď j stroji j∗ (nová úloha skončí dříve nebo zároveň) J := J ∪ {j}\{j∗ } Hana Rudová, FI MU: Rezervace 8 2. května 2023 Příklad: jednotková váha & identické stroje 2 stroje a 8 úloh: j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Iterace 1: j = 1 1 1050 M2 M1 Iterace 2: j = 2 2 1 1050 M2 M1 Iterace 3: j = 3, j∗ = 1 3 2 1050 M2 M1 Iterace 4: j = 4 4 3 2 1050 M2 M1 Hana Rudová, FI MU: Rezervace 9 2. května 2023 Příklad: jednotková váha & identické stroje 2 stroje a 8 úloh: j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 Iterace 5: j = 5 5 4 3 2 1050 M2 M1 Iterace 6: j = 6, j∗ = 4 6 53 2 1050 M2 M1 Iterace 7: j = 7 7 6 53 2 1050 M2 M1 Iterace 8: j = 8, j∗ = 7 8 6 53 2 1050 M2 M1 Hana Rudová, FI MU: Rezervace 10 2. května 2023 Nelimitovaný počet identických strojů Všechny úlohy musí být realizovány tj. váha úloh nehraje roli Cíl: použít minimální počet strojů Algoritmus dávající optimální řešení Předpokladejme: r1 ≤ · · · ≤ rn M = ∅ (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 i := i + 1 M := M ∪ {i} přiřaď úlohu j na stroj i Hana Rudová, FI MU: Rezervace 11 2. května 2023 Příklad: nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 1 1050 M3 M2 M1 2 1 1050 M3 M2 M1 3 2 1 1050 M3 M2 M1 Hana Rudová, FI MU: Rezervace 12 2. května 2023 Příklad: nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 4 3 2 1 1050 M3 M2 M1 5 4 3 2 1 1050 M3 M2 M1 6 6 5 4 3 2 1 1050 M3 M2 M1 Hana Rudová, FI MU: Rezervace 13 2. května 2023 Příklad: nelimitovaný počet identických strojů j 1 2 3 4 5 6 7 8 rj 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 7 6 6 5 4 3 2 1 1050 M3 M2 M1 8M4 7 6 6 5 4 3 2 1 1050 M3 M2 M1 Hana Rudová, FI MU: Rezervace 14 2. května 2023 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á, FI MU: Rezervace 15 2. května 2023 Reformulace na problém barvení grafu Problém s nelimitovaným počtem identických strojů lze reformulovat na problém barvení grafu vrchol = úloha hrana (j, 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 Hana Rudová, FI MU: Rezervace 16 2. května 2023 Příklad: reformulace j 1 2 3 4 5 6 7 8 rj 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: 6 5 4 3 2 1 8 7 Hana Rudová, FI MU: Rezervace 17 2. května 2023 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á, FI MU: Rezervace 18 2. května 2023 Předzpracování ψit: počet úloh, které mohou být přiřazeny na stroj i během intervalu [t − 1, t] možné využití stroje i v čase t čím vyšší hodnota, tím je zdroj i 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á, FI MU: Rezervace 19 2. května 2023 Prioritní indexy Prioritní index pro úlohu j: Ij = f (wj /pj , |Mj |) uspořádání úloh podle: I1 ≤ I2 ≤ · · · ≤ In čím menší je |Mj |, tím nižší je Ij čím vyšší je wj /pj , tím nižší je Ij 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ř. Ij = |Mj | wj /pj Prioritní index pro stroj vybírá stroj pro úlohu jestliže úloha potřebuje stroj v [t, t + pj ] pak výběr stroje i záleží na funkci s faktory ψi,t+1, . . . , ψi,t+pj , tj. na g(ψi,t+1, . . . , ψi,t+pj ) např. g(ψi,t+1, . . . , ψi,t+pj ) = pj l=1 ψi,t+l /pj nebo g(ψi,t+1, . . . , ψi,t+pj ) = max(ψi,t+1, . . . , ψi,t+pj ) Hana Rudová, FI MU: Rezervace 20 2. května 2023 Algoritmus maximalizace váženého počtu aktivit 1 j = 1 2 Vyber úlohu j s nejnižším Ij a vyber mezi stroji a dostupnými časy zdroj a čas s nejnižší g(ψi,t+1, . . . , ψi,t+pj ) Zruš úlohu j jestliže nemůže být přiřazena ani jednomu stroji v žádném čase 3 Jestliže j = n STOP jinak nastav j = j + 1 a běž na krok 2 Hana Rudová, FI MU: Rezervace 21 2. května 2023 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 rj 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} pro Ij = |Mj | wj /pj a g(ψi,t+1, . . . , ψi,t+pj ) = pj l=1 ψi,t+l /pj Řešení: Úlohy 7 6 1 4 5 2 Stroje 2 1 3 3 1 2 Časy 11-14 14-19 5-8 11-15 2-8 0-10 úlohu 3 nelze umístit Hana Rudová, FI MU: Rezervace 22 2. května 2023 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) nelimitovaný počet identických strojů Rezervační systém s rezervou kompozitní řídící pravidlo Hana Rudová, FI MU: Rezervace 23 2. května 2023 Rozvrhování jako timetabling 2. května 2023 4 Úvod 5 Rozvrhování s operátory 6 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 Omezení operátorů/nástrojů (operator/tool) mnoho operátorů ú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á, FI MU: Rozvrhování jako timetabling 25 2. května 2023 Rozvrhování jako problém plánování projektu s omezenými zdroji Problém plánování projektu s omezenými zdroji resource-constrained project scheduling problem (RCPSP) n úloh N zdrojů Ri kapacita zdroje i pj doba provádění úlohy j Rij požadavek úlohy j na zdroj i Precj (přímí) předchůdci úlohy j Rozvrhování s operátory Ri = 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á, FI MU: Rozvrhování jako timetabling 26 2. května 2023 Rozvrhování s operátory jako barvení grafu Omezíme se na problém s jednotkovou dobou trvání Úloha = uzel Úlohy potřebují stejného operátora = hrana mezi uzly 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 Problém existence řešení 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 jaký nejmenší počet barev je třeba? chromatické číslo grafu Hana Rudová, FI MU: Rozvrhování jako timetabling 27 2. května 2023 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 1 uspořádej uzly v klesajícím pořadí podle jejich stupně 2 použij barvu 1 pro první uzel 3 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 4 obarvi vybraný uzel s nejmenší možnou barvou 5 jestliže jsou všechny uzly obarveny STOP jinak běž na krok 3 Hana Rudová, FI MU: Rozvrhování jako timetabling 28 2. května 2023 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 1 1 0 1 1 Lisa 1 1 1 0 0 Jane 1 0 1 0 0 Larry 0 1 0 1 1 2 1 5 3 4 stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Můžeme vybrat buď úlohu 1 nebo úlohu 2 Např. vybereme 1 a obarvíme barvou 1 Hana Rudová, FI MU: Rozvrhování jako timetabling 29 2. května 2023 Příklad: rozvrhování schůzek (dokončení) 5 1 3 2 4 Úroveň saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 V posledním kroku obarvi 3 stejnou barvou jako 4 ⇒celkem 4 barvy, tj. makespan=4 stupen=4 stupen=3 stupen=4 stupen=2 stupen=3 5 1 3 2 4 Hana Rudová, FI MU: Rozvrhování jako timetabling 30 2. května 2023 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 1 2 3 Operátor 1 1 0 0 Operátor 2 1 0 0 Operátor 3 0 1 0 Operátor 4 0 1 1 Operátor 5 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á, FI MU: Rozvrhování jako timetabling 31 2. května 2023 Vztah k rezervačním systémům Rozvrhování s operátory blízké rezervačnímu systému bez rezervy 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á, FI MU: Rozvrhování jako timetabling 32 2. května 2023 Rozvrhování s pracovní sílou: aplikace Řízení projektu ve stavebním průmyslu dodavatel má realizovat n aktivit doba trvání aktivity j je pj aktivita j požaduje pracovní skupinu velikosti Wj 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 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 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á, FI MU: Rozvrhování jako timetabling 33 2. května 2023 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 ) 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) ≤ 17 10 Cmax (OPT) + 2 Hana Rudová, FI MU: Rozvrhování jako timetabling 34 2. května 2023 Příklad: heuristika prvního padnoucího koše (FF) Předpokládejme 18 úloh a W =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 (301×6=1806) pak přiřadíme vždy dvě úlohy na další tři zdroje (701×2=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á, FI MU: Rozvrhování jako timetabling 35 2. května 2023 Heuristika prvního padnoucí koše se zmenšováním úloh Zlepšení FF heuristiky Uspořádání úloh od nejdelší k nejkratší 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) ≤ 11 9 Cmax (OPT) + 4 FF i FFD mohou být rozšířeny o různé termíny dostupnosti Hana Rudová, FI MU: Rozvrhování jako timetabling 36 2. května 2023 Diskuse Uvažovali jsme reprezentanty různých problémů 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á, FI MU: Rozvrhování jako timetabling 37 2. května 2023 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 plánování projektu s omezenými zdroji (RCPSP) rozvrhování s operátory a barvení grafu heuristika pro barvení grafu 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á, FI MU: Rozvrhování jako timetabling 38 2. května 2023