PB165 Grafy a sítě:
Plánování projektu, plánování pomocí barvení grafu
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 1/68
Obsah
1 Plánování projektu
Neomezené zdroje
Variabilní doba trvání
2 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ě: Plánování projektu, plánování pomocí barvení grafu 2/68
Plánování projektu
Základní problém plánování projektu
precedenční podmínky
paralelní stroj s neomezeným počtem strojů
minimalizace maximálního času konce úloh (makespan)
relativně jednoduché na řešení: metoda kritické (nejdelší) cesty
princip: nalezneme kritickou cestu a ta určuje makespan
21 4 6
3 5 7
1
12 3 4
2 3
Rozšíření: variabilní doba trvání
doba trvání úlohy spojena s cenou provádění
optimalizace: kompromis mezi cenou na ukončení projektu a cenou za
zkrácení délky úloh
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 3/68
Popis problému
Popis problému
paralelních stroj
n úloh s precedenčními omezeními
doba provádění pj
objektivní funkce: minimalizace maximálního času konce úloh
(makespan)
Základní problém s neomezenými zdroji
P∞|prec|Cmax m ≥ n metoda kritické cesty
Plánování projektu s omezenými zdroji
Pm|prec|Cmax 2 ≤ m < n NP úplný problém
Značení
Sj nejdřívější startovní čas úlohy j
Cj = Sj + pj nejdřívější koncový úlohy j
Sj nejpozdější startovní čas úlohy j
Cj nejpozdější koncový čas úlohy j
Precj (přímí) předchůdci úlohy j
∀k ∈ Precj všechny úlohy k, které předcházejí úlohu j
∀j : k ∈ Precj všechny úlohy j, které následují úlohu k
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 4/68
Metoda kritické cesty (critical path method CPM)
Popis algoritmu pro nalezení kritických cest
dopředná procedura
start v čase 0
výpočet nejdřívějšího startovního času každé úlohy
čas dokončení poslední úlohy je makespan
zpětná procedura
start v čase rovném makespan
výpočet nejpozdějšího startovního času, aby byl realizován tento
makespan
Úloha s rezervou (slack job)
její startovní čas může být odložen aniž je navýšen makespan
úloha j, jejichž nejdřívější startovní čas Sj je menší než nejpozdější startovní čas Sj
rezerva úlohy j: Sj − Sj
Kritická úloha
úloha, která nesmí být odložena
úloha, jejíž nejdřívější startovní čas je roven nejpozdějšímu start. času
Kritická cesta
řetěz úloh začínající v čase 0 a končící v čase Cmax
v grafu může existovat více kritických cest
kritické cesty se mohou částečně překrývat
graf kritických cest GCP : podgraf daný množinou kritických úloh a kritických cest
Cvičení: Jaký je rozdíl mezi kritickou cestou a grafem kritických cest? Ukažte rozdíl na příkladu.
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 5/68
Kritická cesta: zadání příkladu
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
2 7
10
12 14
4
1
3
6 9
5 8
1311
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 6/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 7/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 8/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 9/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
11+12=23
14+12=26
14+7=21
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 10/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
11+12=23
14+12=26
14+7=21
26+6=32
23+10=33
26+10=36
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 11/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
11+12=23
14+12=26
14+7=21
26+6=32
23+10=33
26+10=36
36+7=43
33+9=42
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 12/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
11+12=23
14+12=26
14+7=21
26+6=32
23+10=33
26+10=36
36+7=43
33+9=42
43+8=51
43+7=50
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 13/68
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
11+12=23
14+12=26
14+7=21
26+6=32
23+10=33
26+10=36
36+7=43
33+9=42
43+8=51
43+7=50
51+5=56
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 14/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 15/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=51
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 16/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 17/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
43−9=34
43−7=36
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 18/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
43−9=34
43−7=36
34−10=24
36−6=30
36−10=26
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 19/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
43−9=34
43−7=36
34−10=24
36−6=30
36−10=26
24−12=12
26−7=19
26−12=14
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 20/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
43−9=34
43−7=36
34−10=24
36−6=30
36−10=26
24−12=12
26−7=19
26−12=14
14−9=5
12−6=6
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 21/68
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
43−9=34
43−7=36
34−10=24
36−6=30
36−10=26
24−12=12
26−7=19
26−12=14
14−9=5
12−6=6
5−5=0
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 22/68
Výsledky dopředné a zpětné procedury
51+5=56
43+8=51
43+7=50
36+7=43
33+9=42
26+6=32
23+10=33
26+10=36
11+12=23
14+12=26
14+7=21
5+6=11
5+9=14
0+5=5
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
5−5=0
14−9=5
12−6=6 24−12=12
26−7=19
26−12=14
34−10=24
36−6=30
36−10=26
43−9=34
43−7=36
51−8=43
51−7=44
56−5=51
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 23/68
Porovnání S’j a S”j
5 11
14
26
23
33
S’j
2 7
10
14
4
1
3
6 9
5 8
1311
120
5
5114
26
36
43
43
6 12 24
30
j
S’’
19
34
2 7
10
14
4
1
3
6
5 8
1311
12
9
0
5
14 26
36
43 51
44
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 24/68
Kritická cesta
2 7
10
12 14
4
1
3
6 9
5 8
1311
maxC = 56
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 25/68
Graf kritických cest GCP
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pj 5 6 9 12 7 12 10 6 10 9 7 8 8 5
2 7
10
12 14
4
1
3
6 9
5 8
1311
maxC = 56
GCP: dvě kritické cesty {1,3,6,9,11,12,14}, {1,3,6,9,11,13,14},
které se částečně překrývají
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 26/68
Metoda kritické cesty
1 Dopředná procedura
1 t = 0
2 pro všechny úlohy j bez předchůdce: Sj = 0, Cj = pj
3 vypočítej postupně pro všechny zbývající úlohy j:
k1
jk2
k3
Sj = max
∀k∈Precj
Ck , Cj = Sj + pj
4 optimální makespan je Cmax = max(C1, . . . , Cn)
2 Zpětná procedura
t = Cmax
pro všechny úlohy j bez následníka: Cj = Cmax , Sj = Cmax − pj
vypočítej postupně pro všechny zbývající úlohy j:
k3
j
k1
k2
Cj = min
∀k:j∈Preck
Sk , Sj = Cj − pj
ověř, že 0 = min(S1 , . . . , Sn )
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 27/68
Cvičení
1 Jaká je grafová reprezentace rozvrhovacího problému zadaného
tabulkou: úloha doba trvání předchůdci
1 1 -
2 2 1
3 3 1
4 4 2,5,6
5 5 1,2
6 2 3
7 4 -
8 1 7,9
9 5 4
10 2 8
2 Nalezeněte graf kritických cest v tomto grafu.
3 Jaký má tento rozvrh makespan?
4 Existují v problému úlohy s rezervou? Pokud ano, uveďte o které úlohy
se jedná. Jakou mají tyto úlohy rezervu?
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 28/68
Kompromis mezi časem a cenou
Lze uvažovat variabilní dobu trvání úloh
za předpokladu vyšší ceny lze zkrátit dobu provádění
Lineární cena
Doba trvání pmin
j ≤ pj ≤ pmax
j
Marginální cena: cena za zkrácení doby trvání úlohy
o 1 časovou jednotku
cj =
ca
j − cb
j
pmax
j − pmin
j
cj
a
cj
b
pj
min pj
max
doba provádění
prostředky (peníze)
⇒ cena provádění úlohy j po dobu pj : cb
j + cj (pmax
j − pj )
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 29/68
Cena za provádění projektu
Fixní režijní náklady c0 celkem: Cmaxc0
na časovou jednotku doby provádění projektu
Cena F(pj ) za provádění projektu
při době provádění úloh pj
určena jako součet
ceny za provádění všech úloh
fixních režijních nákladů
F(pj ) = Cmaxc0 +
j
cb
j + cj (pmax
j − pj )
Cíl: ∀j nalézt pj a Sj tak, aby byla F(pj ) minimální
cj
a
cj
b
pj
min pj
max
doba provádění
prostředky (peníze)
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 30/68
Variabilní doba trvání: metody řešení
Objektivní funkce: minimální cena projektu
Kompromisní heuristika mezi časem a cenou
dobrá kvalita rozvrhu
použitené i pro nelineární cenu
Další přístupy: formulace lineárního programování
systém lineárních nerovnic s lineárním optimalizačním kritériem
simplexová metoda
optimální rozvrh
nelineární verze obtížně řešitelné
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 31/68
Řez, minimální řez
Orientovaný graf G = (V , E)
Počáteční uzel: zdroj s ∈ V
Koncový uzel: stok t ∈ V
Řez ze zdroje s do stoku t: ... také mluvíme o vrcholovém řezu
množina uzlů V , jejíž smazáním z grafu se rozpojí zdroj a stok
E množina hran incidentních s V
tj. v G’=(V-V’,E-E’) neexistuje orientovaná cesta z s to t
Minimální řez z s do t: řez U takový, že neexistuje řez W ⊂ U
tj. vrácení libovolného uzlu z U do grafu znovu spojí zdroj a stok
řez
zdroj stok
minimální řez
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 32/68
Řez, minimální řez II.
Uvažujme orientovaný graf G0 = (V0, E0)
Do grafu přidáme zdroj:
nový vrchol s a
hrany S vedoucí z s do všech vrcholů G0 bez předchůdců
Do grafu přidáme stok:
nový vrchol t a
hrany T vedoucí ze všech vrcholů G0 bez následníků do t
Nový graf G = (V , E): V = V0 ∪ {s, t}, E = E0 ∪ S ∪ T
Budeme hledat řezy a minimální řezy z s do t v G
řez
zdroj stok
minimální řez
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 33/68
Řez, minimální řez II.
Uvažujme orientovaný graf G0 = (V0, E0)
Do grafu přidáme zdroj:
nový vrchol s a
hrany S vedoucí z s do všech vrcholů G0 bez předchůdců
Do grafu přidáme stok:
nový vrchol t a
hrany T vedoucí ze všech vrcholů G0 bez následníků do t
Nový graf G = (V , E): V = V0 ∪ {s, t}, E = E0 ∪ S ∪ T
Budeme hledat řezy a minimální řezy z s do t v G
řez
zdroj stok
minimální řez
př. graf má 4 minimální řezy
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 34/68
Cvičení: minimální řez
Kolik minimálních řezů a které mají následující grafy?
1
2
3 4
5
6
5
7
8
1
2
3 4
6
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 35/68
Kompromisní heuristika: příklad
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pmax
j 5 6 9 12 7 12 10 6 10 9 7 8 7 5
pmin
j 3 5 7 9 5 9 8 3 7 5 4 5 5 2
cb
j 20 25 20 15 30 40 35 25 30 20 25 35 20 10
cj 7 2 4 3 4 3 4 4 4 5 2 2 4 8
fixní režijní náklady na časovou jednotku c0=6
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 36/68
Algoritmus kompromisní heuristiky
1 Nastav doby provádění na jejich maximum: pj = pmax
j
Urči všechny kritické cesty s těmito dobami provádění
Zkonstruuj graf GCP kritických cest
2 Urči všechny minimální řezy v GCP
Najdi řezy, jejichž doba provádění je větší než jejich minimum:
pj > pmin
j ∀j ∈ GCP
Pokud takový řez neexistuje STOP, jinak běž na krok 3
3 Pro každý minimální řez: spočítej cenu redukující všechny doby
provádění o 1 časovou jednotku
Vyber minimální řez s nejnižší cenou
Jestliže je menší než fixní režijní náklady c0 za časovou jednotku běž na
krok 4, jinak STOP
4 Redukuj všechny doby provádění v minimálním řezu o 1 časovou
jednotku
Urči novou množinu kritických cest
Reviduj graf GCP a běž na krok 2
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 37/68
Příklad (pokračování): maximální doba provádění
2 7
10
12 14
4
1
3
6 9
5 8
1311
maxC = 56
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 38/68
Kompromisní heuristika: příklad
c0=6
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pmax
j 5 6 9 12 7 12 10 6 10 9 7 8 7 5
pmin
j 3 5 7 9 5 9 8 3 7 5 4 5 5 2
cb
j 20 25 20 15 30 40 35 25 30 20 25 35 20 10
cj 7 2 4 3 4 3 4 4 4 5 2 2 4 8
Náklady na provedení projektu při maximální době trvání úloh
F(pmax
j ) = Cmaxc0 + j cb
j + cj (pmax
j − pmax
j ) =
= Cmaxc0 + j cb
j =
= 56 × 6 + 20 + 25 + 20 + 15 + 30 + 40 + 35 + 25+
+30 + 20 + 25 + 35 + 20 + 10 =
= 336 + 350 = 686
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 39/68
Graf kritických cest GCP
Kandidáti na redukci: uzel 11 a uzel 12, vybereme uzel 12
12 141
3
6 9
11
c = 36 c = 49
c = 212 c = 814c = 71
c = 43
Rezy: {1},{3},{6},{9}
{11},{12},{14}
c = 211
minimální řez
s nejnižší cenou
³
ulohy 12 z 8 na 7
redukce doby provádení
Fixní režijní náklady se redukují z 56 × 6 na 55 × 6 = 330
Cena za provádění úloh naroste o c12 = 2, tj. 350 + 2 = 352
Celková cena klesla z 686 na 330 + 352 = 682
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 40/68
Graf kritických cest GCP
12 141
3
6 9
1311
c = 36 c = 49
c = 413
c = 212 c = 814c = 71
c = 211c = 43
Rezy: {1},{3},{6},{9}
{11},{12,13},{14}
minimální řez
s nejnižší cenou
¬
5
9 12 10
7 7
77 na 6
redukce doby trvání ulohy 11 ze 7 na 6
Fixní režijní náklady se redukují z 55 × 6 na 54 × 6 = 324
Cena za provádění úloh naroste o c11 = 2, tj. 352 + 2 = 354
Celková cena klesla z 682 na 324 + 354 = 678
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 41/68
Graf kritických cest GCP
12 141
3
6 9
1311
C = 36 C = 49
C = 413
C = 212 C = 814
C = 211C = 43
2 7
10
12 141
3
6 9
1311
C = 71
C = 22 C = 47C = 34
C = 510
4
5−2
10−7
5−3
6−5
12−9 10−8
9−5
7−5
12−9
9−7
8−5
další redukce: pro uzel 2 na 5 a pro uzel 11 na 5, ...
7−4
Fixní režijní náklady se redukují z 54 × 6 na 53 × 6 = 318
Cena za provádění úloh naroste o c2 + c11 = 2 + 2, tj. 354 + 4 = 358
Celková cena klesla z 678 na 318 + 358 = 676
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 42/68
Kompromisní heuristika: cvičení
Jaká je cena za provádění projektu, pokud jsou doby trvání úloh maximální, tj.
čemu se rovná F(pmax
j ) za následujících předpokladú?
fixní režijní náklady na časovou jednotku jsou c0 = 4
pmax
j maximální doba trvání úlohy j
pmin
j minimální doba trvání úlohy j
cj marginální cena
cb
j cena za provádění úlohy j při maximální době jejího trvání
Precj předchůdci úlohy j
j 1 2 3 4 5 6 7 8
pmax
j 4 4 4 4 4 4 3 6
pmin
j 3 2 2 2 2 2 2 6
cb
j 20 25 20 15 30 40 35 25
cj 3 5 5 1 2 5 3 5
j 1 2 3 4 5 6 7 8
Precj - 2 4,5 2 2 3,7 5 6
Jak lze cenu za projekt zlepšit, pokud provedeme dva kroky kompromisní
heuristiky? Kterým úlohám upravíte dobu trvání v jednotlivých krocích?
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 43/68
Obsah
1 Plánování projektu
Neomezené zdroje
Variabilní doba trvání
2 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ě: Plánování projektu, plánování pomocí barvení grafu 44/68
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
Barvení grafu a rozvrhování
Rezervační problémy
Přiřazení místností
Rozvrhování operátorů
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 45/68
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
Intuice
obarvi uzly s vyšším stupněm dříve
obarvi uzly s vyšší úrovní saturace dříve
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 46/68
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
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
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 47/68
Přiřazení místností
Problém přiřazení místností
cíl: přiřazení místnosti každému předmětu se zadanými časy
úloha = předmět s několika schůzkami týdně, jejichž časy jsou určeny
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
možné řešení:
nalezení rozvrhu vzhledem k danému počtu místností
nalezení rozvrhu s minimálním počtem místností
Přiřazení místností jako barvení grafu
vrchol: předmět
hrana: mezi předměty, které vyžadují stejný čas výuky
barva vrcholu: odpovídá vybrané místnosti (zdroji)
sousedící vrcholy/předměty musí mít různé barvy/místnosti,
protože vyžadují stejný čas
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 48/68
Přiřazení místností: pří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
Řešení:
místnost červená žlutá žlutá červená šedá
čas/předmět A B C D E
1 + + - - -
2 - - + - +
3 - + - + -
4 + - + - -
5 - - - + +
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 49/68
Přiřazení místností: příklad (pokračování)
předmět A B C D E
saturace - 1 1 0 0
stupeň neob. - 1 1 2 2
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 50/68
Přiřazení místností: pří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
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 51/68
Přiřazení místností: příklad (dokončení)
předmět A B C D E
saturace - - - 1 1
stupeň neob. - - - 1 1
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 52/68
Přiřazení místností: příklad (dokončení)
předmět A B C D E
saturace - - - 1 1
stupeň neob. - - - 1 1
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 53/68
Přiřazení místností: příklad (dokončení)
předmět A B C D E
saturace - - - 1 1
stupeň neob. - - - 1 1
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 54/68
Rezervační problém
Příklady
rezervace aut
rezervace pokojů v hotelu
rezervace strojů v továrně
Určen časový interval pro každou rezervaci
pj = dj − rj
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í
lze rezervace realizovat s daným počtem zdrojů?
kolik zdrojů je třeba ke splnění rezervací?
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 55/68
Rezervační problém jako barvení grafu
Vrchol: rezervace
Hrana: pokud se dvě rezervace překrývají v čase
Barva vrcholu: odpovídá vybranému zdroji
sousedící vrcholy/rezervace musí mít různé barvy/zdroje,
protože se překrývají v čase
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 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í problém barvení grafu: 3
28
7
6
5
1
4
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 56/68
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ň
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
sousedící úlohy/vrcholy musí mít různý čas/barvu,
protože vyžadují stejného operátora
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ě: Plánování projektu, plánování pomocí barvení grafu 57/68
Příklad: plánová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
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 58/68
Příklad: plánová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
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 59/68
Příklad: plánová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
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 60/68
Příklad: plánování schůzek (dokončení)
5
1 3
2
4
Úroveň saturace = 1 pro všechny úlohy
Vyber 2 vzhledem k nejvyššímu stupni
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 61/68
Příklad: plánování schůzek (dokončení)
5
1 3
2
4
Úroveň saturace = 1 pro všechny úlohy
Vyber 2 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
5
1 3
2
4
Úroveň saturace = 2 pro všechny uzly
Vyber 4 vzhledem k nejvyššímu stupni
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 62/68
Příklad: plánování schůzek (dokončení)
5
1 3
2
4
Úroveň saturace = 1 pro všechny úlohy
Vyber 2 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
5
1 3
2
4
Úroveň saturace = 2 pro všechny uzly
Vyber 4 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
5
1 3
2
4
Úroveň saturace = 2 pro uzel 3
Úroveň saturace = 3 pro uzel 5
Vyber 5 na obarvení
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 63/68
Příklad: plánování schůzek (dokončení)
5
1 3
2
4
Úroveň saturace = 1 pro všechny úlohy
Vyber 2 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
5
1 3
2
4
Úroveň saturace = 2 pro všechny uzly
Vyber 4 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
5
1 3
2
4
Úroveň saturace = 2 pro uzel 3
Úroveň saturace = 3 pro uzel 5
Vyber 5 na obarvení
5
1 3
2
4
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 64/68
Příklad: plánování schůzek (dokončení)
5
1 3
2
4
Úroveň saturace = 1 pro všechny úlohy
Vyber 2 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
5
1 3
2
4
Úroveň saturace = 2 pro všechny uzly
Vyber 4 vzhledem k nejvyššímu stupni
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
£
5
1 3
2
4
Úroveň saturace = 2 pro uzel 3
Úroveň saturace = 3 pro uzel 5
Vyber 5 na obarvení
5
1 3
2
4 5
1 3
2
4
V posledním kroku obarvi 3
stejnou barvou jako 4
⇒celkem 4 barvy, tj. makespan=4
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 65/68
Shrnutí
Přiřazení místností
vrchol: předmět úloha
hrana: mezi předměty vyžadujícími stejný čas průnik časových bodů
barva vrcholu: odpovídá vybrané místnosti zdroj
sousedící vrcholy/předměty musí mít různé barvy/místnosti,
protože vyžadují stejný čas
Rezervační problém
vrchol: rezervace úloha
hrana: pokud se dvě rezervace překrývají v čase průnik intervalů
barva vrcholu: odpovídá vybranému zdroji zdroj
sousedící vrcholy/rezervace musí mít různé barvy/zdroje,
protože se překrývají v čase
Rozvrhování operátorů
vrchol: úloha úloha
hrana: mezi úlohami vyžadujícími stejného operátora průnik zdrojů
barva vrcholu: čas pro realizaci úlohy časový bod
sousedící úlohy/vrcholy musí mít různý čas/barvu,
protože vyžadují stejného operátora
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 66/68
Cvičení
Jakou grafovou reprezentaci mají následující problémy? Problémy vyřešte a ukažte
postup řešení.
1 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í
2 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ě: Plánování projektu, plánování pomocí barvení grafu 67/68
Cvičení (pokračování)
3 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átorů
PB165 Grafy a sítě: Plánování projektu, plánování pomocí barvení grafu 68/68