McNaughtonův algoritmus

McNaughtonův algoritmus slouží k rozvržení n preemptivních úkolů na k identických zdrojů při minimalizaci délky rozvrhu. Algoritmus pracuje s lineární asymptotickou složitostí O(n).

Princip

Algoritmus nejprve vytvoří obdélníkovou matici, v níž je počet řádků roven počtu zdrojů a počet sloupců odpovídá délce rozvrhu. Délku rozvrhu můžeme vyjádřit jako:


C^{*}_{max} = \\max \\{{{1} \\over {R}}\\; \\sum^{n}_{i = 1}\\; p_{i},\\; \\max_{i = 1, \\;2, \\cdots, \\; n} \\; p_{i} \\}

Suma v maximu značí situaci, kdy je obdélníková matice rozvrhu ideálně zarovnána (tj. každý ze zdrojů je vždy obsazen). Druhý argument pak vyjadřuje délku nejdelšího úkolu – jednotlivé úkoly jsou vnitřně sekvenční, nelze proto jeden úkol vykonávat zároveň na více zdrojích (procesorech).

Nyní, když je již známá délka rozvrhu, může algoritmus přistoupit k samotnému plánování. Algoritmus iteruje postupně přes všechny úkoly a vyplňuje matici od levého horního rohu po řádcích. První úkol umístí do levého horního rohu, druhý úkol těsně za něj a tak dále. V okamžiku, kdy se některý z úkolů již nevejde celý na jeden řádek (zdroj), tak jej algoritmus přeruší (nechá na k-tém zdroji vykonat pouze koncovou část úkolu), a jeho první část rovrhne na zdroj následující. Díky výše zmíněnému výpočtu délky rozvrhu se nikdy nemůže stát, že by byl jeden úkol zpracováván v jeden okamžik více zdrojích.

Po rozvržení posledního úkolu algoritmus terminuje. Matice odpovídá optimálnímu rozvrhu.


Příklad

Rozvrhněte následující úkoly T = [1,\\; 4,\\; 4,\\; 2,\\; 1] na 3 identické zdroje s využitím preempce.

Řešení

Celková délka rozvrhu bude 4, protože suma délek úkolů je 12 a rozvrhujeme na 3 zdroje, a navíc je délka nejdelšího úkolu taktéž 4. Matice rozvrhu proto bude mít rozměr 3 \\times 4.

Výsledný rozvrh
Výsledný rozvrh

Literatura

  • HANZÁLEK, Zdeněk. Kombinatorická optimalice - slides k přednáškám.







Doporučujeme

Internet pro vaši firmu na míru