PB165 Grafy a sítě: Úvod k plánování a rozvrhování PB165 Grafy a sítě: Úvod k plánování a rozvrhování 1/53 Grafy a sítě v plánování a rozvrhování: osnova O Problém rozvrhování: vlastnosti stroje, omezení, optimalizace O Precedenční omezení a disjunktivní grafová reprezentace: korespondence mezi rozvrhem a grafem O Plánování projektu (precedenční omezení): kritická cesta, kompromisní heuristika O Barvení grafu: algoritmus saturace a problémy přiřazení místností, rezervační problém, plánování operátorů O Hranově ohodnocené grafy: obchodní cestující, doba na dopravu, plánování na počítačových sítích O Plánování s komunikací a s precedencemi: plánování seznamem, heuristiky mapování, shlukovací heuristiky O Paralelní úlohy s průběžnou komunikací: vyvažování zátěže a rozdělení grafu Rozvrhování na Fl: PA167 Rozvrhování, PA163 Omezující podmínky PB165 Grafy a sítě: Úvod k plánování a rozvrhování 2/53 Rozvrhování a plánování (scheduling) • Zdroj/stroj • kapacita • dostupnost v čase • rychlost • Úloha/aktivita • nejdřívější startovní čas • nej pozdější koncový čas • doba trvání (na referenčním zdroji) • počet zdrojů • alternativní zdroje • Rozvrhování • optimální alokace/přiřazení zdrojů v čase množině úloh • omezené množství zdrojů • maximalizace zisku za daných omezení Visopt ShopFloor System PB165 Grafy a site: Úvod k plánování a rozvrhování 3/53 Příklad: rozvrhování s precedencemi • Rozvrhování 7 úloh na 2 zdrojích • doba trvání úlohy + precedenční podmínky » nalezení rozvrhu tak, aby se minimalizovala doba nutná na realizaci všech úloh kritická cesta PB165 Grafy a sítě: Úvod k plánování a rozvrhování 4/53 Příklad: rozvrhování s precedencemi • Rozvrhování 7 úloh na 2 zdrojích • doba trvání úlohy + precedenční podmínky » nalezení rozvrhu tak, aby se minimalizovala doba nutná na realizaci všech úloh 2 © 2© 1 2 1 / \1 1 2 1 / \1 -® v'lV«<2)-<4 ř-<5V -^j} kritická cesta • Možný rozvrh • na kritické (nejdelší) cestě nesmí vzniknout zdržení Zdroj 2 [ 2 I I ° I Zdroj 1 | 1 | 3 hl 5 |7 i—i—i—i—i—i—i—i—i—r PB165 Grafy a sítě: Úvod k plánování a rozvrhování 5/53 Úlohy, stroje • Stroje / = 1,..., m • Úlohy j = 1,..., n • (/,_/') operace nebo provádění úlohy j na stroji / • úloha se může skládat z několika operací • příklad: úloha 4 má tři operace s nenulovou dobou trvání (2,4),(3,4),(6,4), tj. je prováděna na strojích 2,3,6 • Statické parametry úlohy • doba trvání p-,ypy doba provádění úlohy y na stroji i • termín dostupnosti j (release date) ry. nejdřívejsí čas, ve kterém může být úloha j prováděna • termín dokončení (due date) dy. čas, do kdy musí být úloha j nejpozději dokončena • váha wy. důležitost úlohy y relativně vzhledem k ostatním úlohám v systému PB165 Grafy a sítě: Úvod k plánování a rozvrhování 6/53 Úlohy, stroje • Stroje / = 1,..., m • Úlohy j = 1,..., n • (/,_/') operace nebo provádění úlohy j na stroji / • úloha se může skládat z několika operací • příklad: úloha 4 má tři operace s nenulovou dobou trvání (2,4),(3,4),(6,4), tj. je prováděna na strojích 2,3,6 • Statické parametry úlohy • doba trvání p-,ypy doba provádění úlohy y na stroji i • termín dostupnosti j (release date) ry. nejdřívejsí čas, ve kterém může být úloha j prováděna • termín dokončení (due date) dy. čas, do kdy musí být úloha j nejpozději dokončena • váha wy. důležitost úlohy y relativně vzhledem k ostatním úlohám v systému • Dynamické parametry úlohy • čas startu úlohy (start time) S,y, Sy. čas, kdy začne provádění úlohy j na stroji i • čas konce úlohy (completion time) C\y Cy. čas, kdy je dokončeno provádění úlohy j na stroji ; PB165 Grafy a sítě: Úvod k plánování a rozvrhování 7/53 Grahamova klasifikace Grahamova klasifikace cü|/3|7 používá se pro popis rozvrhovacích problémů • a: charakteristiky stroje • popisuje způsob alokace úloh na stroje • ß: charakteristiky úloh • popisuje omezení aplikovaná na úlohy • 7: optimalizační kritéria PB165 Grafy a sítě: Úvod k plánování a rozvrhování 8/53 Grahamova klasifikace Grahamova klasifikace cü|/3|7 používá se pro popis rozvrhovacích problémů • a: charakteristiky stroje • popisuje způsob alokace úloh na stroje • ß: charakteristiky úloh • popisuje omezení aplikovaná na úlohy • 7: optimalizační kritéria http://wMM.mathematik.uni-osnabrueck.de/research/OR/class/ • složitost a algoritmy pro jednotlivé rozvrhovací problémy PB165 Grafy a sítě: Úvod k plánování a rozvrhování 9/53 Základní stroje Jeden stroj 1: 1| ... | ... • nejjednodušší varianta • speciální případ dalších složitějších prostředí stroje Identické paralelní stroje Pm • m identických strojů zapojených paralelně (se stejnou rychlostí) • úloha je dána jedinou operací • úloha může být prováděna na libovolném z m strojů ■-0-0-0-0- PB165 Grafy a sítě: Úvod k plánování a rozvrhování 10/53 Stroje s různou rychlostí Paralelní stroje s různou rychlostí Qm • doba trvání úlohy 7 na stroji / přímo závislá na jeho rychlosti v; • Pij = Pj/vi • příklad: několik počítačů s různou rychlostí procesoru PB165 Grafy a sítě: Úvod k plánování a rozvrhování 11/53 Stroje s různou rychlostí Paralelní stroje s různou rychlostí Qm • doba trvání úlohy 7 na stroji / přímo závislá na jeho rychlosti v; • Pij = Pj/vi • příklad: několik počítačů s různou rychlostí procesoru Nezávislé paralelní stroje s různou rychlostí Rm • stroje mají různou rychlost pro různé úlohy a stroj / zpracovává úlohu j rychlostí v,y • Pij = Pj/vij • příklad: vektorový počítač počítá vektorové úlohy rychleji než klasické PC PB165 Grafy a sítě: Úvod k plánování a rozvrhování 12/53 Multi-operační (shop) problémy Multi-operační (shop) problémy • jedna úloha je prováděna postupně na několika strojích • úloha j se skládá z několika operací (i, j) • operace (i, j) úlohy _/ je prováděna na stroji ; po dobu p-,j • příklad: úloha j se 4 operacemi 1 stroj 4 stroj (l,y), (2,y), (3,7), (4,7) (X>0*0 3.sTroj 2.str stroj PB165 Grafy a sítě: Úvod k plánování a rozvrhování 13/53 Multi-operační (shop) problémy Multi-operační (shop) problémy • jedna úloha je prováděna postupně na několika strojích • úloha j se skládá z několika operací (i, j) • operace (i, j) úlohy _/ je prováděna na stroji ; po dobu p-,j • příklad: úloha j se 4 operacemi 1 stroj 4 stroj (l,y), (2,y), (3,7), (4,7) CK>00 3.sTroj 2.str Open shop Om °'&r0J • multi-operační problém s m stroji (žádné nové vlastnosti) Job shop J m • multi-operační problém s m stroji • pořadí provádění operací je předem určeno • příklad: (2,y) -+ (l,y) ^ (3,y) -+ (4,y) stroj PB165 Grafy a sítě: Úvod k plánování a rozvrhování 14/53 Multi-operační (shop) problémy Multi-operační (shop) problémy • jedna úloha je prováděna postupně na několika strojích • úloha j se skládá z několika operací (i, j) • operace (i, j) úlohy _/ je prováděna na stroji ; po dobu p-,j • příklad: úloha j se 4 operacemi 1 stroj 4 stroj (l,y), (2,y), (3,7), (4,7) CK>00 r\ ĺ /-> 3.stroj 2.stroj Upen snop Um ' ' • multi-operační problém s m stroji (žádné nové vlastnosti) Job shop J m • multi-operační problém s m stroji • pořadí provádění operací je předem určeno « příklad: (2,y) -+ (l,y) ^ (3,y) ^ (4,y) Multi-operační problémy = klasické detailně studované problémy operačního výzkumu • reálné problémy mnohem komplikovanější • metody řešení lze použít jako základ pro řešení složitějších problémů • př. automobilová výrobní linka PB165 Grafy a sítě: Úvod k plánování a rozvrhování 15/53 Precedenční podmínky přec • úloha může být prováděna až po skončení další(ch) úloh • pro úlohy a, b píšeme a —>■ b, což znamená Sa + pa < St, Vhodnost stroje Mj 9 podmnožina strojů Mj, na níž lze provádět úlohu j 9 př. úloha může být prováděna pouze na těch strojích v počítačové síti, kde jsou dostupná data PB165 Grafy a sítě: Úvod k plánování a rozvrhování 16/53 Směrovací (routing) omezení • udávají, na kterých strojích musí být úloha prováděna • vazba na směrování v počítačových sítích • pořadí provádění úlohy v multi-operačních problémech • job shop problém: pořadí operací předem stanoveno • open shop problém: pořadí operací úlohy (route for the job) stanoveno až při rozvrhování PB165 Grafy a sítě: Úvod k plánování a rozvrhování 17/53 Doprava a komunikace tjki, íw, tj • doba nutná na přepravu úlohy j mezi dvěma zařízeními k a / • tjki doba na přepravu ze stroje k na stroj / pro úlohu j • tki doba nezávislá na úloze • tj doba nezávislá na strojích • omezení na přepravované/přenášené množství a možnou dobu přepravy • omezení na propustnost (kapacitu) hrany/linky • omezení na vzdálenost uzlů pro přepravu/přenos tki dáno vzdáleností uzlů v síti/grafu: PB165 Grafy a sítě: Úvod k plánování a rozvrhování 18/53 Optimalizace: makespan • Maximální čas konce úloh (makespan) Cmax = max(Ci,..., C„) • Příklad: Cmax = max{l, 3,4,5,8,7, 9} = 9 Zdroj 2 [ 2 1 1 s i Zdroj 1 | 1 | 3 hl 5 |7 i—i—i—i—i—i—i—i—i—r PB165 Grafy a sítě: Úvod k plánování a rozvrhování 19/53 Optimalizace: makespan • Maximální čas konce úloh (makespan) Cmax = max(Ci,..., C„) • Příklad: Cmax = max{l, 3,4,5,8,7, 9} = 9 Zdroj 2 [ 2 1 1 s i Zdroj 1 | 1 | 3 hl 5 |7 I—I—I—I—I—I—I—I—I—I--------*■ • Cíl: minimalizace makespan často • maximalizuje výkon (throughput) • zajišťuje rovnoměrné zatížení strojů (load balancing) • příklad: Cmax = max{l, 2, 4, 5, 7,4, 6} = 7 cas —►• Zdroj 2 2 6 5 Zdroj 1 1 3 4 7 • Velmi často používané kritérium PB165 Grafy a sítě: Úvod k plánování a rozvrhování 20/53 Optimalizace: zpoždění • Zpoždění (lateness) úlohy j: Lj = Cj — dj • Cíl: minimalizace zpoždění Lmax = max(/.!,...,/.„) • Příklad: 1 3 2 I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—M»-0 5 10 15 í t í Cti Ĺto (Jsj max(Z.i,/_2,/-3) = max(G - c/i, C2 - d2, C3 - c/3) max(4 - 8,16 - 14,10-10) = max(-4,2,0) = 2 PB165 Grafy a sítě: Úvod k plánovaní a rozvrhování 21/53 Optimalizace: nezáporné zpoždění • Nezáporné zpoždění (tardiness) úlohy j: Tj = max(C/ — c/y,0) • Cíl: minimalizace celkového zpoždění y^Tj celkové zpoždění úloh 1 3 2 I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—»-Příklad: 0 5 10 15 t t t T1 + T2 + T2 = max(Ci -c/i,0) + max(C2-c/2,0) + max(C3-c/3,0) = max(4-8,0) + max(16-14,0) + max(10-10,0) = 0+2 + 0 = 2 PB165 Grafy a sítě: Úvod k plánovaní a rozvrhování 22/53 Optimalizace: nezáporné zpoždění • Nezáporné zpoždění (tardiness) úlohy j: Tj = max(C/ — c/y,0) • Cíl: minimalizace celkového zpoždění y^Tj celkové zpoždění úloh 1 3 2 I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—»- • Příklad: 0 5 10 15 t t t T1 + T2 + T2 = max(Ci -c/i,0) + max(C2-c/2,0) + max(C3-c/3,0) = max(4-8,0) + max(16-14,0) + max(10-10,0) = 0+2 + 0 = 2 • Cíl: minimalizace celkového váženého zpoždění n \JwjTj celkové vážené zpoždění úloh PB165 Grafy a sítě: Úvod k plánovaní a rozvrhování 23/53 Termín dokončení a grafy Lateness Pozdě nebo ne Ui dj PB165 Grafy a sítě: Úvod k plánovaní a rozvrhování Tardiness V praxi dj 3 24/53 Příklady rozvrhovacích problému s Grahamovou klasifikací • l|prec|Cmax • plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan PB165 Grafy a sítě: Úvod k plánování a rozvrhování 25/53 Příklady rozvrhovacích problému s Grahamovou klasifikací • l|prec|Cmax • plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan • Pm\rj, Mj\ Y^ wjTj • systém s m stroji zapojenými paralelně, kde • úloha j přijde v čase rj a má být naplánována do času dj • úloha j může být naplánována pouze na podmnožině strojů dané Mj a pokud není úloha j zpracována včas, tak je penalizována wjTj PB165 Grafy a sítě: Úvod k plánování a rozvrhování 26/53 Příklady rozvrhovacích problému s Grahamovou klasifikací l|prec|Cmax • plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan Pm\rj,Mj\J2wjTj • systém s m stroji zapojenými paralelně, kde • úloha j přijde v čase rj a má být naplánována do času dj • úloha j může být naplánována pouze na podmnožině strojů dané Mj a pokud není úloha j zpracována včas, tak je penalizována wjTj Jm\\Cmax • job shop problém, kde je cílem minimalizovat makespan • velmi často studovaný a velmi známý typ job-shop problému PB165 Grafy a sítě: Úvod k plánování a rozvrhování 27/53 Příklady rozvrhovacích problému s Grahamovou klasifikací • l|prec|Cmax • plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan • Pm\rj, Mj\ Y^ wjTj • systém s m stroji zapojenými paralelně, kde • úloha j přijde v čase rj a má být naplánována do času dj • úloha j může být naplánována pouze na podmnožině strojů dané Mj a pokud není úloha j zpracována včas, tak je penalizována wjTj • Jm\\Cmax • job shop problém, kde je cílem minimalizovat makespan • velmi často studovaný a velmi známý typ job-shop problému • P oo| přec |Cmax a problém s neomezeným počtem strojů zapojených paralelně, kde jsou úlohy provázány precedenčními podmínkami a kde je cílem minimalizovat makespan • klasický problém plánování projektu PB165 Grafy a sítě: Úvod k plánování a rozvrhování 28/53 Úvod k plánování a rozvrhování \J V\J\J • Vlastnosti stroje • Omezení • Optimalizace • Příklady Grafová reprezentace pro: • Precedenční omezení • Disjunktivní grafová reprezentace PB165 Grafy a sítě: Úvod k plánování a rozvrhování 29/53 Precedenční omezení • Úloha může být prováděna až po skončení další(ch) úloh • úloha a před úlohou b: a —> b : Sa + pa < S^, • Orientovaný acyklický vrcholově ohodnocený graf a uzly reprezentují úlohy » hrany reprezentují precedenční podmínky • ohodnocení vrcholu reprezentuje dobu trvání • graf bez cyklů (pro cyklický graf neexistuje žádné řešení) Úloha Doba trvání Předchůdci 1 2 - 2 3 1 3 1 1 4 4 2 5 2 3 6 1 4,5 7 3 4,5 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 30/53 Úloha jako obdélník • Úloha jako uzel lze převést na úloha jako obdélník úloha j úloha k ' • Horizontální strany obdélníku použity jako časové osy odpovídající době provádění úlohy zdroj 3 zdroj 2 zdroj 1 ľ ŕ cas PB165 Grafy a sítě: Úvod k plánování a rozvrhování 31/53 Precedenční omezení: aplikace • Příklad: zprostředkování, instalace a testování rozsáhlého počítačového systému • projekt zahrnuje • evaluace a výběr hardware, vývoj software, nábor a školení lidí, testování a ladění systému, ... • precedenční vztahy • některé úlohy mohou být prováděny paralelně • úloha musí být realizována až po dokončení jiných úloh • cíl: minimalizovat čas na realizaci celého projektu, tj. makespan PB165 Grafy a sítě: Úvod k plánování a rozvrhování 32/53 Precedenční omezení: aplikace • Příklad: zprostředkování, instalace a testování rozsáhlého počítačového systému • projekt zahrnuje • evaluace a výběr hardware, vývoj software, nábor a školení lidí, testování a ladění systému, ... • precedenční vztahy • některé úlohy mohou být prováděny paralelně • úloha musí být realizována až po dokončení jiných úloh a cíl: minimalizovat čas na realizaci celého projektu, tj. makespan • Obecně: problémy plánování projektu • příští přednáška • Rozšíření: plánování workflows O orientovaný acyklický graf pro provádění úloh na počítačové síti O obecné rozšíření: cyklické grafy + podmínky vyhodnocení cyklů PB165 Grafy a sítě: Úvod k plánování a rozvrhování 33/53 Disjunktivní grafová reprezentace a multi-operační rozvrhování • n úloh • m strojů • Jedna úloha je prováděna postupně na několika strojích • Operace (i,j): provádění úlohy j na stroji / • pij: trvání operace (/',_/) • Pořadí operací úlohy je předem stanoveno: • (;,_/') —> (/(,y) specifikuje, že úloha y má být prováděna na stoji ; dříve než na stroji k 9 Cíl: rozvrhovat úlohy na strojích • bez překrytí na strojích • bez překrytí v rámci úlohy • minimalizace makespan Cmax tedy jedná se o job shop problém s minimalizací makespan Jm\\Cmax PB165 Grafy a sítě: Úvod k plánování a rozvrhování 34/53 Aplikace: automobilová montážní linka • Rozdílné typy aut na montážní lince • dvou-dveřové kupé, čtyř-dveřový sedan, ... • rozdílné barvy • rozdílné vybavení: automatická vs. manuální převodovka, posuvná střech, ... • Kritická místa (bottlenecks) CL Q. O Cíl » výkon stroje ovlivňuje tempo výroby • např. lakování (změna barvy vyžaduje časově náročné čištění) • maximalizace výkonnosti vhodným seřazením automobilů, • rovnoměrná pracovní zátěž na jednotlivých výrobních místech PB165 Grafy a sítě: Úvod k plánování a rozvrhování 35/53 Příklad: job shop problém Data: • stroje: M1,M2,M3 • úlohy: JI : (3,1) —»■ (2,1) -J2:(l,2)^(3,2) J3:(2,3)^(l,3)- -(1,1) -(3,3) M1-«— ■^------------------------ -M2-S— • doby trvání: p31 = 4, p21 = 2, pil pl2 = 3,p32 = 3 p23 = 2,pl3 = 4,p33 = PB165 Grafy a sítě: Úvod k plánování a rozvrhování -M3 36/53 Příklad: job shop problém Data: • stroje: M1,M2,M3 • úlohy: JI : (3,1) —»■ (2,1) -J2:(l,2)^(3,2) J3:(2,3)^(l,3)- -(1,1) -(3,3) M1-«— ■^------------------------ -M2-S— • doby trvání: p31 = 4, p21 = 2, pil = 1 pl2 = 3,p32 = 3 p23 = 2,pl3 = 4,p33 = 1 Řešení: PB165 Grafy a sítě: Úvod k plánování a rozvrhování ■M3 "T" 10 12 37/53 Disjunktivní grafová reprezentace Graf G = (N,AuB) • uzly odpovídají operacím N = {(i,j)\(i,j) je operace} • konjunktivní hrany A reprezentují pořadí operací úlohy • (;,_/') —> (k,j) G A operace (/,_/') předchází (/c,_/) • disjunktivní hrany ß reprezentují konflikty na strojích • dvě operace (/,_/') a (;', /) jsou spojeny dvěma opačně orientovanými hranami • dva pomocné uzly U a V reprezentující zdroj a stok • hrany z Ľ ke všem prvním operacím úlohy • hrany ze všech posledních operací úlohy do V PB165 Grafy a sítě: Úvod k plánování a rozvrhování 38/53 Výběr hran Pojmy: • Podmnožina D c B je nazývána výběr, jestliže obsahuje z každého páru disjunktivních hran právě jednu • Výběr D je splnitelný, jestliže výsledný orientovaný graf G(D) = (/V, A U D) je acyklický • jedná se o graf s konjunktivními hranami a vybranými diskjunktními hranami Poznámky: • splnitelný výběr určuje posloupnost, ve které jsou operace prováděny na strojích • každý (konzistentní) rozvrh jednoznačně určuje splnitelný výběr • každý splnitelný výběr jednoznačně určuje (konzistentní) rozvrh PB165 Grafy a sítě: Úvod k plánování a rozvrhování 39/53 Příklad: výběr V grafu existuje v důsledku nevhodného výběru hran cyklus: PB165 Grafy a sítě: Úvod k plánování a rozvrhování 40/53 Příklad: výběr V grafu existuje v důsledku nevhodného výběru hran cyklus: • (1,2)^(3,2) • (3,2)^(3,1)^(2,1)^(1,1)^(1,2) => nelze splnit (k tomuto výběru neexistuje rozvrh) PB165 Grafy a sítě: Úvod k plánování a rozvrhování 41/53 Příklad: splnitelný výběr Jakým způsobem nalézt rozvrh pro daný splnitelný výběr? Tedy: jakým způsobem lze nalézt tento odpovídající rozvrh: M1 1 1 | | IVP I I 1 1 M3 I C ) 1 5 1 10 I 15 20 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 42/53 Výpočet rozvrhu pro výběr Metoda: výpočet nejdelších cest z Ľ do dalších uzlů v G(D) Technický popis: • uzly (/',_/) mají ohodnocení p,y, uzel U má ohodnocení 0 • délka cesty /'i, /2,..., ir: součet ohodnocení uzlů /'i, /2,..., ir-\ • spočítej délku l;j nejdelší cesty z Ľ do (/,_/') a V, např. použitím Dijkstrova algoritmu PB165 Grafy a sítě: Úvod k plánování a rozvrhování 43/53 Výpočet rozvrhu pro výběr Metoda: výpočet nejdelších cest z Ľ do dalších uzlů v G(D) Technický popis: • uzly (/',_/) mají ohodnocení p,y, uzel U má ohodnocení 0 • délka cesty /'i, /2,..., ir: součet ohodnocení uzlů /'i, /2,..., ir-\ • spočítej délku l;j nejdelší cesty z Ľ do (/,_/') a V, např. použitím Dijkstrova algoritmu O pro všechny uzly (/,_/') bez předchůdce: /,y = 0 O vypočítej postupně pro všechny zbývající uzly (/,_/') (a pro uzel V): In max J:j = Iki + Pij v(k,iy.(k,i)^(i,j) PB165 Grafy a sítě: Úvod k plánování a rozvrhování 44/53 Výpočet rozvrhu pro výběr Metoda: výpočet nejdelších cest z Ľ do dalších uzlů v G(D) Technický popis: • uzly (/',_/) mají ohodnocení p,y, uzel U má ohodnocení 0 • délka cesty /'i, /2,..., ir: součet ohodnocení uzlů /'i, /2,..., ir-\ • spočítej délku l;j nejdelší cesty z Ľ do (/,_/') a V, např. použitím Dijkstrova algoritmu O pro všechny uzly (/,_/') bez předchůdce: /,y = 0 O vypočítej postupně pro všechny zbývající uzly (/,_/') (a pro uzel V): /;; = max /;; V(M):(M)^(/J) kl + Pij • zahaj operaci (/',_/) v čase /,y • délka nejdelší cesty z (7 do V je rovna makespan • tato cesta je kritická cesta PB165 Grafy a sítě: Úvod k plánování a rozvrhování 45/53 Příklad: výpočet rozvrhu pro výběr Výpočet li 2W 4*s i" uzel I (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka PB165 Grafy a sítě: Úvod k plánování a rozvrhování 46/53 Příklad: výpočet rozvrhu pro výběr Výpočet I;; 4^^ r uzel I (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 Ö Ö PB165 Grafy a sítě: Úvod k plánování a rozvrhování 47/53 Příklad: výpočet rozvrhu pro výběr Výpočet li 2W 4*s i" uzel I (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 0 0 4 4 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 48/53 Příklad: výpočet rozvrhu pro výběr Výpočet li 2W 4*s i" uzel I (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 0 0 4 4 6 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 49/53 Příklad: výpočet rozvrhu pro výběr Výpočet li 2W 4*s i" uzel I (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 0 0 4 4 6 7 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 50/53 Příklad: výpočet rozvrhu pro výběr Výpočet I;; uzel (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 Ö Ö 4 4 6 7 11 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 51/53 Příklad: výpočet rozvrhu pro výběr Výpočet I;; uzel (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 Ö Ö 4 4 6 7 11 12 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 52/53 Konstrukce výběru pro daný rozvrh Nalezněte výběr hran pro daný rozvrh: Konstrukce odpovídajícího výběru: vybereme disjunktivní hrany, které odpovídají uspořádání operací úlohy v rozvrhu PB165 Grafy a sítě: Úvod k plánování a rozvrhování 53/53