Počítačové rozvrhování výroby Martin Hrubý Fakulta informačních technologií Vysoké učení technické v Brně
Co je cílem?
• Výsledkem rozvrhování je rozvrh. Plán a rozvrh. • Cílem je získat rozvrh pro efektivní výrobu. • Získat ho přesný — časování, souběhy, platnost, racionalita. • Podnikové zvyklosti ve výrobě. • Získat ho rychle — jak dlouho se chce čekat na výsledek? • Získávat ho opakovaně, tj. experimentovat. • Reagovat na události ve výrobě.
Školní rozvrh
Ganttův diagram
Úloha rozvrhování
• Akademická a praktická formulace úlohy. • Úloha obsahuje: • Výrobní operace a jejich vazby. • Výrobní zdroje — stroje, nástroje, personál a materiál. • Zdrojové požadavky operací. • Rozvrhové požadavky.
• Formulace podnikové úlohy do modelové podoby (ustálená terminologie podniku).
Kombinatorická úloha
• Komb. úlohy — RCPSP, VRP, NRP, TSP, … • Kombinatorický aspekt. • Pořadí provádění věcí jako kódování řešení. • Kombinatorická složitost v exponenciálním řádu (49! = 6x10^(62), 100! = 10^(157)).
• Řešení: optimální a sub-optimální.
Prostor řešení úlohy Počáteční řešení
Četnost
Průměrná řešení Dobrá řešení
Hodnocení
Konstrukce jednoho rozvrhu
• Rozvrh (jako Ganttův diagram) je 2D struktura. • Do struktury vkládáme časové a zdrojové umístění operací.
• LJS a RJS rozvrhování. • Do rozvrhu vkládáme operace v určitém pořadí.
LJS/RJS Rozvrhování
Architektura nástroje
• Automatizovaný prostředek pro rozvrhování. • Model úlohy — technologické postupy výroby. • Simulátor výroby — rozvrhovací procedura (SGS).
• Optimalizační metoda. • Zadání optimalizační úlohy — co je kritériem výběru.
Kritéria posuzování rozvrhů
• Je rozvrh A lepší než B? Rozhodnout strojově. • LJS rozvrh — celková doba výroby (makespan). • RJS rozvrh — suma odstupů od termínů dodání.
• Multi-kriteriální posuzování: • Splnění termínů. Odstup od termínů. Makespan. • Využití zdrojů — personál. • Počet rekonfigurací strojů. • Množství splněné výroby za daný časový rámec.
Multi-kriteriální rozhodování
• Váhování kritérií versus posuzování kritérií. • Příklad: • Míru uspokojení nad večeří v restauraci stanovím ze tří kritérií: • 1/3 chuť jídla, 1/3 vůně jídla, 1/3 kvalita obsluhy. • Zhodnotím kritéria, váhuji, výsledné číslo reprezentuje mé uspokojení.
• Vede na značně chaotické chování optimalizátoru. • Odlišné jednotky v kritériích (čas, počet, zpoždění).
Model úlohy
• Operace, zdroje a závislosti (precedence). • Zřetězení operací — výrobní zakázka (příkaz, technologický postup, …). Vede na konkrétní produkt.
• Model založený na operacích (rozvrhování). • Model založený na požadovaném množství výroby (plánování a rozvrhování).
• Jakou maximální produkci jsem schopen v týdnu provést? • Jakou produkci zvládnu s aktuálním stavem zásob?
Model operace
• Fáze operace — příprava, rozjezd, výroba, uklízení.
• Atomičnost operace. • Kontextová příprava operace — fáze přípravy je platná pro další operace v čase.
• Job mounter — procedura, která umístí operaci do rozvrhu.
Vazby operací
• Vazba mezi dvěma operacemi A, B — časová souvislost operací (např. transport).
• Zřetězení operací A, B, C v technologickém postupu.
• Left-Justified & Right-Justified Schedule.
Vazby operací
LJS/RJS Rozvrhování
Rozvrhování s pevnými vazbami
Na pořadí záleží Volná vazba S-S 1 Pevná vazba S-S 2
Počátek
Optimalizační metody
• Budeme hledat to správné pořadí operací v rozvrhování.
• Prostor řešení. Kandidátní řešení.
• Triviální metoda — iterační. • Exaktní metody — LP/MIP, SAT Solving. • Heuristické iterační metody — stochastický prvek.
Genetické algoritmy
• Evoluce — přirozený versus řízený výběr. • Evoluce je proces tvořený generacemi populací. • Ukončení evoluce a výsledek. • GA je univerzální optimalizační schéma. • Jedinec v populaci je dán kódem pro generování rozvrhu.
Cyklus evoluce
Genetické operace c1
c2
Rodič 1
0
1
3
4
2
5
6
7
Rodič 2
0
3
1
2
4
6
5
7
Potomek
0
1
3
2
4
5
6
7
Vzor
0
1
3
4
2
5
6
7
Mutant
3
1
0
4
2
6
5
7
Výhody a nevýhody GA
• Výhody: • Stále máme alespoň nějaký výsledek. • Metoda je flexibilní a dá se vyladit na konkrétní podnik. • Čím déle GA pracuje, tím by měl být výsledek lepší (vizte rozložení četnosti řešení).
• Nevýhody: • Stochastický prvek ve výpočtu — bez něj to nelze. • Degenerace populace.
Dynamické heuristiky
• Optimalizátor se učí o úloze v průběhu jejího řešení.
• ”Ještě jsem neviděl dobrý rozvrh, při kterém by
operace A a B startovaly souběžně, po sobě, …”
• Charakteristiky rozvrhů. • Vylučování rozvrhů charakteristikami. • Odhalování vylučujících charakteristik. • Řízení optimalizace.
Výpočetní výkon optimalizace
• Paralelizace — spousta elementárních
výpočetních úkonů je nezávislá na ostatních.
• Je možné je provést v počítači souběžně.
• Paralelizace výpočtu populace. • Paralelizace samotné evoluce.
Paralelní evoluce
• IBM Power8 20xCPU x 8 vláken. • 160 samostatných evolucí v jedné velké populaci.
• Výsledky jsou nadějné: lze dosáhnout dobrého výsledku v menším počtu generací (zkrátit evoluci).
Výsledek evoluce
• Výsledkem evoluce je nejlepší nalezený jedinec, tj. kód pro vytvoření rozvrhu.
• Rozvrh se exportuje do nadřazeného podnikového IS.
• Uživatelská interpretace výsledku. • Přehodnocení rozvrhu s částečně rozpracovanou výrobou.
Nasazení optimalizátoru
• Vyžaduje v podniku určité (počáteční) úsilí. • Modelování technologických postupů do
podoby zadání pro optimalizátor (jednotlivé výrobky).
• Školení, konzultace.
• Dodržování vypočteného rozvrhu. • Zpětná vazba.
Závěr
• Kvalita rozvrhu — počítač versus člověk. • Náklady na pořízení optimalizátoru. • Nasazení optimalizátoru v podniku. • Vize: racionálně dynamicky řízená výroba.
