PB165 Grafy a sítě: Plánování projektu PB165 Grafy a sítě: Plánování projektu 1/38 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 ©r©r©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/38 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) • Poo |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 O = S'- + pj nejdřívější koncový úlohy j • Sj' nejpozdější startovní čas úlohy j C-' nejpozdější koncový čas úlohy j • Precj (přímí) předchůdci úlohy j V/c G PreCj všechny úlohy k, které předcházejí úlohu j V/' : k G PreCj všechny úlohy j, které následují úlohu k PB165 Grafy a sítě: Plánování projektu 3/38 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 a 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 a ú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/38 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 D—©—© @—@ PB165 Grafy a sítě: Plánování projektu 5/38 Příklad: dopředná procedura 2^©-^© PB165 Grafy a sítě: Plánování projektu 6/38 Příklad: dopředná procedura 2^©-^© PB165 Grafy a sítě: Plánování projektu 7/38 Příklad: dopředná procedur, PB165 Grafy a sítě: Plánování projektu 8/38 Příklad: dopředná procedur, 5+6=11 11+12=23 D—©—©X 1)0+5=5 14+12=26 5+9= 14+7=21 PB165 Grafy a sítě: Plánování projektu 9/38 Příklad: dopředná procedura 5+6=11 11+12=23 26+6=32 14+7=21 PB165 Grafy a sítě: Plánování projektu 10/38 Příklad: dopředná procedura 5+6=11 11+12=23 1)0+5=5 14+12=26 5+9= 26+6=32 14+7=21 PB165 Grafy a sítě: Plánování projektu 11/38 Příklad: dopředná procedura 5+6=11 11+12=23 -^ w w\33+ 23+10=33 33+9=42 1)0+5=5 14+12=26 43+8=51 T2}-----te 13)43+7=50 5+9= 26+6=32 14+7=21 PB165 Grafy a sítě: Plánování projektu 12/38 Příklad: dopředná procedura 5+6=11 11+12=23 -^ w w\33+ 23+10=33 33+9=42 1)0+5=5 14+12=26 43+8=51 'rŽ)-----»/14) 51+5=56 13)43+7=50 5+9= 26+6=32 14+7=21 PB165 Grafy a sítě: Plánování projektu 13/38 Příklad: zpětná procedura 1^©—© PB165 Grafy a sítě: Plánování projektu 14/38 Příklad: zpětná procedura 1^©—© PB165 Grafy a sítě: Plánování projektu 15/38 Příklad: zpětná procedura 1^©—© PB165 Grafy a sítě: Plánování projektu 51-8=43 56-5=51 11)-----n13) 51-7=44 16/38 Příklad: zpětná procedura i^©—© PB165 Grafy a sítě: Plánování projektu ,43-9=34 (ÍO) 51-8=43 56-5=51 11 '43-7=36 13)51-7=44 17/38 Příklad: zpětná procedura 34-10=24 ■©—©v ^43-9=34 (TB) 51-8=43 56-5=51 36-10=26 "^^(1^)-----+(u) 6^^9)n 13)51-7=44 PB165 Grafy a sítě: Plánování projektu 18/38 Příklad: zpětná procedura 24-12=12 34-10=24 26-12=14 36-10=26 \43-9=34 l-----^-----) (TB) 51-8=43 56-5=51 y\J----►(13)51-7=44 43-7=36 5)-----^8 26-7=19 36-6=30 PB165 Grafy a sítě: Plánování projektu 19/38 Příklad: zpětná procedura 12-6=6 24-12=12 34-10=24 26-12=14 36-10=26 \43-9=34 (TB) 51-8=43 56-5=51 y\J----►(13)51-7=44 43-7=36 5)-----^8 26-7=19 36-6=30 PB165 Grafy a sítě: Plánování projektu 20/38 Příklad: zpětná procedura 12-6^6 24-12=12 34-10=24 \43-9=34 5-5=0/ (TB) 51-8=43 56-5=51 1 ) 26-12=14 36-10=26 """"" ^^ ^^ 5J----*(8 26-7=19 36-6=30 ^MJ-----►(13)51-7=44 43-7=36 PB165 Grafy a sítě: Plánování projektu 21/38 Výsledky dopředně a zpětné procedury legenda 0 5+6=11 11+12=23 ...... ^^ ^-^ ^^ 23+10=33 2>-v)—\5 ^ ^^ v-^ \ 33+9=42 (ío) 43+8=51 ' 1 ^ 0+5=5 14+12=26 ^^"""""*'@-----*© 51 +5=56 26+6=32 14+7=21 O legenda 12-6=6 24-12=12 34-10=24 C^" - pj = Sj ' IT)-----«^7)----►('ľN ^ — 43-9=34 5-5=0/ 7?0) 51-8=43 56-5=51 26-12=14 36-10=26 ^^^"-(TS)-----./u) 14-9: PB165 Grafy a sítě: Plánování projektu 22/38 Porovnání S y a S"y 10) 43 51 26 ^'^"-»•^2)------^14) PB165 Grafy a sítě: Plánování projektu 23/38 Kritická cesta 2)^0^0. C =56 max \ JS>—©■ ©-H© PB165 Grafy a sítě: Plánování projektu 24/38 Algoritmus pro nalezení kritické cesty O Dopředná procedura O í = 0 Q pro všechny úlohy j bez předchůdce: Sj = 0, C- = pj Q vypočítej postupně pro všechny zbývající úlohy j: Sj max CĹ VkEPreCj V Sj- Pj CL) O optimální makespan je Cmax = max(C1/, O Zpětná procedura • f = *~-max » pro všechny úlohy _/ bez následníka: Cy' = Cmax, S a vypočítej postupně pro všechny zbývající úlohy j: C„ ■Pj k2 • over, ze 0 C: min(S{'. min S, Mk:jePreck k-. C; ■pj PB165 Grafy a sítě: Plánování projektu 25/38 O 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 O Nalezeněte kritickou cestu v tomto grafu. Q Jaký má tento rozvrh makespan? O 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 26/38 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í pfn < pj < pj"ax • Marginální cena: cena za zkrácení doby trvání úlohy o 1 časovou jednotku prostředky (peníze) CJ doba provádění cena provádění úlohy j po dobu py. c1? + Cj(pj"ax — pj) PB165 Grafy a sítě: Plánování projektu 27/38 Cena za provádění projektu • Fixní režijní náklady co celkem: Cmaxco 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 + ]T (c/ + Clip?** - pj)) • Cíl: V/' nalézt pj a Sj tak, aby byla F{pj) minimální prostředky (peníze) doba provádění ^a PB165 Grafy a sítě: Plánování projektu 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 29/38 Kompromisní heuristika mezi časem a cenou • Počáteční uzel: zdroj • Koncový uzel: stok • Rez: 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 minimální řez j' i i zdr°j ', rx^/r*' . stok PB165 Grafy a sítě: Plánování projektu 30/38 Kompromisní heuristika: příklad j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 „max 5 6 9 12 7 12 10 6 10 9 7 8 7 5 «min ri 3 5 7 9 5 9 8 3 7 5 4 5 5 2 «í 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 cq=6 PB165 Grafy a sítě: Plánování projektu 31/38 Algoritmus kompromisní heuristiky O O Nastav doby provádění na jejich maximum: pj = pj"3x Urči všechny kritické cesty s těmito dobami provádění Zkonstruuj graf Gqp kritických cest Urči všechny minimální řezy v Gcp Najdi řezy, jejichž doba provádění je větší než jejich minimum: Pj>pf" Y/'G Gcp Pokud takový řez neexistuje STOP, jinak bez na krok 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 cq za časovou jednotku běž na krok 4, jinak STOP 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 32/38 Příklad (pokračování): maximální doba provádění 2)^0^0. C =56 max \ JS>—©■ ©-•o PB165 Grafy a sítě: Plánování projektu 33/38 Kompromisní heuristika: příklad co =6 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 _max 5 6 9 12 7 12 10 6 10 9 7 8 7 5 pmin 3 5 7 9 5 9 8 3 7 5 4 5 5 2 «f 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 = CmaxCo + zZj cj = = 56x6 + 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 34/38 Podgraf s kritickou cestou {Gqp) 9 Kandidáti na redukci: uzel 11 a uzel 12, vybereme uzel 12 © '6" Cg=4 \ c3=4 Rezy:{1},{3},{6},{9} {11},{12},{14} .0-^0 clf2 minimální řez s nejnižší cenou 0 redukce doby provádění úlohy 12 z 8 na 7 • Fixní režijní náklady se redukují z 56 x 6 na 55 x 6 = 330 • Cena za provádění úloh naroste o c\i = 2, tj. 350 + 2 = 352 • Celková cena klesla z 686 na 330 + 352 = 682 PB165 Grafy a sítě: Plánování projektu 35/38 Podgraf s kritickou cestou {Gqp) c 1=7 O Cg=4 c<=3 V q jT^-7 v~y\7na6 X 9X^ 12 10 >^ C 12= 2 C 1^8 ©-►© Ca=4 C1F2 C13=4 "*\ minimální řez s nejnižší cenou Rezy:{1},{3},{6},{9} {11},{12,13},{14} redukce doby trvání úlohy 11 ze 7 na 6 • Fixní režijní náklady se redukují z 55 x 6 na 54 x 6 = 324 • Cena za provádění úloh naroste o en = 2, tj. 352 + 2 = 354 • Celková cena klesla z 682 na 324 + 354 = 678 PB165 Grafy a sítě: Plánování projektu 36/38 Podgraf s kritickou cestou {Gqp) C3=4 další redukce: pro uzel 2 na 5 a pro uzel 11 na 5, .. I—hJ) • Fixní režijní náklady se redukují z 54 x 6 na 53 x 6 = 318 • Cena za provádění úloh naroste o C2 + cn = 2 + 2, tj. 354 + 4 = 358 • Celková cena klesla z 678 na 318 + 358 = 676 PB165 Grafy a sítě: Plánování projektu 37/38 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{pfax) za následujících předpokladů? a fixni režijní náklady na časovou jednotku jsou Co = 4 • pj"ax maximální doba trvání úlohy y • pj"'n minimální doba trvání úlohy j • ej marginálni cena • Cj cena za provádění úlohy y při maximální době jejího trvání • Precj předchůdci úlohy y j 1 2 3 4 5 6 7 8 pmax 4 4 4 4 4 4 3 6 j 1 2 3 4 5 6 7 8 p!"i- 3 2 2 2 2 2 2 6 Precj - 2 4,5 2 2 3,7 5 6 sb 20 25 20 15 30 40 35 25 CJ 3 5 5 1 2 5 3 5 • 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 38/38