Ohodnocené grafy
ooooo
Barvení grafu
oooooooooooc
PB165 Grafy a sítě:
6. Grafová reprezentace
PB165 Grafy a sítě: 6. Grafová reprezentace 1/22
Ohodnocené grafy
ooooo
Barvení grafu
oooooooooooc
Shrnutí
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
o plánování jako barvení grafu
PB165 Grafy a sítě: 6. Grafová reprezentace 2/22
Ohodnocené grafy
ooooo
Obsah prednášky
(l) Ohodnocené grafy
* Problém obchodního cestujícího
* Doba na dopravu
 Plánování na počítačové síti
0 Barvení grafu
* Popis problému a jednoduché řešení
* Přiřazení místností
o Rezervační problém
* Rozvrhování operátorů
PB165 Grafy a sítě: 6. Grafová reprezentace
Barvení grafu
oooooooooooc
3/22
Ohodnocené grafy Barvení grafu
ˇoooo oooooooooooc
Problém obchodního cestujícího
Problém obchodního cestujícího
* Doba na nastavení (setup time) sy
* Skj č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
o 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
o Problém obchodního cestujícího = l\sjk\Cmax
PB165 Grafy a sítě: 6. Grafová reprezentace 4/22
Ohodnocené grafy Barvení grafu
oooo oooooooooooc
Doba na dopravu
Doba na dopravu
* Multi-operační rozvrhování
* úloha
* skládá z několika operací
 může/nemusí být určeno jejich pořadí1
* operace má zadáno
dobu provádění, konkrétní stroj k provádění
* stroj: na každém stroji maximálně jedna operace
* doba na dopravu (transportation time) í/,/ mezi stroji h a /
* kapacita cest mezi stroji neomezená
* cíl: realizovat všechny operace všech úloh
při minimalizaci času dokončení všech úloh
Grafová reprezentace
o orientovaný hranově ohodnocený graf
a 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 5/22
Ohodnocené grafy
oooo
Plánování na počítačové síti
Plánování na počítačové síti
* Stroj: počet procesorů
* Úlohy prováděny na jednom uzlu počítačové sítě
 vyžadují několik procesorů
* Ú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
o 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 6/22
Ohodnocené grafy
oooo
Plánování na počítačové síti
Barvení grafu
oooooooooooc
Počítačová síť: grafová reprezentace
o 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 7/22
Ohodnocené grafy
oooo
Barvení grafu
oooooooooooc
Plánování na počítačové síti
Plánování úlohy na počítačové síti: príklad
* Úloha naplánována
k provádění na uzlu 1
o Data na uzlech 2 a 3
o Data jsou přenesena přes D,C a A,B
o Kapacita linky/zdrojů A,B,C,D musí mít v
daném čase postačující propustnost
o 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
ooooo
Popis problému a jednoduché řešení
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
a 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
ˇooooooooooc
Barvení grafu a rozvrhování
Rezervační problémy
* Přiřazení místností
* Rozvrhování operátorů
9/22
Ohodnocené grafy Barvení grafu
ooooo ooooooooooc
Popis problému a jednoduché řešení
Heuristiky pro barvení grafu se saturací
* Stupeň uzlu
* počet hran spojených s uzlem
* Úroveň saturace
* počet různých barev spojených s uzlem
o Intuice
* obarvi uzly s vyšším stupněm dříve
o obarvi uzly s vyšší úrovní saturace dříve
Algoritmus
 uspořádej uzly v klesajícím pořadí podle jejich stupně
