Úvod do rozvrhování
14. února 2023
1 Rozvrh
2 Reálné problémy
3 Terminologie
4 Klasifikace rozvrhovacích problémů
Definice pojmu rozvrhování
Rozvrhování
optimální alokace/přiřazení zdrojů množině úloh v čase
omezené množství zdrojů
maximalizace zisku za daných omezení
Stroj Mi , i = 1, . . . , m úloha Tj , j = 1, . . . , n
Strojově orientovaný Ganttův diagram
time
1 1 3 5 4
M T T3 6 9
M T T T T
M T T T2 2 8 7
0 1 2 3 4 5 6 7 8
Hana Rudová, FI MU: Úvod do rozvrhování 2 14. února 2023
Rozvrh
Rozvrh:
dán umístěním úloh do konkrétního času a na konkrétní zdroje,
kde mají být úlohy prováděny
Úplný rozvrh:
v rozvrhu jsou umístěny všechny úlohy ze zadání problému
Částečný rozvrh:
některé úlohy ze zadání problému nejsou umístěny/přiřazeny
Konzistentní rozvrh:
rozvrh, ve kterém jsou splněna všechna omezení
kladená na zdroje a umístěné/přiřazené úlohy, např.
úloha je naplánována v čase, kdy je dostupná
na jednom stroji (s jednotkovou kapacitou) běží nejvýše jedna úloha
Konzistentní úplný rozvrh vs. konzistentní částečný rozvrh
Optimální rozvrh:
umístění úloh na stroje je optimální vzhledem k zadanému
optimalizačnímu kritériu, např.
min Cmax : makespan (čas dokončení poslední úlohy) je minimální
Hana Rudová, FI MU: Úvod do rozvrhování 3 14. února 2023
Příklad: montáž kola
10 úloh s danou dobou trvání
Precedenční podmínky
úlohu lze provést až po provedení
zadané množiny úloh
Nepreemtivní úlohy
úlohy nelze přerušit
Optimalizační kritéria
minimalizace makespan
minimální počet pracovníků
T4
T6 8 T10
T9T5
T1
T3
T7
7
7
822
8
18
3
2
T2 7
T
T93T
T1 2
T4 6 T10
T5
T
T8T
T7
Schedule
2TT1
T106TT5T4
Optimal
schedule
7 32
7T
24161452
T8 T93T
Hana Rudová, FI MU: Úvod do rozvrhování 4 14. února 2023
Reálný problém: rozvrhování sester v nemocnici
Jedná se o problém rozvrhování zaměstnanců
Požadavky na personál
odlišný počet sester v pracovní dny a o víkendu
menší nároky při obsazování nočních směn
dodržení pravidel daných ze zákona
preference zaměstnanců na pracovní dobu
. . .
Cíl
určit přiřazení sester na směny
splnění požadavků
minimalizace ceny
Hana Rudová, FI MU: Úvod do rozvrhování 5 14. února 2023
Plánování nákladní automobilové dopravy
Problém směrování vozidel (vehicle routing problem)
požadavky na doručení/vyzvednutí/doručení+vyzvednutí
lokace, časová okna, hmotnost, objem
vozidla, která musí tyto lokace obsloužit
kapacita/objem vozidel, jedno/více depot vozidel
stejná/různá vozidla
optimalizace: počtu vozidel, vzdálenosti, ceny
Statický vs. dynamický problém
problém dán předem vs. reakce na změny problému při realizaci řešení
Spolupráce FI s firmou Wereldo
1
3
2 4
5
6 7
8
9
1
3
2 4
5
6 7
8
9
Hana Rudová, FI MU: Úvod do rozvrhování 6 14. února 2023
Univerzitní rozvrhování předmětů http://www.unitime.org
Nalezení času a místnosti pro výuku předmětů na univerzitě
omezení kladena na umístění předmětů
optimalizace preferenčních požadavků na čas a místnosti
každý předmět má určeny své studenty (registrace, studijní obory)
minimalizace počtu překrývajících se předmětů pro všechny studenty
Návrh, vývoj a používání systému UniTime
FI spolupracuje na návrhu a vývoji od 2001
primárně vyvinuto a používáno na Purdue University, USA
MU: používáno na 7 fakultách včetně FI
International Timetabling Competition ITC 2019
reálné problémy z 10 různých univerzit po celém světě (UniTime data)
Hana Rudová, FI MU: Úvod do rozvrhování 7 14. února 2023
Terminologie: scheduling vs. timetabling
Scheduling ... rozvrhování/plánování
alokace zdrojů za daných podmínek na objekty umístěných
v časoprostoru tak, že je minimalizována celková cena daných zdrojů
důraz je kladen na uspořádání objektů
precedenční podmínky
př. plánování výroby: stanovení pořadí operací, důležitost časových
návazností operací
schedule ... rozvrh
zahrnuje prostorové a časové informace
Timetabling ... rozvrhování
alokace zdrojů za daných podmínek na objekty umístěných
v časoprostoru tak, že jsou co nejlépe splněna zadaná kritéria
důraz kladen na konkrétní časové umístění objektů
často vymezen předem časový horizont (počet rozvrhovaných slotů)
př. školní rozvrhování: předmětům přiřazen čas a místo vyuky
timetable ... rozvrh
ukazuje, kdy a kde se budou události konat
Hana Rudová, FI MU: Úvod do rozvrhování 8 14. února 2023
Terminologie: planning
Plánování (planning) někdy chápáno v dlouhodobějším horizontu
krátkodobé podrobné rozvrhování + dlouhodobé obecné plánování
např. plánování=vytvoření vhodné množiny úloh
tak aby bylo dosaženo zadaných cílů
rozvrhování=přiřazení úloh v čase na zdroje
tak aby byla minimalizována cena
nebo dlouhodobé plánování zdrojů
tak abychom pokryli budoucí potřeby
vs. krátkodobé rozvrhování úloh na zdroje
tak aby byly splněny aktuální požadavky
Hana Rudová, FI MU: Úvod do rozvrhování 9 14. února 2023
Terminologie: AI planning
Plánování v umělé inteligenci (AI planning)
vykonání posloupnosti akcí tak,
abychom se dostali z počátečního stavu do koncového stavu
př. plánování činností robota
počáteční stav v místnosti, cílový stav v místnosti,
robot provede posloupnost akcí (např. přemístí předměty) tak, aby se
dostal do cílového stavu
lze chápat jako vytvoření vhodné množiny úloh jako u plánování
(viz předchozí průsvitka)
Přednášká IV126 Umělá inteligence II
zahrnut blok přednášek o plánování
Hana Rudová, FI MU: Úvod do rozvrhování 10 14. února 2023
Terminologie: sequencing, rostering
Sequencing ... seřazení
za daných podmínek:
konstrukce pořadí úloh, ve kterém budou prováděny
sequence ... posloupnost
pořadí, ve kterém jsou úlohy prováděny
př. pořadí automobilů na montážní linku
Rostering
umístění zdrojů za daných podmínek do slotů s pomocí vzorů (pattern)
roster ... rozpis
seznam jmen lidí, který určuje, které úlohy budou provádět a kdy
př. rozpis sester v nemocnici, rozpis řidičů autobusů
Hana Rudová, FI MU: Úvod do rozvrhování 11 14. února 2023
Úlohy, stroje
Stroje (zdroje, prostředky) i = 1, . . . , m
Úlohy (aktivity) j = 1, . . . , n
(i, j) operace nebo provádění úlohy j na stroji i
úloha se může skládat z několika operací
příklad: úloha 4 má tři operace s nenulovou dobou trvání (2,4),(3,4),(6,4), tj.
je prováděna na strojích 2,3,6
Statické parametry úlohy
doba trvání pij , pj : 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 by měla být úloha j nejpozději dokončena (preference)
vs. deadline: čas, do kdy musí být úloha j nejpozději dokončena (požadavek)
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)Sij , Sj : čas zahájení provádění úlohy j na stroji i
čas konce úlohy (completion time) Cij , Cj : čas, kdy je dokončeno provádění
úlohy j na stroji i
Hana Rudová, FI MU: Úvod do rozvrhování 12 14. února 2023
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 pro jednotlivé rozvrhovací problémy
Příklady:
P3|prec|Cmax: montáž kola
Pm|rj | wj Cj : paralelní stroje
Hana Rudová, FI MU: Úvod do rozvrhování 13 14. února 2023
Vlastnosti stroje α
Jeden stroj 1: 1| . . . | . . .
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ů
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ř. 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ř. vektorový počítač počítá vektorové úlohy rychleji než klasické PC
Hana Rudová, FI MU: Úvod do rozvrhování 14 14. února 2023
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, j), (2, j), (3, j), (4, j)
1.stroj
3.stroj
4.stroj
2.stroj
Multi-operační problémy jsou klasické
detailně studované problémy operačního výzkumu
Reálné problémy ale často mnohem komplikovanější
využití znalostí o podproblémech nebo zjednodušených problémech a
jejich řešicích metodách
Hana Rudová, FI MU: Úvod do rozvrhování 15 14. února 2023
Flow shop α
Flow shop Fm
multi-operační problém s m stroji v sérii
každá úloha musí být prováděna na všech strojích
úloha musí být prováděna na všech strojích ve stejném pořadí
nejdříve se úloha provádí na 1. stroji, pak na 2., . . .
Flexible flow shop FFs
zobecnění flow shop problému
s fází, každé fázi přísluší paralelní stroj
příklad: paralelní stroj 1.fáze: 1+2+3, paralelní stroj 2.fáze: 4+5, ...
tj. multi-operační problém s s paralelními stroji
úloha musí projít všemi fázemi ve stejném pořadí
nejprve se úloha provádí na paralelním stroji 1. fáze,
pak na paralelním stroji 2. fáze, . . .
na paralelním stroji příslušejícím dané fázi může být úloha prováděna
na libovolném stroji
1.fáze
2.fáze
3.fáze
4.fáze
1
2
3
4
5
6
7
8
9
Hana Rudová, FI MU: Úvod do rozvrhování 16 14. února 2023
Open shop & job shop α
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
doba zpracování úlohy na některých strojích může být nulová
(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)
Open shop Om
multi-operační problém s m stroji
doba zpracování úlohy na některých strojích může být nulová
rozvrhovač určí, v jakém pořadí je úloha prováděna na strojích
Hana Rudová, FI MU: Úvod do rozvrhování 17 14. února 2023