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/34
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/34
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/34
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í 4/34
Ú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í 5/34
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í 6/34
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í 7/34
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í 8/34
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í 9/34
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í 10/34
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í 11/34
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í 12/34
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í 13/34
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í 14/34
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í 15/34
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í 16/34
Cvičení: optimalizační kritéria a sekvenční úlohy
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í 17/34
Cvičení: optimalizační kritéria a paralelní úlohy
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
Stroj 1&2 1 2 1&2 1 1&2
Čas startu úlohy 0 10 1 12 3 8
Váha úlohy 1 2 1 2 1 3
Doba trvání 1 2 4 3 5 2
Termín dokončení 4 13 3 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í 18/34
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í 19/34
Ú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í 20/34
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í 21/34
Ú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í 22/34
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í 23/34
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í 24/34
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í 25/34
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)
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í 26/34
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í 27/34
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í 28/34
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í 29/34
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í 30/34
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í 31/34
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í 32/34
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í 33/34
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í 34/34