9 použij barvu 1 pro první uzel
Q 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
@ obarvi vybraný uzel s nejmenší možnou barvou
(D jestliže jsou všechny uzly obarveny STOP
jinak běž na krok 3
PB165 Grafy a sítě: 6. Grafová reprezentace 10/22
Ohodnocené grafy
ooooo
Přiřazení místností
Přiřazení místností
* Problém přiřazení místností
o ú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)
Barveni grafu
ooooooooooc
PB165 Grafy a sítě: 6. Grafová reprezentace 11/22
Ohodnocené grafy
ooooo
Přiřazení místností
Prirazení místností: príklad
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 12/22
Ohodnocené grafy
ooooo
Přirazení místností
Přiřazení místností:
PB165 Grafy a sítě: 6. Grafová reprezentace
Barvení grafu
ooooooooooc
príklad (pokračování)
předmět A B C D E
saturace - 1 1 0 0
stupeň neob. - 1 1 2 2
předmět A B C D E
saturace - - 1 1 0
stupeň neob. - - 1 1 2
13/22
Ohodnocené grafy
ooooo
Přiřazení místností
Přiřazení místností:
PB165 Grafy a sítě: 6. Grafová reprezentace
Barvení grafu
ooooooooooc
príklad (dokončení)
předmět A B C D E
saturace - - - 1 1
stupeň neob. - - - 1 1
14/22
Ohodnocené grafy
ooooo
Přiřazení místností
Prirazení místností: príklad (resení)
předmět A B C D E
časy (1,4) (1,3) (2,4) (3,5) (2,5)
místnost červená červená šedá
Barvení grafu
ooooooooooc
B čas/předmět A B C D E
1 + . . .
2 - - - +
3 - - + 4
+ - - 5
- - - + +
PB165 Grafy a sítě: 6. Grafová reprezentace 15/22
Ohodnocené grafy
ooooo
Barvení grafu
ooooooooooc
Rezervační problém
Rezervační problém
9 Příklady
o rezervace aut
* rezervace pokojů v hotelu
 rezervace strojů v továrně
o Určen časový interval pro každou rezervaci
* Pj = rj - d j
* pj doba trvání úlohy
o 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
ooooo
Barvení grafu
ooooooooooc
Rezervační problém
Rezervační problém jako barvení grafu
* Graf
a vrchol: rezervace
* hrana: pokud se dvě rezervace překrývají v čase
Barva vrcholu: koresponduje vybranému zdroji
a kolik zdrojů je třeba ke splnění rezervací
= chromatické číslo
a lze rezervace realizovat s daným počtem zdrojů
= existuje barvení s daným počtem barev
o Příklad:
j 1 2 3 4 5 6 7 8
dj
0 1 1 3 4 5 6 6
5 3 4 7 6 7 9 8
Odpovídající problém barvení grafu:
PB165 Grafy a sítě: 6. Grafová reprezentace 17/22
Ohodnocené grafy Barvení grafu
ooooo ooooooooooc
Rozvrhování operátorů
Rozvrhování operátorů
* 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ň
o 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
ooooo
Rozvrhování operátorů
Příklad: plánování schůzek
Vytvoř rozvrh pro 5 schůzek se 4 lidmi
a 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
stupen=4,
1
stupen=3)
s,stupen=4
stupen=2
stupen=3
PB165 Grafy a sítě: 6. Grafová reprezentace
Barvení grafu
ooooooooooc
Můžeme vybrat buď
úlohu 1 nebo úlohu 2
Např. vybereme 1 a obarvíme
barvou 1
19/22
Ohodnocené grafy
ooooo
Barvení grafu
ooooooooooo
Rozvrhování operátorů
Príklad: plánování schůzek (dokončení)
Úroveň saturace = 1 pro všechny úlohy
Vyber 2 vzhledem k nejvyššímu stupni
Üroven 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=
20/22
Ohodnocené grafy Barvení grafu
ooooo oooooooooooc
Rozvrhování operátorů
Cvičení
Jakou grafovou reprezentaci mají následující problémy? Problémy vyřešte
a ukažte postup řešení.
Q) 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í
9 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
Ohodnocené grafy Barvení grafu
ooooo oooooooooooc
Rozvrhování operátorů
Cvičení (pokračování)
9 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 1 2 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