Ohodnocené grafy Barveni grafu OOOOOOOOOOOC PB165 Grafy a sítě: 6. Grafová reprezentace PB165 Grafy a sítě: 6. Grafová reprezentace 1/22 Minule • Rozvrhování: optimální přiřazení zdrojů v čase množině úloh • Grafová reprezentace: orientované vrcholově ohodnocené grafy • precedenční podmínky • multi-operační rozvrhování a disjunktivní grafová reprezentace Dnes • orientované vrcholově/hranově ohodnocené grafy • plánování jako barvení grafu PB165 Grafy a sítě: 6. Grafová reprezentace 2/22 Ohodnocené grafy Obsah přv Q Ohodnocené grafy • Problém obchodního cestujícího • Doba na dopravu • Plánování na počítačové síti Q Barvení grafu • Popis problému a jednoduché řešení • Přiřazení místností • Rezervační problém • Rozvrhování operátorů PB165 Grafy a sítě: 6. Grafová reprezentace Barveni grafu OOOOOOOOOOOC 3/22 Ohodnocené grafy • OOOO Problém obchodního cestujícího Problém obchodník Barveni grafu OOOOOOOOOOOO • Doba na nastavení (setup time) s/y • s/y čas nutný pro provádění úlohy k po úloze y • problém l\sjk\Cmax • Problém obchodního cestujícího • obchodní cestující musí projet všechna města tak, aby celková ujetá vzdálenost (resp. doba cesty) byla minimální a každé město projel právě jednou a Grafová reprezentace • (orientovaný) hranově ohodnocený graf • vrchol = město • (orientovaná) hrana z A do B = přímá cesta z A do B • hrany mohou být orientované, pokud chceme uvažovat různou náročnost v opačných směrech cesty • ohodnocení hrany z A do B = doba nutná na cestu z A do B • Problém obchodního cestujícího = llsy/JCmax PB165 Grafy a sítě: 6. Grafová reprezentace 4/22 • kapacita cest mezi stroji neomezená • cíl: realizovat všechny operace všech úloh při minimalizaci času dokončení všech úloh o Grafová reprezentace • orientovaný hranově ohodnocený graf • vrchol: stroj • hrana: pokud lze přejít přímo z jednoho stroje na druhý • ohodnocení hrany: doba na dopravu z jednoho stroje na druhý PB165 Grafy a sítě: 6. Grafová reprezentace • Stroj: počet procesoru • Úlohy prováděny na jednom uzlu počítačové sítě • vyžadují několik procesoru • Úlohy potřebují k výpočtu data • data dané velikosti na jednom nebo více uzlech • data je nutné přenést na uzel, kde se úloha bude počítat • realita: data jsou často zreplikována na několika uzlech • Linka: • propustnost = kapacita linky • latence = doba nutná na přenos dat po lince • Cíl: realizovat všechny úlohy • úlohy musí mít dostatek procesorů • data musí ležet v době výpočtu na uzlu, kde se počítá úloha • je nutné plánovat i přenosy dat tak, aby bylo možné data přenést vzhledem k latenci i propustnosti linek na cestě PB165 Grafy a sítě: 6. Grafová reprezentace Ohodnocené grafy Počítačová síť: tmmaaá • Vrcholově ohodnocený neorientovaný graf • Vrchol: stroj nebo linka • Ohodnocení vrcholu-stroje: počet procesorů • Ohodnocení vrcholu-linky: propustnost linky • linka je chápána jako zdroj, jehož kapacita odpovídá propustnosti • doba trvání úlohy na lince odpovídá latenci • Hrany: pokud jsou stroje A a B přímo spojeny linkou C, pak existují hrany AC a BC PB165 Grafy a sítě: 6. Grafová reprezentace Ohodnocené grafy Barveni grafu OOOOOOOOOOOO Plánování úlohy • Úloha naplánována k provádění na uzlu 1 • Data na uzlech 2 a 3 • Data jsou přenesena přes D,C a A,B • Kapacita linky/zdrojů A,B,C,D musí mít v daném čase postačující propustnost • Celková doba přenostu do 1: max(latenceA+latenceB, latenceD+latenceC) Základní otázka: je možné nyní takovouto úlohu naplánovat? A je možné ji naplánovat při modifikaci cest pro přenosy? PB165 Grafy a sítě: 6. Grafová reprezentace 8/22 Ohodnocené grafy Popis problému a jednoduché 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 PB165 Grafy a sítě: 6. Grafová reprezentace Barvení grafu a rozvrhování • Rezervační problémy • Přiřazení místností • Rozvrhování operátorů 9/22 Ohodnocené grafy OOOOO Barveni grafu o«oooooooooo BQ Heuristiky pro barver • 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 0 jestliže jsou všechny uzly obarveny STOP jinak běž na krok 3 PB165 Grafy a sítě: 6. Grafová reprezentace 10/22 • Problém přiřazení místností • úloha = předmět s několika schůzkami týdně, zdroj = místnost • dva předměty nesmí být zároveň vyučovány ve stejné místnosti • všechny schůzky předmětu musí být vyučovány ve stejné místnosti rozvrh: přiřazení místnosti každému předmětu možné řešení: • nalezení rozvrhu s minimálním počtem místností • nalezení rozvrhu vzhledem k danému počtu místností • Přiřazení místností jako barvení grafu • vrchol: předmět • barva vrcholu: odpovídá vybrané místnosti • hrana: mezi předměty vyžadujícími stejný čas výuky (musí mít různé místnosti a také různé barvy) PB165 Grafy a sítě: 6. Grafová reprezentace 11/22 Ohodnocené grafy OOOOO Přiřazení aaKUUifii Kolik místností je třeba k rozvrhování těchto předmětů? předmět A B C D E časy (1,4) (1,3) (2,4) (3,5) (2,5) stupeň 2 2 2 2 2 PB165 Grafy a sítě: 6. Grafová reprezentace Ohodnocené grafy OOOOO Barveni grafu oooo«ooooooc Přiřazení mmsMmmäímm předmět saturace stupeň neob. předmět saturace stupeň neob. B C D E 110 0 112 2 B C D E - 1 1 0 - 1 1 2 PB165 Grafy a sítě: 6. Grafová reprezentace 13/22 Ohodnocené grafy OOOOO Barveni grafu ooooo«oooooc Přiřazení mmiMSímmm předmět 4 * ' saturace stupeň neob. ABC D E 1 1 1 1 PB165 Grafy a sítě: 6. Grafová reprezentace 14/22 předmět A B C D E časy (1,4) (1,3) (2,4) (3,5) (2,5) červená šedá místnost červená čas/předmět A B C D E 1 + ... 2 - - - + 3 - - + - 4 + - - - 5 - - - + + PB165 Grafy a sítě: 6. Grafová reprezentace 15/22 • Příklady • rezervace aut • rezervace pokojů v hotelu • rezervace strojů v továrně a Určen časový interval pro každou rezervaci • p j = r j - d j • pj doba trvání úlohy • rj termín dostupnosti • dj termín dokončení • Každá rezervace vyžaduje zdroj (auto, pokoj, stroj) • Možné řešení • kolik zdrojů je třeba ke splnění rezervací • lze rezervace realizovat s daným počtem zdrojů PB165 Grafy a sítě: 6. Grafová reprezentace 16/22 Ohodnocené grafy Graf • vrchol: rezervace • hrana: pokud se dvě rezervace překrývají v čase Barva vrcholu: koresponduje vybranému zdroji • kolik zdrojů je třeba ke splnění rezervací = chromatické číslo • lze rezervace realizovat s daným počtem zdrojů = existuje barvení s daným počtem barev • Příklad: •j dj 2 3 4 5 6 7 Odpovídající problém barvení grafu: Barveni grafu OOOOOOOOÄOOO Rezervační problém Rezervační prol 3lém jako barvení grafu PB165 Grafy a sítě: 6. Grafová reprezentace 17/22 • Zadáno několik různých operátorů » Úloha potřebuje jeden nebo více specifických operátorů • Úlohy vyžadující stejného operátora nemohou běžet zároveň • Jednotková doba trvání úlohy • Možné řešení: • rozvržení všech úloh v rámci časového horizontu • nalezení minimálního času (=makespan) tak, aby byly provedeny všechny úlohy • Rozvrhování operátorů jako barvení grafu • vrchol: úloha • hrana: mezi úlohami, které potřebují stejného operátora » barva vrcholu: čas pro realizaci úlohy • rozvržení všech úloh v rámci časového horizontu = existuje barvení s daným počtem barev • makespan = chromatické číslo grafu PB165 Grafy a sítě: 6. Grafová reprezentace 18/22 Ohodnocené grafy Příklad: pláru 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 st u pen =4y ill /T\stupen=4 'S-ť^v stupen=2 / \ (3) stupen=3/ stupen=3 PB165 Grafy a sítě: 6. Grafová reprezentace Můžeme vybrat buď úlohu 1 nebo úlohu 2 Např. vybereme 1 a obarvíme barvou 1 19/22 Ú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 PB165 Grafy a sítě: 6. Grafová reprezentace Ú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=A 20/22 Jakou grafovou reprezentaci mají následující problémy? Problémy vyřešte a ukažte postup řešení. O Určete, ve kterých místnostech se mají konat schůzky tak, aby byla v každé místnosti nejvýše jedna schůzka a přitom byly schůzky organizovány v uvedených termínech. předmět A B C D E časy (1,3,5) (2,4) (1,2) (3,4) (1,5) Nápověda: problém přiřazení místností Q Stroje v továrně mají být využívány uvedenými operacemi v následujících časových intervalech. Určete, kolik strojů je třeba a které stroje budou využívat jednotlivé operace v případě, že stroj může zpracovávat nejvýše jednu operaci, operace A B C D E F interval 1-3 2-4 1-4 4-5 5-8 5-6 Nápověda: rezervační problém PB165 Grafy a sítě: 6. Grafová reprezentace 21/22 O Určete, kolik času je potřeba pro realizaci operací na uvedených strojích, jestliže může být na každém stroji zpracovávána nejvýše jedna operace, operace 12 3 4 5 6 7 stroje A,B C,D A,C,E E,F E,G D,G G Nápověda: rozvrhování operátoru PB165 Grafy a sítě: 6. Grafová reprezentace 22/22