Plánovaní projektu oooooooooooooooooooooo PB165 Grafy a sítě: 7. Plánování projektu PB165 Grafy a sítě: 7. Plánování projektu 1/38 Plánovaní projektu oooooooooooooooooooooo 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) a relativně jednoduché na řešení: metoda kritické (nejdelší) cesty princip: nalezneme kritickou cestu a ta určuje makespan 1 ©r0r©; • 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ě: 7. Plánování projektu 2/38 62 • 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 (makespan) 9 Poo I přec | 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 C'-' nejpozdější koncový čas úlohy j • Precj (přímí) předchůdci úlohy y 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ě: 7. Plánování projektu a 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ě: 7. Plánování projektu 4/38 Plánovaní projektu oo«ooooooooooooooooooo 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 £)—©—© ©—© PB165 Grafy a sítě: 7. Plánování projek 5/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura PB165 Grafy a sítě: 7. Plánování projektu 6/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura PB165 Grafy a sítě: 7. Plánování projektu 7/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura PB165 Grafy a sítě: 7. Plánování projektu 8/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura 5+6=11 11+12=23 2 )---•/?)---►( 7 1)0+5=5 14+12=26 14+7=21 PB165 Grafy a sítě: 7. Plánování projektu 9/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura 5+6=11 11+12=23 26+6=32 14+7=21 PB165 Grafy a sítě: 7. Plánování projektu 10/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura 5+6=11 11+12=23 26+6=32 14+7=21 PB165 Grafy a sítě: 7. Plánování projektu 11/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura 5+6=11 11+12=23 1)---•►( 13) 43+7=50 36+7=43 26+6=32 14+7=21 PB165 Grafy a sítě: 7. Plánování projektu 12/38 Plánovaní projektu ooo«oooooooooooooooooo Příklad: dopředná procedura 5+6=11 11+12=23 •-SÄ5+1 n 7k 33+9=42 L ío) 43+8=51 O 0+5=5 14+12=26 """"^(T^---»^14)51+5=56 T)---»{?)26+10=36 1)---»-(13)43+7=50 36+7=43 26+6=32 14+7=21 PB165 Grafy a sítě: 7. Plánování projektu 13/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura ©—©- PB165 Grafy a sítě: 7. Plánování projektu 14/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura ©—©- PB165 Grafy a sítě: 7. Plánování projektu 15/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura (^O PB165 Grafy a sítě: 7. Plánování projektu Q"-ß=^ 51-8=43 56-5=51 Í2V-*ŕí?) 16/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura (^O PB165 Grafy a sítě: 7. Plánování projektu legenda T . © Q"-ß=^ s43-9=34 . T\0) 51-8=43 56-5=51 y\J-----►( 13) 51 -7=44 43-7=36 17/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura PB165 Grafy a sítě: 7. Plánování projektu 34-10=24 legenda T . © Q"-ß=^ \43-9=34 - 7Ü)) 51-8=43 56-5=51 36-10=26 "-"***-• '' y\J-----►( 13) 51 -7=44 43-7=36 18/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura 24-12=12 34-10=24 ©—CD legenda T . © Q"-ß=^ 9=34 51-8=43 56-5=51 26-12=14 36-10=26 ~ Wl2^-----*(u) y\J-----►( 13) 51 -7=44 43-7=36 5)-----^8 26-7=19 36-6=30 PB165 Grafy a sítě: 7. Plánování projektu 19/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura 12-6=6 24-12=12 34-10=24 D—©—CD legenda T . © Q"-ß=^ 9=34 51-8=43 56-5=51 26-12=14 36-10=26 ~ Wl2^-----*/íí) y\J-----►( 13) 51 -7=44 43-7=36 26-7=19 36-6=30 PB165 Grafy a sítě: 7. Plánování projektu 20/38 Plánovaní projektu oooo»ooooooooooooooooo Příklad: zpětná procedura 12-6^6 24-12=12 34-10=24 S—©-H2) -9=34 5-5=0/ (\o\ 51-8=43 56-5=51 i '« 26-12=14 36-10=26 ~ Wíi}-----*(u) TÍ—®s legenda T . © c"->i-! y\J-----►( 13) 51 -7=44 43-7=36 26-7=19 36-6=30 PB165 Grafy a sítě: 7. Plánování projektu 21/38 Plánovaní projektu ooooo«oooooooooooooooo Výsledky dopřet tftUtlT legenda 5+6=11 11+12=23 ...... s; +p,=q ^^ s-^ ^-v 23+10=33 ! 2 )-----»{4 )-----►( 7 , 33+9=42 L 36+7=43 ' 51—►( 8 y ^26+6=32 14+7=21 12-6^6 24-12=12 34-10=24 ^43-9=34 MO) 51-8=43 56-5=51 12= 14 36-10=26 "~^*"@-----*© 14-9=5 1)-----KJ 3) 51-7=44 43-7=36 PB165 Grafy a sítě: 7. Plánování projektu 26-7=19 36-6=30 22/38 Plánovaní projektu oooooo»ooooooooooooc oo Porovnání S y a S y 43 51 26 "~^*"@-----*© PB165 Grafy a sítě: 7. Plánování projektu 19 30 23/38 Plánovaní projektu ooooooo«oooooooooooooo Kritická cesta !>-©—© \ j®-KD. PB165 Grafy a sítě: 7. Plánování projektu C =56 max @-K3> 24/38 Plánovaní projektu OOOOOOOO0OOOOOOOOOOOOO Algoritmus pro ESMEBBmSi O Dopředná procedura O í = 0 O pro všechny úlohy j bez předchůdce: Sj = 0, Cj = pj Q vypočítej postupně pro všechny zbývající úlohy j: ^© Si = v^,^ C/ = SÍ + « O optimální makespan je Cmax = max(C1/,..., C'„) O Zpětná procedura • t — *~max » pro všechny úlohy j bez následníka: rn — r en — r _ n. » vypočítej postupně pro všechny zbývající úlohy j: (jy-^® q= min Síy, S'{=C{-pi • ověř, žeiJ = min(S{',..., S^') PB165 Grafy a sítě: 7. Plánováni projektu 25/38 O Jaká je grafová reprezentace rozvrhovacího problému zadané ú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 Q Nalezeněte kritickou cestu v tomto grafu. Q Jaký má tento rozvrh makespan? Q Existují v problému úlohy s rezervou? Pokud ano, uveďte o které úlohy se jedná. PB165 Grafy a sítě: 7. Plánování projektu Plánovaní projektu OOOOOOOOOO0OOOOOOOOOOO Kompromis mezi č. mamamm • 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 ~ — J J doba provádění cena provádění úlohy j po dobu py. c1? + Cj(pj"ax — pj) PB165 Grafy a sítě: 7. Plánování projektu 27/38 Plánovaní projek ooooooooooo« tu oooooooooo Variabilní doba rvaní Cena za provádění • Fixní režijní náklady cq 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 (cf + Cj(pfax - pj)) • Cíl: V/ nalézt pj a Sj tak, aby byla F{pj) minimální prostředky (peníze) ^a doba provádění PB165 Grafy a sítě: 7. Plánování projektu Plánovaní projektu OOOOOOOOOOOO0OOOOOOOOO Variabilní doba trvání: • 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ě: 7. Plánování projektu 29/38 Plánovaní projektu ooooooooooooo«oooooooo Variabilní doba trvání 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 jrJ „*A "\ ~\ —ř----------------f ■> ■■ zdroj ', rx^/f ' stok rez-., PB165 Grafy a sítě: 7. Plánování projektu 30/38 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 í 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ě: 7. Plánování projektu 31/38 O • Nastav doby provádění na jejich maximum: pj = p!"ax • Urči všechny kritické cesty s těmito dobami provádění • Zkonstruuj graf Gqp kritických cest O • 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ý rez neexistuje STOP, jinak běz na krok 3 O • 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 O • 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ě: 7. Plánování projektu 32/38 Plánovaní projektu oooooooooooooooo«ooooo Variabilní doba trvání Příklad (pokračování): maximální doba provádění !>-©—© C =56 max \ ^©—© ©-*® PB165 Grafy a sítě: 7. Plánování projektu 33/38 Plánovaní projektu ooooooooooooooooo«oooo Kompromisní heuris 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 «í 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 co=6 Náklady na provedení projektu při maximální době trvání úloh F(pf*) = Cmaxc0 + Zj(c} + Cj{p?'ax-P?'axj) = = CmaxO) + 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ě: 7. Plánování projektu 34/38 Plánovaní projektu oooooooooooooooooo«ooo Podgraf s kritickou cestou {Gqp) Kandidáti na redukci: uzel 11 a uzel 12, vybereme uzel 12 c c p 7 12-2 c 14" 8 vL/ vLIx minimální řez c^4 c _ 2 s nejnižší cenou ir 0 Rezy:{1},{3},{6},{9} {11},{12},{14} redukce doby provádění úlohy 12 z 8 na 7 o Fixní režijní náklady se red ukují z 56 x 6 na 55 x 6 = 330 o Cena za provádění úloh naroste o C12 = 2, tj. 350 + 2 = 352 o Celko vá cena klesla z :686 na 330 + 352 = 682 PB165 Grafy a síté: 7. F 'lánování projektu 35/38 Plánovaní projektu ooooooooooooooooooo»oo Podgraf s kritickou cestou {Gqp) C 1=7 Q Cg=4 C 6=3 V n jT^-^ ^-y\7na6 X 9^ 12 10 >^ C 12= 2 Cl=8 ©-►© C1F2 C13=4 "*\ minimální řez s nejnižší cenou C3=4 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 cn = 2, tj. 352 + 2 = 354 • Celková cena klesla z 682 na 324 + 354 = 678 PB165 Grafy a sítě: 7. Plánování projektu 36/38 Plánovaní projektu oooooooooooooooooooo«o Podgraf s kritickou cestou {Gqp) C9=2/ CA= 3 C7=4 9-73) ' Cq= 4 5 C12- 2 C14-@—^O 5-2 další redukce: pro uzel 2 na 5 a pro uzel 11 na 5, ... • 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ě: 7. Plánování projektu 37/38 • Jaká je cena za provádění projektu, pokud jsou doby trvání úloh maximální, tj. čemu se rovná F{pj,l'x) za následujících předpokladů? • fixni režijní náklady na časovou jednotku jsou Co = 4 • pfax maximální doba trvání úlohy j • pf" minimální doba trvání úlohy y • q marginální cena • Cj cena za provádění úlohy j při maximální době jejího trvání • Preq předchůdci úlohy y j 1 2 3 4 5 6 7 8 pmax 4 4 4 4 4 4 3 6 pr 3 2 2 2 2 2 2 6 cľ 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 Preq - 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ě: 7. Plánování projektu 38/38