PB165 Grafy a sítě: Plánování projektu
PB165 Grafy a sítě: Plánování projektu 1/39
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 2/39
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)
P|prec|Cmax m  n metoda kritické cesty
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 3/39
Metoda kritické cesty
Popis algoritmu pro nalezení kritické cesty
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, jejichž nejdřívější startovní čas menší než nejpozdější startovní čas
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
množina kritických úloh
řetěz úloh začínající v čase 0 a končící v čase Cmax
PB165 Grafy a sítě: Plánování projektu 4/39
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 5/39
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 6/39
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 7/39
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 8/39
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 9/39
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 10/39
Algoritmus pro nalezení 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
kPrecj
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:jPreck
Sk , Sj = Cj - pj
ověř, že 0 = min(S1 , . . . , Sn )
PB165 Grafy a sítě: Plánování projektu 11/39
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 kritickou cestu 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á.
PB165 Grafy a sítě: Plánování projektu 12/39
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
jcj
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 13/39
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 14/39
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 15/39
Kompromisní heuristika mezi časem a cenou
Počáteční uzel: zdroj
Koncový uzel: stok
Řez: množina uzlů, jejíž smazáním z grafu
se rozpojí zdroj a stok
Minimální řez: vrácení libovolného uzlu z min. řezu
do grafu znovu spojí zdroj a stok
řez
zdroj stok
minimální řez
PB165 Grafy a sítě: Plánování projektu 16/39
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 17/39
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 18/39
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 19/39
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 20/39
Podgraf s kritickou cestou (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 21/39
Podgraf s kritickou cestou (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 22/39
Podgraf s kritickou cestou (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 23/39
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 24/39
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 25/39
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 26/39
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 27/39
Přiřazení místností
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 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 28/39
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 29/39
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 30/39
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 31/39
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 32/39
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 33/39
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 34/39
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 35/39
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 36/39
Shrnutí
Přiřazení místností
vrchol: předmět úloha
hrana: mezi předměty vyžadují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 37/39
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 38/39
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 39/39