Grafová reprezentaci OOOOOOOOOOOOOO PB165 Grafy a sítě: 5. Plánování a rozvrhování PB165 Grafy a sítě: 5. Plánování a rozvrhování 1/31 erminologie a klasifika oooooooooooooo Plánování a ro: zvrhování Q Terminologie a klasifikace • Úvod • Vlastnosti stroje • Omezení • Optimalizace O Grafová reprezentace (l.část) • Precedenční omezení 9 Disjunktivní grafová reprezentace PB165 Grafy a sítě: 5. Plánování a rozvrhování Grafová reprezentaci OOOOOOOOOOOOOO 2/31 Rozvrhování a plánování (scheduling • Rozvrhování • optimální alokace/přiřazení zdrojů v čase množině úloh 9 omezené množství zdrojů • maximalizace zisku za daných omezení • Zdroj • kapacita —^—,... , ,,...., ^ , ?...., -^r • dostupnost v čase ____ • rychlost • Úloha • nejdřívější startovní čas • nej pozdější koncový čas • doba trvání (ref. zdroj) » počet zdrojů • alternativní zdroje PB165 Grafy a sítě: 5. Plánování a rozvrhování — Visopt ShopFloor System 3/31 Terminologie a klasifika o«oooooooooooo Grafová reprezentaci OOOOOOOOOOOOOO Příklad • 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Í6 1 1 2 1 / N^1 "\ Y S" '3 s 3 , \3 J kritická cesta • Možný rozvrh • na kritické (nejdelší) cestě nesmí vzniknout zdržení Zdroj 2 2 6 Zdroj 113 4 5 7 I I I I I I I I I v PB165 Grafy a sítě: 5. Plánování a rozvrhování 4/31 • Stroje (zdroje, prostředky) ; = 1,..., m • Úlohy (aktivity) j = 1,..., n • (i, j) operace nebo provádění úlohy j na stroji / • Statické parametry úlohy • doba trvání p\y py doba provádění úlohy j na stroji / • termín dostupnosti j (release date) ry. 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 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;j,Sj: čas, kdy začne provádění úlohy y na stroji ; • č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ě: 5. Plánování a rozvrhováni 5/31 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://www.mathematik.uni-osnabrueck.de/research/OR/class/ • složitost a algoritmy pro jednotlivé rozvrhovací problémy PB165 Grafy a sítě: 5. Plánování a rozvrhování 6/31 Terminologie a klasifikace oooo»ooooooooo Grafová reprezentace (l.cast) OOOOOOOOOOOOOO Vlastnosti stroje Vlastnosti stroje a Jeden stroj 1: 1| • Identické paralelní stroje Pm • m strojů (zapojených paralelně) • úloha j je jedna operace a ta může být prováděna na libovolném z m strojů _^ ^ ^ ^ p3 -o --0-00-0 • Paralelní stroje s různou rychlostí Qm • 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 • příklad: vektorový počítač počítá vektorové úlohy rychleji než klasické PC PB165 Grafy a sítě: 5. Plánování a rozvrhování ooooo«oooooooo Grafová reprezentaci OOOOOOOOOOOOOO lulti-operač. stroj Multi-operační (shop) problémy • jedna úloha je prováděna postupně na několika strojích • lze říci, že úloha se skládá z několika operací 1.stroj 4.stroj příklad: úloha se 4 operacemi: \^J~^\_J~^\_)~~*\_.) 3^íroj 2. str Job shop Jm • m strojů • úloha musí být prováděna na všech strojích • každá úloha má předem definované pořadí, ve kterém je prováděna na jednotlivých strojích Multi-operační problémy jsou klasické detailně studované problémy operačního výzkumu • reálné problémy mnohem komplikovanější o 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ě: 5. Plánování a roz oooooo»ooooooo Grafová reprezentaci OOOOOOOOOOOOOO Omezení • Precedenční podmínky přec • úloha může být prováděna až po skončení další(ch) úloh • Vhodnost stroje • 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 M; PB165 Grafy a sítě: 5. Plánování a rozvrhování 9/31 • Omezení na pracovní sílu l/l// » stroje mohou potřebovat operátory a úlohy lze provádět pouze pokud jsou dostupní 1/1/ operátorů • mohou existovat různé skupiny operátorů se specifickou kvalifikací l/l// je počet operátorů ve skupině / • př. hw zařízení (mikroskop) dostupné pouze pro jednu úlohu PB165 Grafy a sítě: 5. Plánování a rozvrhování 10/31 • 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 \ PB165 Grafy a sítě: 5. Plánování a rozvrhování 11/31 ooooooooo«o Grafová reprezentaci OOOOOOOOOOOOOO Omezení • Nastavovací (setup) doba a cena • závislé na posloupnosti provádění Syk i Sjk C'ijk i Cjk • Sijk čas nutný pro provádění úlohy k po úloze j na stroji ; • cijk cena nutná ... • sjk,Cjk nastavovací doba a cena nezávislá na stroji a příklad: plnění limonád do lahví PB165 Grafy a sítě: 5. Plánování a rozvrhování 12/31 oooooooooo» Grafová reprezentaci OOOOOOOOOOOOOO Omezení • Doprava a komunikace tjkhtkhtj • tyt 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 • doba nutná na přepravu mezi dvěma zařízeními • omezení na množství a možnou dobu přepravy • propustnost linky a vzdálenost uzlů v počítačové síti tki dáno vzdáleností uzlů v síti/grafu: PB165 Grafy a sítě: 5. Plánování a rozvrhování 13/31 • Maximální čas konce úloh (makespan) Cmax = max(Ci,..., Cn) o Minimalizace makespan často • maximalizuje výkon (throughput) • zajišťuje rovnoměrné zatížení strojů (load balancing) • Velmi často používané kritérium PB165 Grafy a sítě: 5. Plánování a rozvrhování 14/31 • Zpoždění (lateness) Lj = Cj — dj • Minimalizace lateness Lmax = max(Li ,...,/.„) • Nezáporné zpoždění (tardiness) Tj = max(C; — dj, 0) a Minimalizace maximální tardiness n YjTj celkové zpoždění úloh • Minimalizace maximální vážené tardiness n \JwjTj vážené zpoždění úloh j=l PB165 Grafy a sítě: 5. Plánování a rozvrhování 15/31 terminologie a klasifika ooooooooooooo« Termín dokoi Lateness Pozdě nebo ne Ui dj PB165 Grafy a sítě: 5. Plánování a rozvrhování Tardiness V praxi 16/31 Q Grafová reprezentace (l.část) • Precedenční omezení • Disjunktivní grafová reprezentace PB165 Grafy a sítě: 5. Plánování a rozvrhování Grafová reprezentaci OOOOOOOOOOOOOO 17/31 oooooooooooooo Grafová reprezentace (l.cast) •OOOOOOOOOOOOO 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 < St, • Orientovaný acyklický vrcholově ohodnocený graf • uzly reprezentují úlohy • hrany reprezentují precedenční podmínky • ohodnocení vrcholu reprezentuje doba 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 braiy a site D. Mánova x£V©r©3 18/31 I erminologie a klasi oooooooooooooo Grafová reprezentaci O0OOOOOOOOOOOO Ú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 zdroje -X5 Ä I I cas —*• PB165 Grafy a sítě: 5. Plánování a rozvrhování 19/31 Terminologie a klasifika oooooooooooooo Grafová reprezentaci 00*00000000000 Montáž kola 9 3 pracovníci a Každá úloha má určenou dobu trvání • Precedenční podmínky • Nepreemtivní (úlohy nelze přerušit) T2)J 1J GCC© ©:, I T, | T? T7 I Prirazení úloh ItJtJtJ Tm ~~| H71 r T1 I T, | I T1 | T„ I T7 | Optimální přiřazení úloh ItJ Tfi lid T* I Tal TQ | Tm I 2 5 7 14 16 24 32 (SMls) CTiU PB165 Grafy a sítě: 5. P 20/31 oooooooooooooo Precedenční OOO0OOOOOOOOOO mämmmsm • 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 • Obecně: problémy plánování projektu • Plánování workflows O orientovaný acyklický graf pro provádění úloh na počítačové síti Q obecné rozšíření: cyklické grafy + podmínky vyhodnocení cyklů PB165 Grafy a sítě: 5. Plánování a rozvrhování 21/31 Terminologie a klasifika oooooooooooooo Grafová reprezentaci OOOOOOOOOOOOOO Disjunktivní grafov multi-operační rozvrhování • n úloh • m strojů 9 Jedna úloha je prováděna postupně na několika strojích • Operace (i, j): provádění úlohy j na stroji / • Pořadí operací úlohy je stanoveno: » (/, j) —> (Ir,j) specifikuje, že úloha j má být prováděna na stoji / dříve než na stroji k • p/f trvání operace (/',/) • Cíl: rozvrhovat úlohy na strojích • bez překrytí na strojích • bez překrytí v rámci úlohy • minimalizace makespan Cmax PB165 Grafy a sítě: 5. Plánování a rozvrhování 22/31 • 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) 9 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ě: 5. Plánování a rozvrhování 23/31 terminologie a klasí oooooooooooooo afová reprezenta Příklad: job shop pi Grafová reprezentaci OOOOOOOOOOOOOO Data: • stroje: Ml , M2, M3 • úlohy: JI : (3,1)- (2,1)- -(1,1) J2 (1,2)- ►(3,2) J3 (2,3)-Mť ►(M)- -(3,3) <---------- -M2-6------------ • doby trvání: p31 = 4, p21 = 2, pil = 1 pl2 = 3,p32 = 3 p23 = 2,pl3 = 4,p33 = 1 Řešení: M1 M3 : 5. Plánovaní a rozvrhování Terminologie a klasifika oooooooooooooo Grafová reprezentace (l.část) OOOOOOOOOOOOOO afová reprezenta Disjunktivní grafov; ■ItlITIIIIflT Graf G = (N,Al)B) • uzly odpovídají operacím N = {(i,j)\(i,j) je operace} • konjunktivní hrany A reprezentují pořadí operací úlohy • (ij) -> (k,j) e A <=4> operace (i,j) předchází (kj) • disjunktivní hrany B 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 9 hrany z U ke všem prvním operacím úlohy • hrany ze všech posledních operací úlohy do V PB165 Grafy a sítě: 5. Plánoval 25/31 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) = (A/, 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ě: 5. Plánování a rozvrhování 26/31 terminologie a klasifikace oooooooooooooo Disjunktivní grafová reprezenta Příklad: Grafová reprezentaci OOOOOOOOOÄOOOO 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ě: 5. Plánování a rozvrhování 27/31 I erminologie a klasi oooooooooooooo Grafová reprezentaci OOOOOOOOOOOOOO Příklad: splnitelný 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 M2 M3 PB165 Grafý"a sítě: 5. Plánování a rozvrhování ~r~ 10 ~r~ 15 20 28/31 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 k, i%,..., ir: součet ohodnocení uzlů h, /2, • • •, V-i • spočítej délku l;j nejdelší cesty z Ľ do (/,/) a V • např. použitím Dijkstrova algoritmu • zahaj operaci (/',_/) v čase /,y • délka nejdelší cesty z Ľ do V je rovna makespan • tato cesta je kritická cesta PB165 Grafy a sítě: 5. Plánování a rozvrhování 29/31 oooooooooooooo afová reprezenta Výpočet rozvrhu pr, mu Grafová reprezentaci oooooooooooo»o 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 Ö Ö 4 4 6 7 11 12 PB165 Grafy a sítě: 5. Plánování a rozvrhování 30/31 Nalezněte výběr hran pro daný rozvrh: 10 12 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ě: 5. Plánování a rozvrhován 31/31