Denní rozvrhování, plánování a řízení výroby
Teoretické řešení rozvrhování
 Vytisknout materiál

Možnosti nalezení optimálního řešení



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ě


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ší.



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


  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.

Opakujte kroky 2 a 3, dokud nebudou všechny úlohy rozvrženy.