Terminologie a klasifikace oooooooooooooo Grafová reprezentace (l.část) 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 Terminologie a klasifikace oooooooooooooo Plánování a rozvrhování l; Terminologie a klasifikace » Úvod • Vlastnosti stroje 9 Omezení • Optimalizace 2 Grafová reprezentace (l.část) » Precedenční omezení Disjunktivní grafová reprezentace PB165 Grafy a sítě: 5. Plánování a rozvrhování Grafová reprezentace (l.část) oooooooooooooo 2/31 Terminologie a klasifikace •ooooooooooooo Úvod Grafová reprezentace (l.čast) oooooooooooooo Rozvrhování a plánování (scheduling) 9 Rozvrhování 9 optimální alokace/přiřazení zdrojů v čase množině úloh omezené množství zdrojů a maximalizace zisku za daných omezení o Zdroj 9 kapacita —-,—,,„ , ,„„,, ^„, ?„„, —^. o dostupnost v čase 9 rychlost — QQQQQQQQQ! L ■■■■■:i]nn:n:: o Úloha 9 nejdřívější startovní čas 9 nej pozdější koncový čas 9 doba trvání (ref. zdroj) o počet zdrojů 9 alternativní zdroje PB165 Grafy a sítě: 5. Plánování a rozvrhování Visopt ShopFloor System 3/31 Terminologie a klasifikace o»oooooooooooo Grafová reprezentace (l.část) oooooooooooooo Příklad o Rozvrhování 7 úloh na 2 zdrojích » doba trvání úlohy + precedenční podmínky o nalezení rozvrhu tak, aby se minimalizovala doba nutná na realizaci všech úloh kritická cesta o Možný rozvrh a na kritické (nejdelší) cestě nesmí vzniknout zdržení Zdroj 2 6 Zdroj 113 4 5 7 PB165 Grafy a sítě: 5. Plánování a roz 4/31 Terminologie a klasifikace Grafová reprezentace (l.část) 00*00000000000 oooooooooooooo Úvod Úlohy, stroje » Stroje (zdroje, prostředky) i = 1,..., m a Úlohy (aktivity) j = 1,..., n 9 (i, j) operace nebo provádění úlohy j na stroji / • Statické parametry úlohy doba trvání p\ypy doba provádění úlohy y na stroji i t termín dostupnosti j (release date) ry. nejdřívějsí čas, ve kterém může být úloha j prováděna o 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 j relativně vzhledem k ostatním úlohám v systému » Dynamické parametry úlohy o čas startu úlohy (start time) S;ySy. čas, kdy začne provádění úlohy j na stroji i a č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áni a rozvrhováni 5/31 Terminologie a klasifikace ooo»oooooooooo Grafová reprezentace (l.část) oooooooooooooo Úvod Grahamova klasifikace Grahamova klasifikace a|/?|7 používá se pro popis rozvrhovacích problémů a: charakteristiky stroje » popisuje způsob alokace úloh na stroje a ß: 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áni a rozvrhováni 6/31 Grafová reprezentace (l.část) oooooooooooooo Terminologie a klasifikace oooo»ooooooooo Vlastnosti stroje Vlastnosti stroje » 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ů Paralelní stroje s různou rychlostí Qm » příklad: několik počítačů s různou rychlostí procesoru a Nezávislé paralelní stroje s různou rychlostí Rm 9 stroje mají různou rychlost pro různé úlohy 9 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í a Terminologie a klasifikace Grafová reprezentace (l.část) ooooo«oooooooo oooooooooooooo Vlastnosti stroje Multi-operační (shop) problémy a 9 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: Q-*Q-»Q-*Q 3.síroj " 2. stroj • 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 o 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ů o př. automobilová výrobní linka PB165 Grafy a sítě: 5. Plánování a rozvrhování 8/31 Terminologie a klasifikace Grafová reprezentace (l.část) oooooo»ooooooo oooooooooooooo Omezení Omezení ß 9 Precedenční podmínky přec a úloha může být prováděna až po skončení další(ch) úloh »v o Vhodnost stroje Mj a podmnožina strojů Mj, na níž lze provádět úlohu j a 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ě: 5. Plánování a rozvrhování 9/31 Terminologie a klasifikace ooooooo«oooooo Grafová reprezentace (l.část) oooooooooooooo Omezení ß o Omezení na pracovní sílu l/l// o 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ě / a př. hw zařízení (mikroskop) dostupné pouze pro jednu úlohu -o-o PB165 Grafy a sítě: 5. Plánování a rozvrhování 10/31 Terminologie a klasifikace oooooooo»ooooo Grafová reprezentace (l.část) oooooooooooooo Omezení ß o Smerovací (routing) omezení o 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 o 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 Terminologie a klasifikace Grafová reprezentace (l.část) ooooooooo«oooo oooooooooooooo Omezení Omezení ß 9 Nastavovací (setup) doba a cena S/,7c,s/A: Cjjk,Cjk o závislé na posloupnosti provádění o s-,jk čas nutný pro provádění úlohy k po úloze j na stroji ; a Cjjk 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 Terminologie a klasifikace oooooooooo»ooo Grafová reprezentace (l.část) oooooooooooooo Omezení ß 9 Doprava a komunikace tjki,tki,tj 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 » doba nutná na přepravu mezi dvěma zařízeními a 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 Terminologie a klasifikace Grafová reprezentace (l.část) ooooooooooo«oo oooooooooooooo Optimalizace Optimalizace: makespan 7 9 Maximální cas konce úloh (makespan) Cmax = max(Ci,..., C„) 9 Minimalizace makespan často o maximalizuje výkon (throughput) » zajišťuje rovnoměrné zatížení strojů (load balancing) o Velmi často používané kritérium PB165 Grafy a sítě: 5. Plánování a rozvrhování 14/31 Terminologie a klasifikace Grafová reprezentace (l.část) oooooooooooo»o oooooooooooooo Optimalizace Optimalizace: termín dokončení dj 7 » Zpoždění (lateness) Lj = Cj — dj 9 Minimalizace lateness Lmax = max(/.i,...,/.n) 9 Nezáporné zpoždění (tardiness) Tj = max(C; — dj,0) o Minimalizace maximální tardiness n YjTj celkové zpoždění úloh o 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 klasifikace ooooooooooooo» Optimalizace Termín dokončení a grafy Lateness Pozdě nebo ne Ui dj PB165 Grafy a sítě: 5. Plánování a rozvrhování Grafová reprezentace (l.část) oooooooooooooo Tardiness V praxi 7 Terminologie a klasifikace oooooooooooooo Úvod Vlastnosti stroje Omezení Optimalizace 2 Grafová reprezentace (l.část) 9 Precedenční omezení Disjunktivní grafová reprezentace PB165 Grafy a sítě: 5. Plánování a rozvrhování Grafová reprezentace (l.část) oooooooooooooo 17/31 Terminologie a klasifikace oooooooooooooo Precedenční omezení Grafová reprezentace (l.část) •ooooooooooooo Precedenční omezení 9 Úloha může být prováděna až po skončení další(ch) úloh a úloha a před úlohou b: a —> b : Sa + pa < St, o 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 Giafy a &ilb 3 5. Plďnouď 4,5 ní a lo^viliouďní Terminologie a klasifikace oooooooooooooo Precedenční omezení Grafová reprezentace (l.část) o»oooooooooooo Úloha jako obdélník a Úloha jako uzel lze převést na úloha jako obdélník úloha i 1 úloha k o Horizontální strany obdélníku použity jako časové osy odpovídající době provádění úlohy ,, zdroje xí Ä I I cas —>■ PB165 Grafy a sítě: 5. Plánování a rozvrhování 19/31 Terminologie a klasifikace oooooooooooooo Precedenční omezení Montáž kola Grafová reprezentace (l.část) oo»ooooooooooo 3 pracovníci » Každá úloha má určenou dobu trvání » Precedenční podmínky » Nepreemtivní (úlohy nelze přerušit) Optimální přiřazení úloh PB165 Grafy a sítě: 5. PI 5 7 14 16 24 T2j7 1] 1 T, | T, T7 -| ItJtJtJ T,„ R71 r T, | T, I 1 T1 | T, | T, | |t4| Tfi |tr| T3 N To I Tm 1 32 20/31 Terminologie a klasifikace Grafová reprezentace (l.část) oooooooooooooo ooo»oooooooooo Precedenční omezení Precedenční omezení: aplikace Zprostředkování, instalace a testování rozsáhlého počítačového systému o projekt zahrnuje a evaluace a výběr hardware, vývoj software, nábor a školení lidí, testování a ladění systému, ... precedenční vztahy a některé úlohy mohou být prováděny paralelně a úloha musí být realizována až po dokončení jiných úloh a cíl: minimalizovat čas na realizaci celého projektu o Obecně: problémy plánování projektu a Plánování workflows O orientovaný acyklický graf pro provádění úloh na počítačové síti 9 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 klasifikace oooooooooooooo Grafová reprezentace (l.část) oooo»ooooooooo Disjunktivní grafová reprezentace Disjunktivní grafová reprezentace a multi-operační rozvrhování a n úloh » m strojů o Jedna úloha je prováděna postupně na několika strojích » Operace (/,/): provádění úlohy j na stroji i 9 Pořadí operací úlohy je stanoveno: (i,j) —> {k,j) specifikuje, že úloha j má být prováděna na stoji / dříve než na stroji k o pij: trvání operace (/,_/) o Cíl: rozvrhovat úlohy na strojích » bez překrytí na strojích o bez překrytí v rámci úlohy a minimalizace makespan Cmax PB165 Grafy a sítě: 5. Plánování a rozvrhování 22/31 Terminologie a klasifikace Grafová reprezentace (l.část) oooooooooooooo ooooo«oooooooo Disjunktivní grafová reprezentace Aplikace: automobilová montážní linka o Rozdílné typy aut na montážní lince 8 dvou-dveřové kupé, čtyř-dveřový sedan, ... a rozdílné barvy a rozdílné vybavení: automatická vs. manuální převodovka, posuvná střech, ... Kritická místa (bottlenecks) C> Q O Ô a výkon stroje ovlivňuje tempo výroby a např. lakování (změna barvy vyžaduje časově náročné čištění) 9 Cíl a maximalizace výkonnosti vhodným seřazením automobilů, a 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 klasifikace oooooooooooooo Disjunktivní grafová reprezentace Príklad: job shop problém Data: stroje: M1,M2,M3 úlohy: JI : (3,1) — (2,1)- -(1,1) J2: (1,2) -(3,2) J3:(2,3)-(l,3)- -(3,3) M1-«---------- •^------------ -M2-S- • doby trvání: p31 = 4, p21 = 2, pil pl2 = 3,p32 = 3 p23 = 2,pl3 = 4,p33 = Řešení: M1 : 5. Plánckraní a rozvrhování O Grafová reprezentace (l.část) oooooo»ooooooo ■M3 10 12 24/31 Terminologie a klasifikace oooooooooooooo Disjunktivní grafová reprezentace Grafová reprezentace (l.část) ooooooo«oooooo Disjunktivní grafová reprezentace Graf G = {N,AuB) 9 uzly odpovídají operacím N = {(i,j)\(i,j) je operace} » konjunktivní hrany A reprezentují pořadí operací úlohy (/,/) -> (kj) e A ^=> operace (ij) předchází (kj) o disjunktivní hrany B reprezentují konflikty na strojích o dvě operace (/,_/') a (/', /) jsou spojeny dvěma opačně orientovanými hranami 9 dva pomocné uzly U a V reprezentující zdroj a stok o hrany z U ke všem prvním operacím úlohy o hrany ze všech posledních operací úlohy do V PB165 Grafy a sítě: 5. Plánoval 25/31 Terminologie a klasifikace Grafová reprezentace (l.část) oooooooooooooo oooooooo»ooooo Disjunktivní grafová reprezentace Výběr hran Pojmy: 9 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 9 Výběr D je splnitelný, jestliže výsledný orientovaný graf G(D) = (A/, A U D) je acyklický o jedná se o graf s konjunktivními hranami a vybranými diskjunktními hranami Poznámky: o splnitelný výběr určuje posloupnost, ve které jsou operace prováděny na strojích o každý (konzistentní) rozvrh jednoznačně určuje splnitelný výběr o 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 Grafová reprezentace (l.část) oooooooooooooo ooooooooo«oooo Disjunktivní grafová reprezentace Příklad: nesplnitelný 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ě: 5. Plánování a rozvrhování 27/31 Terminologie a klasifikace oooooooooooooo Disjunktivní grafová reprezentace Grafová reprezentace (l.část) oooooooooo»ooo Príklad: splnitelný výber 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 Grafy"a sítě: 5. Plánování a rozvrhování ~r~ 10 Terminologie a klasifikace oooooooooooooo Grafová reprezentace (l.část) ooooooooooo«oo Disjunktivní grafová reprezentace 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: o uzly (/",_/) mají ohodnocení p,y, uzel U má ohodnocení 0 délka cesty /'i, /'a,..., i/- součet ohodnocení uzlů /'i, /2,..., /r-i » spočítej délku l;j nejdelší cesty z Ľ do (/,_/') a V a např. použitím Dijkstrova algoritmu o zahaj operaci (i,j) v čase /,y o 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 Terminologie a klasifikace oooooooooooooo Disjunktivní grafová reprezentace Výpočet rozvrhu pro výber Grafová reprezentace (l.část) 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 Terminologie a klasifikace oooooooooooooo Disjunktivní grafová reprezentace Grafová reprezentace (l.část) ooooooooooooo» Príklad: výber pro daný rozvrh Nalezněte výběr hran pro daný rozvrh: Konstrukce odpovídajícího výberu: 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