Úvod do rozvrhování (dokončení)
14. února 2022
1 Klasifikace rozvrhovacích problémů (dokončení)
2 Složitost
Omezení β
Precedenční podmínky prec
lineární posloupnost, stromová struktura
pro úlohy a, b píšeme a → b, což znamená Sa + pa ≤ Sb
příklad: montáž kola
Přerušení úlohy (preemptions) pmtn
při příchodu úlohy s vyšší prioritou je současná úloha přerušena
Vhodnost stroje Mj
podmnožina strojů Mj , na níž lze provádět úlohu j
přiřazení místností: postačující velikost učebny
hry: počítač s HW grafickou knihovnou
Omezení na pracovní sílu W , Wl
do problému zavedeme další typ zdroje
stroje mohou potřebovat operátory a úlohy lze provádět jen tehdy,
pokud jsou dostupní W operátorů
mohou existovat různé skupiny operátorů se specifickou kvalifikací
Wl je počet operátorů ve skupině l
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 2 14. února 2022
Omezení (pokračování) β
Směrovací (routing) omezení
udávají, na kterých strojích musí být úloha prováděna
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í
Nastavovací (setup) doba a cena sijk, cijk, sjk, cjk
závislé na posloupnosti provádění
sijk čas nutný pro provádění úlohy k po úloze j na stroji i
cijk cena nutná pro provádění úlohy k po úloze j na stroji i
sjk , cjk čas/cena nezávislý na stroji
příklady
plnění limonád do lahví
problém obchodního cestujícího 1|sjk |Cmax
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 3 14. února 2022
Omezení (pokračování) β
Výroba na objednávku a na sklad
výroba zboží na sklad, pokud je u něj záruka spotřeby
nutno uvážit cenu za skladování
výroba zboží na objednávku vynucuje úvahu termínů dokončení
vyprodukované množství závislé na zákazníkovi
Skladovací prostor a doba čekání při výrobě
omezené množství prostoru při výrobě
horní hranice počtu úloh čekajících ve frontě na stroj
blokování: úloha je zablokována na současném stroji, protože fronta na
následujícím stroji je plná
...
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 4 14. února 2022
Optimalizace: výkon a makespan γ
Makespan Cmax: 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é a základní kritérium
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 5 14. února 2022
Optimalizace: zpoždění γ
Zpoždění (lateness) úlohy j: Lj = Cj − dj
Maximální zpoždění Lmax
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
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 6 14. února 2022
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í
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 7 14. února 2022
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
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 8 14. února 2022
Optimalizace: skladování při výrobě γ
Cena za skladování vyrobeného zboží
Cena za skladování při výrobě
(Work-In-Process inventory cost)
příliš velké množství právě vyráběneho zboží může zaplnit linku
příliš dlouho odložené zboží může být znehodnoceno
Délka skladování při výrobě svázána s časy konce úloh
⇒ minimalizace součtu časů konců úloh
n
j=1
Cj
⇒ minimalizace váženého součtu časů konců úloh
n
j=1
wjCj
celková hodnota daná skladováním při výrobě
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 9 14. února 2022
Další optimalizační kritéria γ
Robustnost
robustnější rozvrh vyžaduje méně změn při změně problému (porucha
stroje, dopravní špička)
Cena za nastavení (setup)
cena za připravení letadla na odlet
(čištění, zásobování, doplnění pohonných hmot)
Cena za pracovní sílu
cena za přiřazení zaměstnanců na konkrétní směnu
V problému často řada optimalizačních kritérií
multi-kriteriální rozvrhování
Pareto optimalizace
žádoucí vztah mezi nimi nemusí být jasně definovaný
co je důležitější?
ani samotná kritéria nemusí být jasně definována
jak daný požadavek reprezentovat kritériem?
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 10 14. února 2022
Polynomiální a nedeterministicky polynomiální problémy
Polynomiální problémy
existuje algoritmus polynomiální složitosti pro řešení problému
NP a NP-úplné problémy
řešitelné nedeterministickým polynomiálním algoritmem
potenciální řešení lze ověřit v polynomiálním čase
v nejhorším případě exponenciální složitost
(pokud neplatí P=NP)
NP-úplný problém
libovolný problém v NP se na něj dá polynomiálně redukovat
Příklady:
Polynomiální
1||Lmax P|pmtn|Cmax 1|| wj Cj
NP
1|rj |Lmax P2||Cmax P2|| wj Cj
Hana Rudová, FI MU: Úvod do rozvrhování (dokončení) 11 14. února 2022
Řídící pravidla
14. února 2022
Řídící pravidla (dispatching rules)
Řídící pravidlo
určuje pořadí (prioritu), ve kterém mají být úlohy prováděny
pokud má více úloh stejnou prioritu, úlohy jsou seřazeny náhodně
(nebo např. dle čísla úlohy)
jakmile se některý stroj uvolní, je vybrána nejprioritnější úloha
Příklad: použijte pro seřazení úloh nejdřívější termín dostupnosti rj
úlohy 1 2 3 4 5 6
rj 9 2 1 2 0 3
pj 1 2 1 1 2 2
Hana Rudová, FI MU: Řídící pravidla 13 14. února 2022
Pravidla s termíny dostupnosti rj a dokončení dj
Nejdřívější termín dostupnosti (Earliest Release Date first ERD)
ekvivalentní nejdříve-příjde-nejdříve-obsloužen (First-Come-First-Serve)
minimalizuje odlišnosti v době čekání na stroji
Nejdřívější termín dokončení (Earliest Due Date first EDD)
směřuje k minimalizaci maximálního zpoždění mezi čekajícími úlohami
optimální pro 1||Lmax (všechny úlohy dostupné na začátku)
pozor, i zde (zejména stejně jako u všech pravidel) musíme brát v úvahu
termín dostupnosti, tj. úlohu lze plánovat teprve když je dostupná!!!
př. r2 = 3, d2 = 5, r3 = 0, d3 = 6 – dříve plánujeme úlohu 3
úlohy 1 2 3 4 5 6
rj 9 3 0 2 0 6
pj 1 2 1 1 2 2
dj 10 5 6 9 2 8
Hana Rudová, FI MU: Řídící pravidla 14 14. února 2022
Pravidla s termíny dostupnosti: minimální rezerva
Minimální rezerva (Minimum Slack first MS)
max(dj − pj − t, 0)
dj termín dokončení
pj doba provádění
t aktuální čas
funkci max používáme, abychom neměli záporné hodnoty pro úlohy,
které už to určitě nestihnou
minimalizace kriterií svázaných s termínem dokončení,
tj. maximální zpoždění
Hana Rudová, FI MU: Řídící pravidla 15 14. února 2022
Statická vs. dynamická pravidla
Statická pravidla nejsou závislá na probíhajícím čase
pořadí se spočítá jako funkce závislá na úloze a/nebo stroji
pořadí nám definuje prioritní frontu úloh
př. nejdřívější termín dostupnosti
Dynamická pravidla jsou závislá na čase
nutno zahrnout do výpočtu funkce i aktuální čas
uspořádání úloh závisí na čase ⇒ v každém čase je nutné určit znovu
úlohu s nejvyšší prioritou a tu zpracováváme
př. minimální rezerva
Hana Rudová, FI MU: Řídící pravidla 16 14. února 2022
Pravidla s dobou trvání pj
Nejdelší doba trvání (Longest Processing Time first LPT)
směřuje k rovnoměrnému zatížení paralelních strojů,
tj. k minimalizaci makespan
myšlenka: kratší úlohy lze později využít pro vyrovnání zátěže na konci;
jakmile jsou úlohy přiřazeny na stroje, tak je lze přeuspořádat bez
změny zatížení
Hana Rudová, FI MU: Řídící pravidla 17 14. února 2022
Pravidla s dobou trvání pj
Nejkratší doba trvání (Shortest Processing Time first SPT)
směřuje k minimalizaci součtu časů konců úloh,
tj. WIP (Work In Process, cena za sklad při výrobě)
Vážená nejkratší doba trvání
(Weighted Shortest Processing Time first WSPT)
navíc wj oproti SPT (řadím dle wj /pj )
minimalizace vážených součtu časů konců úloh, tj. WIP
optimální pro jeden stroj, kde jsou všechny úlohy dostupné na začátku
(rj = 0 pro každou úlohu j)
Hana Rudová, FI MU: Řídící pravidla 18 14. února 2022
Další řídící pravidla
Kritická cesta (Critical Path CP)
vhodné pro precedenční omezení
vybírá úlohu, která je první v nejdelším řetězci
dob provádění v grafu úloh daném precedencemi
vede k minimalizaci makespan
Nejméně flexibilní úloha (Least Flexible Job LFJ first)
při zadání množiny vhodných strojů
vybírá se úloha, která může být prováděna na nejmenším počtu strojů
(tj. nejméně alternativ)
vede k minimalizaci makespan
Náhodné pořadí (Service in Random Order SIRO)
náhodný výběr úloh
Hana Rudová, FI MU: Řídící pravidla 19 14. února 2022
Řídící pravidla: diskuse
Jednoduchá na implementaci
Optimální ve speciálních případech
Zaměřeny na jedno optimalizační kritérium
Kombinování několika řídících pravidel: kompozitní řídící pravidla
Použití v praxi
pro řadu problémů příliš triviální
i tady lze např. použít jako generátor iniciálního řešení
nebo jako metodu pro řešení podproblémů
používá se pro složité problémy s vysokými nároky na propustnost
např. počet naplánovaných aktivit za vteřinu
nebo pro problémy s vysokým stupněm dynamiky
např. plánování úloh na počítače
(neznámá doba trvání, příchody nových úloh, výpadky strojů)
Hana Rudová, FI MU: Řídící pravidla 20 14. února 2022