PB165 Grafy a site: Plánování projektu PB165 Grafy a sítě: Plánování projektu 1/24 Plánování projektu • Základní problém plánování projektu a precedenční podmínky • paralelní stroj s neomezeným počtem strojů • minimalizace maximálního času konce úloh (makespan) o relativně jednoduché na řešení: metoda kritické (nejdelší) cesty princip: nalezneme kritickou cestu a ta určuje makespan ©r©r©3 o Rozšíření: variabilní doba trvání o 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/24 Popis problému a 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) o Pqo | přec | Cmax m>n metoda kritické cesty Pm\prec\Cmax 2 < m < n NP úplný problém o Značení • Sj nejdřívější startovní čas úlohy j Cj = Sj + pj nejdřívější koncový úlohy j • S'-' nejpozdější startovní čas úlohy j O' 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/24 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 nejpozdejsí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ž nejdrívejsí startovní čas menší než nejpozdější startovní čas a Kritická úloha úloha, která nesmí být odložena o úloha, jejíž nejdrívejsí startovní čas je roven nejpozdejsímu start, času o 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/24 Kritická cesta: zadání prí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—(*y~© PB165 Grafy a sítě: Plánování projektu 5/24 Príklad: dopredná procedura 5+6=11 11+12=23 legenda © 23+10=33 \ 33+9=42 (To) 43+8=51 1| 0+5=5 14+12=26 """"-^(íi)-----^14)51+5=56 T)----^9)s26+10=36 Jf^ ? V)—*Ky 43+7=50 36+7=43 26+6=32 14+7=21 PB165 Grafy a sítě: Plánování projektu 6/24 Príklad: zpětná procedura 12-6^6 24-12=12 34-10=24 5-5=0 26-12=14 36-10=26 s)---*dT \á3-9=34 l-----^----> (To) 51-8=43 56-5=51 VT)-----►(13)51-7=44 43-7=36 26-7=19 36-6=30 PB165 Grafy a sítě: Plánování projektu 7/24 Výsledky dopředně a zpětné procedury 5+6=11 11+12=23 '—O- .23+10=33 legenda O 2 )------►( 4 )------►( 7 : _ 33+9=42 Ho) 43+8=51 ' 1 1 0+5=5 14+12=26 ^^^~*'(T2)-----»(w) 51 +5=56 legenda 12-6=6 24-12=12 34-10=24 C^" - pj = Sj' 43-9=34 10) 51-8=43 56-5=51 2=14 36-10=26 ^^~~~-*"(-Í2)-----*(?4) 26-7=19 36-6=30 PB165 Grafy a sítě: Plánování projektu B/24 10) 43 51 26 ^^~~~-*"(-Í2)------*(?4) PB165 Grafy a sítě: Plánování projektu 9/24 Kritická cesta !>^©—© 0-*@ PB165 Grafy a sítě: Plánování projektu 10/24 Algoritmus pro nalezení kritické cesty (Ď Dopředná procedura i í = 0 O pro všechny úlohy j bez předchůdce: Sj = 0, Cj = p/ O vypočítej postupně pro všechny zbývající úlohy j: íkil : k2)^ n s; = max c;, c/ = s; + P7 J VkePrecj J J J 'k3l 9 optimální makespan je Cmax = max(C1/,..., C'n) 9 Zpětná procedura • í = Cmax o pro všechny úlohy j bez následníka: Cj' = Cmax, Sj' = Cmax o vypočítej postupně pro všechny zbývající úlohy j: mr^@ C'= min SX, S':'=C':'-pj W""-0=^ J Vk:jePreck k J J J • ověř, že 0 = min(S{',..., S'n') PB165 Grafy a sítě: Plánování projektu Cvičení 9 Jaká je grafová reprezentace rozvrhovacího problému zadaného ú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 9 Nalezeněte kritickou cestu v tomto grafu. 9 Jaký má tento rozvrh makespan? 9 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/24 Kompromis mezi casern 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í pfm < pj < pj"ax Marginální cena: cena za zkrácení doby trvání úlohy o 1 časovou jednotku prostředky (peníze) CJ „max __ nmm doba provádění cena provádění úlohy j po dobu pj: c1? + Cj(pj"ax — pj) PB165 Grafy a sítě: Plánování projektu 13/24 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 a 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) = Cmaxco + Y,(CJ+ cÁPr - Pií) • 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 resení • Objektivní funkce: minimální cena projektu o Kompromisní heuristika mezi časem a cenou o dobrá kvalita rozvrhu o použitené i pro nelineární cenu o Další přístupy: formulace lineárního programování o 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/24 Kompromisní heuristika mezi casern a cenou » Počáteční uzel: zdroj o Koncový uzel: stok 9 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 jp zdroj i ._ PB165 Grafy a sítě: Plánování projektu 16/24 Kompromisní heuristika: prí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 nmin 3 5 7 9 5 9 8 3 7 5 4 5 5 2 Cf 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 17/24 Algoritmus kompromisní heuristiky Q o Nastav doby provádění na jejich maximum: pj = p!"ax o Urči všechny kritické cesty s těmito dobami provádění o Zkonstruuj graf Gqp kritických cest 9 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ý řez neexistuje STOP, jinak bez na krok 3 9 a Pro každý minimální řez: spočítej cenu redukující všechny doby provádění o 1 časovou jednotku o 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 o 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/24 Príklad (pokračování): maximální doba provádění PB165 Grafy a sítě: Plánování projektu 19/24 Kompromisní heuristika: prí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 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 Náklady na provedení projektu při maximální době trvání úloh F(p^x) = Cmaxco + Zj(cf + Cj{P?ax - PTax)) = = CmaxCo + 5_// 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 20/24 Podgraf s kritickou cestou (Gcp) o Kandidáti na redukci: uzel 11 a uzel 12, vybereme uzel 12 c1=7 Q clf2 c i2" 2 c 14- 8 ©-►© Rezy:{1},{3},{6},{9} {11},{12},{14} minimální řez s nejnižší cenou 0 redukce doby provádění úlohy 12 z 8 na 7 o 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\2 = 2, tj. 350 + 2 = 352 Celková cena klesla z 686 na 330 + 352 = 682 PB165 Grafy a sítě: Plánování projektu 21/24 Podgraf s kritickou cestou (Gcp) C 1=7 12=' 14=' Q C 6=3 ■9=' \^T^ ©-►© C3=4 Rezy:{1},{3},{6},{9} {11},{12,13},{14} C1F2 c13=4 "*\ minimální řez s nejnižší cenou redukce doby trvání úlohy 11 ze 7 na 6 o 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 22/24 C2=2 ■■ C4= 3 C7=4 ,12-9 Podgraf-Sukritickou cestou (Gcp) 2/ c4=; ---.._■■.. mo r "@—►© 5 C12- 2 C14-^8-5 0_^0 ; \ X>*12-9 lo-y^XT^ C,= 4 11 Hľ^M 3)7-5 Cn=2n' C13=4 další redukce: pro uzel 2 na 5 a pro uzel 11 na 5, ... o 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 23/24 Kompromisní heuristika: cvičení 9 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í o 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 O 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/24