Denní rozvrhování, plánování a řízení výroby
Teoretické řešení rozvrhování
Teoretické řešení rozvrhování
Možnosti nalezení optimálního řešení
První možnost řešení je zkusit všechny možnosti. Řada uživatelů výpočetní techniky nekriticky věří v souladu s dosavadním trendem, že možnosti výpočetní techniky exponenciálně rostou, zvětšují se objemy pamětí a výkony procesorů. Zatím sice nevíme, kdy tento růst skončí vyčerpáním fyzikálních vlastností hmoty, nicméně můžeme předpokládat, že zatím tento růst bude pokračovat.
To je dobrá zpráva. Špatná zpráva však přichází z oblasti teorie počítačů. Tam jsou hodnoceny algoritmy podle své složitosti. Bohužel rozvrhovací algoritmy patří mezi velmi složité, tzv. NP-úplné. Je prokázáno, že na současných počítačích by výpočet pro nepříliš velký přesáhl stáří vesmíru - jedná se o kombinatorické algoritmy, de facto s faktoriálními odhady času.
Přesně jde algoritmicky řešit jen několik málo úloh. Všechny ostatní lze rozdělit na dvě skupiny:
- skupinu, kde detailní rozvrh nemá smysl, neboť velký počet rozvrhovaných úkolů a pracovišť vede ke sblížení statického a dynamického využití pracovišť (fronty jsou tak dlouhé, že je jedno, co vybereme)
- skupinu, kde detailní rozvrh smysl má, pak se pokusíme o heuristické řešení, které bude určitě lepší než nejhorší, v lepším případě lepší než průměrné a v nejlepším případě o málo horší než optimální
Speciální případ - rozvrh pro jedno pracoviště
Mějme množinu úloh a jediné pracoviště, pro každou úlohu máme termín plnění a celkový čas. Úkolem je seřadit tyto úlohy tak, aby průměr součtu všech zpoždění byl nejmenší. Předstih neuvažujeme. Alternativně můžeme za kritérium kvality uvažovat průměr součtu kvadrátů zpoždění. Tím vyloučíme případy s extrémním zpožděním.
Jedno je jasné: Pokud leží všechny požadované termíny plnění až za součtem všech celkových časů, tak na pořadí nezáleží (bereme jen skluzy).
Jinak můžeme použít následující strategie:
- FCFS (first come, first served) - požadavky vyřídíme v pořadí, jak přišly,
- DDS (customer due date) - vyřizujeme vždy požadavek, který má nejdříve požadovaný termín splnění,
- SPT (shortest process time) - vybíráme požadavku seřazené vzestupně pole celkového času,
- LPT (longest process time) - vybíráme požadavku seřazené sestupně pole celkového času,
- CR (critical ratio) - minimální poměr zbývající dní k celkovému času operace,
- Silové řešení (prozkoumání) všech permutací požadavků (je jich bohužel n!),
- Náhodný výběr - pro velký počet požadavků vybereme relativně dost náhodných permutací a z nich vybereme nejlepší.
Každá strategie má své výhody na nevýhody. Kromě silového řešení v případě velkého množství úloh můžeme vždy určit více strategií a vybrat nejlepší.
Speciální případ - rozvrh pro dvě pracoviště na výrobní lince
Pro dvě pracoviště existuje algoritmus (Johnsonovo pravidlo), který rozvrhne úlohy tak, že nedojde k prostojům. Tento algoritmus předpokládá určitou množinu úkolů, které se v průběhu řešení nemění.
Předpoklady
- Doba úkolu musí být známa a konstantní pro každou práci na každém pracovišti.
- Doby úkolu musí být nezávislé na posloupnost úloh na pracovišti.
- Všechny úkoly musí následovat ve stejné dvoukrokové pracovní posloupnosti (pracoviště 1, potom pracoviště 2).
- Nemohou být použity priority operací.
Určení optimální posloupnosti zahrnuje tyto kroky:
- Sepište úlohy a jejich časy pro každé pracoviště.
- Vyberte úlohu s nejkratším časem. Je-li nejkratší čas na prvním pracovišti, rozvrhněte tuto úlohu jako první na první pracoviště, pokud se jedná o úlohu na druhém pracovišti, rozvrhněte ji jako poslední. V případě více možnosti rozhodněte náhodně.
- Vylučte tuto úlohu a její časy z dalších úvah.
- Opakujte kroky 2 a 3, dokud nebudou všechny úlohy rozvrženy.