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/31 Grafy a site v plánování a rozvrhování: osnova i Problém rozvrhování: vlastnosti stroje, omezení, optimalizace Q Precedenční omezení a disjunktivní grafová reprezentace: korespondence mezi rozvrhem a grafem Q Plánování projektu (precedenční omezení): kritická cesta, kompromisní heuristika « Barvení grafu: algoritmus saturace a problémy přiřazení místností, rezervační problém, plánování operátorů 5 Hranově ohodnocené grafy: obchodní cestující, doba na dopravu, plánování na počítačových sítích e Plánování s komunikací a s precedencemi: plánování seznamem, heuristiky mapování, shlukovací heuristiky 9 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/31 Rozvrhování a plánování (scheduling) o Zdroj/stroj <» kapacita • dostupnost v čase » rychlost o Úloha/aktivita • nejdřívější startovní čas • nej pozdější koncový čas » doba trvání (na referenčním zdroji) o počet zdrojů • alternativní zdroje • Rozvrhování o 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/31 Príklad: rozvrhování s precedencemi 9 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 2© 2© 1 / \l 1 2 1/ \1 )—(7) Í1W2W4T h<5V - t. ^-i 3.stroj 2.stroj Open snop Um • multi-operační problém s m stroji (žádné nové vlastnosti) Job shop Jm a 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 9 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í 9/31 Omezení ß Precedenční podmínky • ú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, přec Vhodnost stroje Mj podmnožina strojů Mj, na níž lze provádět úlohu j o 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í 10/31 Omezení ß Směrovací (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 » 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í 11/31 Omezení ß Doprava a komunikace tju, tki, 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 o 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í 12/31 Optimalizace: makespan 7 o Maximální čas konce úloh (makespan) Cmax = max(G,..., Cn) o Příklad: Cmax = max{l, 3,4,5,8,7, 9} = 9 Zdroj 2 | 2 | | 6 | Zdroj 1 [71 3 [71 5 IT i—i—i—i—i—i—i—i—i—r • Cíl: minimalizace makespan často o 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 2 6 5 1 3 4 7 Zdroj 2| Zdroj 1 i—i—i—i—i—i—i—i—i—r • Velmi často používané kritérium PB165 Grafy a sítě: Úvod k plánování a rozvrhování cas 13/31 Optimalizace: zpoždění 7 • Zpoždění (lateness) úlohy j: Lj = Cj — dj 9 Cíl: minimalizace zpoždění max(/.!,...,/.„) 9 Příklad: 1 3 2 I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—I—»-0 5 10 15 t í t tlj Clo Cir^ 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ánování a rozvrhování 14/31 Optimalizace: nezáporné zpoždění 7 • Nezáporné zpoždění (tardiness) úlohy j: Tj = max(Cý — dj,0) o Cíl: minimalizace celkového zpoždění n YjTj celkové zpoždění úloh 1 3 2 9 Příklad: I-----1-----1-----1-----1-----1-----1-----1-----1-----1-----1-----1-----1-----1-----1-----1-----M»- 0 5 10 15 í t í tlj Clo Cir^ 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ánování a rozvrhování 15/31 Termín dokončení a grafy Lateness Pozdě nebo ne U; PB165 Grafy a sítě: Úvod k plánovaní a rozvrhování 7 Tardiness V praxi 3 16/31 Prí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 ry 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 o 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í 17/31 Úvod k plánování a rozvrhován I Terminologie a klasifikace o Úvod o Vlastnosti stroje o Omezení o Optimalizace o 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í 18/31 Precedencní 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, o Orientovaný acyklický vrcholově ohodnocený graf o uzly reprezentují úlohy a hrany reprezentují precedencní 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í 19/31 Úloha jako obdélník • Úloha jako uzel lze převést na úloha jako obdélník úloha j úloha k o 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 rr[ ŕ cas PB165 Grafy a sítě: Úvod k plánování a rozvrhování 20/31 Precedencní omezení: aplikace 9 Příklad: zprostředkování, instalace a testování rozsáhlého počítačového systému • projekt zahrnuje o evaluace a výběr hardware, vývoj software, nábor a školení lidí, testování a ladění systému, ... • precedencní 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 • Obecně: problémy plánování projektu • příští přednáška o Rozšíření: 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ě: Úvod k plánování a rozvrhování 21/31 Disjunktivní grafová reprezentace a multi-operační rozvrhování o 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 / 9 pij: trvání operace (/',_/) o 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 o Cíl: rozvrhovat úlohy na strojích • bez překrytí na strojích o 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í 22/31 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í 23/31 Příklad: job shop problém Data: • stroje: M1,M2,M3 • úlohy: JI: (3,1)^(2,1) -v (1,1) J2:(l,2)^(3,2) J3: (2, 3) ^(1,3) ^(3, 3) M1-«— -M2<- • doby trvání: p31 = 4, p21 = 2, pil = 1 pl2 = 3,p32 = 3 p23 = 2,pl3 = 4,p33 = 1 Řešení: M1 PB165 Grafy a sítě: Úvod k plánování a rozvrhování M3 10 12 24/31 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 o dvě operace (/,_/') a (;', /) jsou spojeny dvěma opačně orientovanými hranami • dva pomocné uzly U a V reprezentující zdroj a stok o hrany z Ľ ke všem prvním operacím úlohy a hrany ze všech posledních operací úlohy do V PB165 Grafy a sítě: Úvod k plánování a rozvrhování 25/31 Výber 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ý o 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 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ě: Úvod k plánování a rozvrhování 26/31 Príklad: nesplnitelný výber V grafu existuje v důsledku nevhodného výběru hran cyklus: o (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ánovaní a rozvrhování 27/31 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[ (T "¥ ~¥ 20 PB165 Grafy a sítě: Úvod k plánování a rozvrhování 28/31 Výpočet rozvrhu pro výber 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,..., /r-i • spočítej délku l;j nejdelší cesty z Ľ do (/,_/') a V, např. použitím Dijkstrova algoritmu Q pro všechny uzly (/,_/') bez předchůdce: l;j = 0 © vypočítej postupně pro všechny zbývající uzly (/,_/') (a pro uzel V): lij = max lij = lk, + pij v(k,iy.(k,i)^(i,j) o zahaj operaci (/',_/) v čase /,y • délka nejdelší cesty z 1/ do V je rovna makespan o tato cesta je kritická cesta PB165 Grafy a sítě: Úvod k plánování a rozvrhování Príklad: výpočet rozvrhu pro výber Výpočet l;j 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í 30/31 Konstrukce výberu pro daný rozvrh Nalezněte výběr hran pro daný rozvrh: M1 M2 M3 □ 0 10 12 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ě: Úvod k plánování a rozvrhování 31/31