Denní rozvrhování, plánování a řízení výroby
Teoretické řešení rozvrhování
 Prezentace
 Tisk

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:


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:



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


  1. Doba úkolu musí být známa a konstantní pro každou práci na každém pracovišti.
  2. Doby úkolu musí být nezávislé na posloupnost úloh na pracovišti.
  3. Všechny úkoly musí následovat ve stejné dvoukrokové pracovní posloupnosti (pracoviště 1, potom pracoviště 2).
  4. Nemohou být použity priority operací.


Určení optimální posloupnosti zahrnuje tyto kroky:


  1. Sepište úlohy a jejich časy pro každé pracoviště.
  2. 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ě.
  3. Vylučte tuto úlohu a její časy z dalších úvah.
  4. Opakujte kroky 2 a 3, dokud nebudou všechny úlohy rozvrženy.