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/56 Grafy a sítě v plánování a rozvrhování: osnova 1 Problém rozvrhování: vlastnosti stroje, omezení, optimalizace 2 Precedenční omezení a disjunktivní grafová reprezentace: korespondence mezi rozvrhem a grafem 3 Plánování projektu (precedenční omezení): kritická cesta, kompromisní heuristika 4 Barvení grafu: algoritmus saturace, problémy přiřazení místností, rezervační problém, plánování operátorů 5 Plánování na počítačové sítí: Transport: doba na dopravu, doba na nastavení Plánování datových přenosů Paralelní úlohy s komunikací Plánování s komunikací a s precedencemi: plánování seznamem, heuristiky mapování, shlukovací heuristiky Rozvrhování na FI: PA167 Rozvrhování, PA163 Omezující podmínky PB165 Grafy a sítě: Úvod k plánování a rozvrhování 2/56 Rozvrhování a plánování (scheduling) Visopt ShopFloor System Zdroj/stroj kapacita dostupnost v čase rychlost Úloha/aktivita nejdřívější startovní čas nejpozdě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í PB165 Grafy a sítě: Úvod k plánování a rozvrhování 3/56 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 1 11 2 3 2 3 1 2 4 6 3 5 7 1 11 2 3 2 3 1 2 4 6 3 5 7 kritická cesta PB165 Grafy a sítě: Úvod k plánování a rozvrhování 4/56 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 1 11 2 3 2 3 1 2 4 6 3 5 7 1 11 2 3 2 3 1 2 4 6 3 5 7 kritická cesta Možný rozvrh na kritické (nejdelší) cestě nesmí vzniknout zdržení 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas PB165 Grafy a sítě: Úvod k plánování a rozvrhování 5/56 Úlohy, stroje Stroje i = 1, . . . , m Úlohy j = 1, . . . , n 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas Sekvenční úloha úloha je zpracovávána na jednom stroji př. 7 úloh na 2 strojích PB165 Grafy a sítě: Úvod k plánování a rozvrhování 6/56 Úlohy, stroje Stroje i = 1, . . . , m Úlohy j = 1, . . . , n 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas Sekvenční úloha úloha je zpracovávána na jednom stroji př. 7 úloh na 2 strojích cas Zdroj 2 Zdroj 1 3 4 1 2 Paralelní úloha úloha je zpracovávána na několika strojích všechny operace úlohy zpracovávány zároveň úlohy 1 a 2 jsou paralelní, úlohy 3 a 4 jsou sekvenční PB165 Grafy a sítě: Úvod k plánování a rozvrhování 7/56 Úlohy, stroje Stroje i = 1, . . . , m Úlohy j = 1, . . . , n 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas Sekvenční úloha úloha je zpracovávána na jednom stroji př. 7 úloh na 2 strojích cas Zdroj 2 Zdroj 1 3 4 1 2 Paralelní úloha úloha je zpracovávána na několika strojích všechny operace úlohy zpracovávány zároveň úlohy 1 a 2 jsou paralelní, úlohy 3 a 4 jsou sekvenční Operace (i, j) nebo provádění úlohy j na stroji i úloha se může skládat z několika operací typicky: operace úlohy zpracovány na strojích postupně bez překrytí př. úloha 1 s operacemi (1,1), (2,1) úloha 2 s operacemi (1,2), (2,2) úloha 3 s operací (1,3) cas Zdroj 1 Zdroj 2 (1,1) (1,2) (2,1)(2,2) (1,3) PB165 Grafy a sítě: Úvod k plánování a rozvrhování 8/56 Parametry úlohy Statické parametry úlohy doba trvání pj (pij ): doba provádění úlohy j (na stroji i) termín dostupnosti j (release date) rj : nejdřívější čas, ve kterém může být úloha j prováděna termín dokončení (due date) dj : čas, do kdy musí být úloha j nejpozději dokončena váha wj : důležitost úlohy j relativně vzhledem k ostatním úloham v systému PB165 Grafy a sítě: Úvod k plánování a rozvrhování 9/56 Parametry úlohy Statické parametry úlohy doba trvání pj (pij ): doba provádění úlohy j (na stroji i) termín dostupnosti j (release date) rj : nejdřívější čas, ve kterém může být úloha j prováděna termín dokončení (due date) dj : čas, do kdy musí být úloha j nejpozději dokončena váha wj : důležitost úlohy j relativně vzhledem k ostatním úloham v systému Dynamické parametry úlohy čas startu úlohy (start time) Sj (Sij ): čas, kdy začne provádění úlohy j (na stroji i) čas konce úlohy (completion time) Cj (Cij ): čas, kdy je dokončeno provádění úlohy j (na stroji i) PB165 Grafy a sítě: Úvod k plánování a rozvrhování 10/56 Grahamova klasifikace Grahamova klasifikace α|β|γ používá se pro popis rozvrhovacích problémů α: charakteristiky stroje popisuje způsob alokace úloh na stroje β: charakteristiky úloh popisuje omezení aplikovaná na úlohy γ: optimalizační kritéria PB165 Grafy a sítě: Úvod k plánování a rozvrhování 11/56 Grahamova klasifikace Grahamova klasifikace α|β|γ používá se pro popis rozvrhovacích problémů α: charakteristiky stroje popisuje způsob alokace úloh na stroje β: charakteristiky úloh popisuje omezení aplikovaná na úlohy γ: optimalizační kritéria http://www.informatik.uni-osnabrueck.de/knust/class/ složitost a algoritmy pro jednotlivé rozvrhovací problémy PB165 Grafy a sítě: Úvod k plánování a rozvrhování 12/56 Základní stroje α Jeden stroj 1: 1| . . . | . . . nejjednodušší varianta speciální případ dalších složitějších prostředí stroje 1 11 2 2 3 1 2 4 6 3 5 7 3 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ů 3P PB165 Grafy a sítě: Úvod k plánování a rozvrhování 13/56 Stroje s různou rychlostí α Paralelní stroje s různou rychlostí Qm doba trvání úlohy j na stroji i přímo závislá na jeho rychlosti vi 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í 14/56 Stroje s různou rychlostí α Paralelní stroje s různou rychlostí Qm doba trvání úlohy j na stroji i přímo závislá na jeho rychlosti vi 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 stroj i zpracovává úlohu j rychlostí vij 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í 15/56 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 j je prováděna na stroji i po dobu pij příklad: úloha j se 4 operacemi 1.stroj 3.stroj 4.stroj 2.stroj (1, j), (2, j), (3, j), (4, j) PB165 Grafy a sítě: Úvod k plánování a rozvrhování 16/56 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 j je prováděna na stroji i po dobu pij příklad: úloha j se 4 operacemi 1.stroj 3.stroj 4.stroj 2.stroj (1, j), (2, j), (3, j), (4, j) Open shop Om multi-operační problém s m stroji (žádné nové vlastnosti) Job shop Jm multi-operační problém s m stroji pořadí provádění operací pro každou úlohu je předem určeno (i, j) → (k, j) určuje, že úloha j má být prováděna na stroji i dříve než na stroji k příklad: (2, j) → (1, j) → (3, j) → (4, j) PB165 Grafy a sítě: Úvod k plánování a rozvrhování 17/56 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 j je prováděna na stroji i po dobu pij příklad: úloha j se 4 operacemi 1.stroj 3.stroj 4.stroj 2.stroj (1, j), (2, j), (3, j), (4, j) Open shop Om multi-operační problém s m stroji (žádné nové vlastnosti) Job shop Jm multi-operační problém s m stroji pořadí provádění operací pro každou úlohu je předem určeno (i, j) → (k, j) určuje, že úloha j má být prováděna na stroji i dříve než na stroji k příklad: (2, j) → (1, j) → (3, j) → (4, j) 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í 18/56 Omezení β Precedenční podmínky prec ú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 ≤ Sb Vhodnost stroje Mj podmnožina strojů Mj , na níž lze provádět úlohu j 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í 19/56 Omezení β Doprava a komunikace tjkl , tkl , tj doba nutná na přepravu úlohy j mezi dvěma zařízeními k a l tjkl doba na přepravu ze stroje k na stroj l pro úlohu j tkl 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 tkl dáno vzdáleností uzlů v síti/grafu: PB165 Grafy a sítě: Úvod k plánování a rozvrhování 20/56 Optimalizace: makespan γ Makespan: maximální čas konce úloh Cmax = max(C1, . . . , Cn) Příklad: Cmax = max{1, 3, 4, 5, 8, 7, 9} = 9 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas PB165 Grafy a sítě: Úvod k plánování a rozvrhování 21/56 Optimalizace: makespan γ Makespan: maximální čas konce úloh Cmax = max(C1, . . . , Cn) Příklad: Cmax = max{1, 3, 4, 5, 8, 7, 9} = 9 1 3 2 4 5 6 7Zdroj 1 Zdroj 2 cas Cíl: minimalizace makespan často maximalizuje výkon (throughput) zajišťuje rovnoměrné zatížení strojů (load balancing) příklad: Cmax = max{1, 2, 4, 5, 7, 4, 6} = 7 4 62 5 71 3Zdroj 1 Zdroj 2 cas Velmi často používané základní kritérium PB165 Grafy a sítě: Úvod k plánování a rozvrhování 22/56 Optimalizace: zpoždění γ Zpoždění (lateness) úlohy j: Lj = Cj − dj Maximální zpoždění Lmax = max(L1, . . . , Ln) Cíl: minimalizace maximálního zpoždění Příklad: d1 d3 d2 21 10 1550 3 2 Lmax = max(L1, L2, L3) = = max(C1 − d1, C2 − d2, C3 − d3) = = max(4 − 8, 16 − 14, 10 − 10) = = max(−4, 2, 0) = 2 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 23/56 Optimalizace: nezáporné zpoždění γ Nezáporné zpoždění (tardiness) úlohy j: Tj = max(Cj − dj , 0) Cíl: minimalizace celkového zpoždění n j=1 Tj celkové zpoždění Příklad: d1 d3 d2 21 10 1550 3 2 T1 +T2 +T3 = max(C1 −d1, 0)+max(C2 −d2, 0)+max(C3 −d3, 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ánování a rozvrhování 24/56 Optimalizace: nezáporné zpoždění γ Nezáporné zpoždění (tardiness) úlohy j: Tj = max(Cj − dj , 0) Cíl: minimalizace celkového zpoždění n j=1 Tj celkové zpoždění Příklad: d1 d3 d2 21 10 1550 3 2 T1 +T2 +T3 = max(C1 −d1, 0)+max(C2 −d2, 0)+max(C3 −d3, 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 j=1 wjTj celkové vážené zpoždění PB165 Grafy a sítě: Úvod k plánování a rozvrhování 25/56 Termín dokončení a grafy γ Cj dj Cj dj Cj dj j Tardiness Pozdě nebo ne V praxi T Cj dj j Lateness L Uj PB165 Grafy a sítě: Úvod k plánování a rozvrhování 26/56 Cvičení: optimalizační kritéria Vypočítejte makespan, maximální zpoždění (lateness) a celkové zpoždění (tardiness) a celkové vážené zpoždění pro daný rozvrh. Úloha 1 2 3 4 5 6 Čas startu úlohy 0 10 1 12 5 8 Váha úlohy 1 2 1 1 2 1 Doba trvání 1 2 4 1 3 2 Termín dokončení 4 13 5 14 7 8 Uveďte odpovídající značení i vztahy pro jednotlivá optimalizační kritéria. PB165 Grafy a sítě: Úvod k plánování a rozvrhování 27/56 Příklady rozvrhovacích problému s Grahamovou klasifikací 1|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í 28/56 Příklady rozvrhovacích problému s Grahamovou klasifikací 1|prec|Cmax plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan Pm|rj , Mj | wj Tj 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 wj Tj PB165 Grafy a sítě: Úvod k plánování a rozvrhování 29/56 Příklady rozvrhovacích problému s Grahamovou klasifikací 1|prec|Cmax plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan Pm|rj , Mj | wj Tj 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 wj Tj 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í 30/56 Příklady rozvrhovacích problému s Grahamovou klasifikací 1|prec|Cmax plánování úloh provázaných precedencemi na jednom stroji s cílem minimalizovat makespan Pm|rj , Mj | wj Tj 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 wj Tj 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∞|prec|Cmax 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 Cvičení: navrhněte různé rozvrhovací problémy pomocí Grahamovy klasifikace a popište je PB165 Grafy a sítě: Úvod k plánování a rozvrhování 31/56 Úvod k plánování a rozvrhování 1 Terminologie a klasifikace Úvod Vlastnosti stroje Omezení Optimalizace Příklady 2 Grafová reprezentace pro: Precedenční omezení Disjunktivní grafová reprezentace PB165 Grafy a sítě: Úvod k plánování a rozvrhování 32/56 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 ≤ Sb Orientovaný acyklický vrcholově ohodnocený graf 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 Předchůdci trvání 1 2 – 2 3 1 3 1 1 4 4 2 5 2 3 6 1 4,5 7 3 4,5 21 4 6 3 5 7 1 12 3 4 2 3 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 33/56 Úloha jako obdélník Úloha jako uzel lze převést na úloha jako obdelník uloha j uloha k Horizontální strany obdelníku použity jako časové osy odpovídající době provádění úlohy cas zdroj 3 zdroj 2 zdroj 1 1 3 4 52 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 34/56 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 cenu a čas na realizaci celého projektu čas na realizaci projektu (makespan) lze promítnout do ceny projektu PB165 Grafy a sítě: Úvod k plánování a rozvrhování 35/56 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 cenu a čas na realizaci celého projektu čas na realizaci projektu (makespan) lze promítnout do ceny projektu Obecně: problémy plánování projektu příští přednáška Rozšíření: plánování workflows 1 orientovaný acyklický graf pro provádění úloh na počítačové síti 2 obecné rozšíření: cyklické grafy + podmínky vyhodnocení cyklů PB165 Grafy a sítě: Úvod k plánování a rozvrhování 36/56 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 i pij : trvání operace (i, j) Pořadí operací úlohy je předem stanoveno: (i, j) → (k, j) specifikuje, že úloha j má být prováděna na stoji i dříve než na stroji k 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í 37/56 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) výkon stroje ovlivňuje tempo výroby např. lakování (změna barvy vyžaduje časově náročné čištění) Cíl 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í 38/56 Příklad: job shop problém Data: stroje: M1, M2, M3 úlohy: J1 : (3, 1) → (2, 1) → (1, 1) J2 : (1, 2) → (3, 2) J3 : (2, 3) → (1, 3) → (3, 3) M1 M2 M3 doby trvání: p31 = 4, p21 = 2, p11 = 1 p12 = 3, p32 = 3 p23 = 2, p13 = 4, p33 = 1 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 39/56 Příklad: job shop problém Data: stroje: M1, M2, M3 úlohy: J1 : (3, 1) → (2, 1) → (1, 1) J2 : (1, 2) → (3, 2) J3 : (2, 3) → (1, 3) → (3, 3) M1 M2 M3 doby trvání: p31 = 4, p21 = 2, p11 = 1 p12 = 3, p32 = 3 p23 = 2, p13 = 4, p33 = 1 Řešení: 105 12 M3 M2 M1 0 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 40/56 Disjunktivní grafová reprezentace Graf G = (N, A ∪ B ∪ P) uzly odpovídají operacím N = {(i, j)|(i, j) je operace} ∪ {U, V } dva pomocné uzly U a V reprezentující zdroj a stok konjunktivní hrany A reprezentují pořadí operací úlohy (i, j) → (k, j) ∈ A ⇐⇒ operace (i, j) předchází (k, j) disjunktivní hrany B reprezentují konflikty na strojích dvě operace (i, j) a (i, l) jsou spojeny dvěma opačně orientovanými hranami pomocné hrany P hrany z U ke všem prvním operacím úlohy hrany ze všech posledních operací úlohy do V 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V PB165 Grafy a sítě: Úvod k plánování a rozvrhování 41/56 Výběr hran Pojmy: Podmnožina D ⊂ 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) = (N, A ∪ D ∪ P) je acyklický jedná se o graf s pomocnými, 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í 42/56 Příklad: nesplnitelný výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 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í 43/56 Příklad: nesplnitelný výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 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í 44/56 Příklad: splnitelný výběr Jakým způsobem nalézt rozvrh pro daný splnitelný výběr? 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V Tedy: jakým způsobem lze nalézt tento odpovídající rozvrh: 105 M3 M2 M1 0 15 20 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 45/56 Výpočet rozvrhu pro výběr Metoda: výpočet nejdelších cest z U do dalších uzlů v G(D) Technický popis: uzly (i, j) mají ohodnocení pij , uzel U má ohodnocení 0 délka cesty i1, i2, . . . , ir : součet ohodnocení uzlů i1, i2, . . . , ir−1 spočítej délku lij nejdelší cesty z U do (i, j) a V PB165 Grafy a sítě: Úvod k plánování a rozvrhování 46/56 Výpočet rozvrhu pro výběr Metoda: výpočet nejdelších cest z U do dalších uzlů v G(D) Technický popis: uzly (i, j) mají ohodnocení pij , uzel U má ohodnocení 0 délka cesty i1, i2, . . . , ir : součet ohodnocení uzlů i1, i2, . . . , ir−1 spočítej délku lij nejdelší cesty z U do (i, j) a V 1 lU = 0 a pro každý uzel (i, j) s jediným předchůdcem U: lij = 0 2 vypočítej postupně pro všechny zbývající uzly (i, j) (a pro uzel V): lij = max ∀(k,l):(k,l)→(i,j) (lkl + pkl ) tj. projdeme všechny předchůdce (k, l) uzlu (i, j) délka cesty do (i, j) přes (k, l) je lkl + pkl zahaj operaci (i, j) v čase lij délka nejdelší cesty z U do V je rovna makespan tato cesta je kritická cesta PB165 Grafy a sítě: Úvod k plánování a rozvrhování 47/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (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í 48/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V délka 0 0 0 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 49/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (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í 50/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (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í 51/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (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í 52/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (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 11 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 53/56 Příklad: výpočet rozvrhu pro výběr 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V 2 4 1 124 33 0 0 Výpočet lij : uzel (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 11 12 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 54/56 Konstrukce výběru pro daný rozvrh Nalezněte výběr hran pro daný rozvrh: 105 12 M3 M2 M1 0 Konstrukce odpovídajícího výběru: vybereme disjunktivní hrany, které odpovídají uspořádání operací úlohy v rozvrhu 3,1 2,1 1,1 1,2 3,2 2,3 1,3 3,3 U V PB165 Grafy a sítě: Úvod k plánování a rozvrhování 55/56 Cvičení: job shop Uveďte grafovou reprezentaci pro zadaný job shop problém a ukažte na něm příklad splnitelného výběru a nesplnitelného výběru. Pro Vámi vytvořený splnitelný výběr nalezněte odpovídající rozvrh. Zadání problému je následující: máme 3 stroje máme 3 úlohy s následujícími precedencemi: J1: (2, 1) → (1, 1) → (3, 1) J2: (3, 2) → (2, 2) → (1, 2) J3: (1, 3) → (3, 3), doby trvání operací jsou: p21 = 2, p11 = 4, p31 = 1, p32 = 4, p22 = 2, p12 = 1, p13 = 3, p33 = 3. PB165 Grafy a sítě: Úvod k plánování a rozvrhování 56/56