Plánovaní projektu oooooooooooooooooooooo PB165 Grafy a site: 7. Plánování projektu PB165 Grafy a sítě: 7. Plánování projektu 1/24 Plánovaní projektu oooooooooooooooooooooo Plánování projektu a Základní problém plánování projektu » precedenční podmínky » paralelní stroj s neomezeným počtem strojů a 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^m » Rozšíření: variabilní doba trvání a 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/24 Plánovaní projektu •ooooooooooooooooooooo Neomezené zdroje Popis problému o Popis problému » paralelních stroj a n úloh s precedenčními omezeními o 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 o 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 3/24 Plánovaní projektu o»oooooooooooooooooooo Neomezené zdroje Metoda kritické cesty 9 Popis algoritmu pro nalezení kritické cesty o dopŕedná procedura o start v čase 0 o výpočet nejdřívějšího startovního času každé úlohy o čas dokončení poslední úlohy je makespan o zpětná procedura o start v čase rovném makespan o výpočet nejpozdejsího startovního času, aby byl realizován tento makespan o Úloha s rezervou (slack job) o její startovní čas může být odložen aniž je navýšen makespan o úloha, jejichž nejdrívejsí startovní čas menší než nejpozdější startovní čas o Kritická úloha a úloha, která nesmí být odložena » úloha, jejíž nejdrívejsí startovní čas je roven nejpozdejsímu start, času o Kritická cesta o množina kritických úloh » řetěz úloh začínající v čase 0 a končící v C3SG Cfnax PB165 Grafy a sítě: 7. Plánování projt.™ 4/24 Plánovaní projektu OOÄOOOOOOOOOOOOOOOOOOO Neomezené zdroje 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 !)—0—© ®-~® PB165 Grafy a sítě: 7. Plánování projektu 5/24 Plánovaní projektu ooo»oooooooooooooooooo Neomezené zdroje Příklad: dopředná procedura 5+6=11 11+12=23 23+10=33 33+9=42 L íq) 43+8=51 i "S 0+5=5 14+12=26 "^^(^-----»^14)51+5=56 T)----*0 26+10=36 íl-----►(13) 43+7=50 36+7=43 26+6=32 14+7=21 PB165 Grafy a sítě: 7. Plánování projektu 6/24 Plánovaní projektu oooo»ooooooooooooooooo Neomezené zdroje Príklad: zpětná procedura 12-6^6 24-12=12 34-10=24 -9=34 5-5=0/ i )0) 51-8=43 56-5=51 26-12=_L4 36-10=26 ~ ~^{\2)-----+(u) 1ľ~ V\)-----K13) 51 -7=44 43-7=36 26-7=19 36-6=30 PB165 Grafy a sítě: 7. Plánování projektu 7/24 Plánovaní projektu ooooo«oooooooooooooooo Neomezené zdroje Výsledky dopředně a zpětné procedury legenda 5+6=11 11+12=23 s;' + R = Q ,23+10=33 > Jl > 7k 0 legenda Q' '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Ü6 ^^~~~^(Í2)-----^Tí) O PB165 Grafy a sítě: 7. Plánování projektu 26-7=19 36-6=30 8/24 Plánovaní projektu oooooo»ooooooooooooooo Neomezené zdroje Porovnání S'y a S"y PB165 Grafy a sítě: 7. Plánování projektu 10) 43 51 19 30 9/24 Plánovaní projektu ooooooo«oooooooooooooo Neomezené zdroje Kritická cesta £^G^© Cmax= 56 ©-►© PB165 Grafy a sítě: 7. Plánování projektu 10/24 Plánovaní projektu oooooooo»ooooooooooooo Neomezené zdroje Algoritmus pro nalezení kritické cesty © Dopředná procedura 9 t = 0 © pro všechny úlohy j bez předchůdce: Sj = 0, C- = p/ 9 vypočítej postupně pro všechny zbývající úlohy _/': ®3?0 Sí = vSq^ Ci = Sl + P} (k3) 4 optimální makespan je Cmax = max(C1/,..., Q) O Zpětná procedura o pro všechny úlohy j bez následníka: r." — C S'.' — C —o-a vypočítej postupně pro všechny zbývající úlohy j: k2) C':'= min Sfk', S;'=q'-pj „>^ J Vk:jePreck k J J ' o ověř, žeiJ = min(S{',..., S'J) PB165 Grafy a sítě: 7. Plánován! projektu 11/24 Plánovaní projektu ooooooooo«oooooooooooo Neomezené zdroje Cvičení O 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ě: 7. Plánování projt..„ 12/24 Plánovaní projektu oooooooooo»ooooooooooo Variabilní doba trvaní Kompromis mezi casern a cenou 9 Lze uvažovat variabilní dobu trvání úloh » za předpokladu vyšší ceny lze zkrátit dobu provádění o Lineární cena o Doba trvání pf>" < pj < pj"ax Marginální cena: cena za zkrácení doby trvání úlohy o 1 časovou jednotku c? -ď ^. — J J „max __ „mm Hi Hi doba provádění „min ri-"aA Pj Pj => cena provádění úlohy j po dobu py. c1? + Cj(pj"ax — pj) PB165 Grafy a sítě: 7. Plánování projektu 13/24 Plánovaní projektu ooooooooooo«oooooooooo Variabilní doba trvaní Cena za provádění projektu 9 Fixní režijní náklady cq celkem: Cmaxco na časovou jednotku doby provádění projektu 9 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 a fixních režijních nákladů F(pj) = Cmaxc0 + ]T (c/ + Cj(p^ - pj)) j 9 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 oooooooooooo»ooooooooo Variabilní doba trvaní 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í a systém lineárních nerovnic s lineárním optimalizačním kritériem o simplexová metoda o optimální rozvrh » nelineární verze obtížně řešitelné PB165 Grafy a sítě: 7. Plánování projektu 15/24 Plánovaní projektu 0000000000000*00000000 Variabilní doba trvaní Kompromisní heuristika mezi casern a cenou o Počáteční uzel: zdroj o Koncový uzel: stok o Rez: množina uzlů, jejíž smazáním z grafu se rozpojí zdroj a stok 9 Minimální řez: vrácení libovolného uzlu z min. řezu do grafu znovu spojí zdroj a stok minimální řez j1*' „»■'"' "■» ~\ —f-------------•> ■■ - ,' n \ n' zdroj ' C^Kr^/t" ,' stok PB165 Grafy a sítě: 7. Plánování projektu 16/24 Plánovaní projektu oooooooooooooo»ooooooo Variabilní doba trvaní 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 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 17/24 Plánovaní projektu ooooooooooooooosoooooo Variabilní doba trvaní Algoritmus kompromisní heuristiky ^max 9 o Nastav doby provádění na jejich maximum: pj = pj' o Urči všechny kritické cesty s těmito dobami provádění o Zkonstruuj graf Gqp kritických cest Q o Urči všechny minimální řezy v Gcp a Najdi řezy, jejichž doba provádění je větší než jejich minimum: Pj > pf" Y/' g Gcp a Pokud takový rez neexistuje STOP, jinak běz na krok 3 9 • 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 o Redukuj všechny doby provádění v minimálním řezu o 1 časovou jednotku a Urči novou množinu kritických cest a Reviduj graf Gcp a běž na krok 2 PB165 Grafy a sítě: 7. Plánování projektu 18/24 Plánovaní projektu oooooooooooooooo»ooooo Variabilní doba trvaní Příklad (pokračování): maximální doba provádění PB165 Grafy a sítě: 7. Plánování projektu 19/24 Plánovaní projektu OOOOOOOOOOOOOOOOOÄOOOO Variabilní doba trvaní 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 pmin 3 5 7 9 5 9 8 3 7 5 4 5 5 2