Precedencne ohranicenia

T2

T1

T4

T3

T5

T6

T7

T8

PRECEDENČNÉ OHRANIČENIA

Príklad
Máme 3 identické paralelné procesory a daných 8 úloh s týmito parametrami:

P = {P1, P2, P3}
T = {T1, T2, …, T8}
{T1< T3, T2< T3, T2< T4, T3< T6, T3< T7, T4< T6, T4< T8, T5< T8} precedencie
m = 3

paralelné procesory

ti = [3, 4, 1, 2, 1, 2, 3, 2]

doba trvania úloh

rj = 0 (j = 1, ... , 8)

časy pripravenosti

di = [5, 4, 5, 3, 7, 6, 9, 12]

požadované časy ukončenia

wi = [1, 2, 1, 3, 1, 2, 2, 2]

priority

PRECEDENČNÝ GRAF:









GANTTOV DIAGRAM:

R1:

R2:

POROVNANIE:

P2

P3

P1

P3

P2

P1

I. PARALELNÉ PROCESORY

1) Rozvrhovanie na jednom procesore

(Jednostupňová výroba)

a) S prerušením

JACKSONOV ALGORITMUS:
Máme n - úloh, rôzne ri a di. Potom algoritmus pre nájdenie optimálneho rozvrhu v zmysle kritéria
Lmax funguje takto:

1) Vždy aktivuj úlohu s najskoršou dobou ukončenia.
2) Akonáhle začne byť úloha Ti pripravená a procesor je obsadený úlohou Tj, pozastav úlohu Tj

v prospech úlohy Ti práve vtedy, ak čas ukončenia i-tej úlohy je skorší ako j-tej úlohy, inak
ponechaj bežať úlohu Tj.

Príklad
R1:

R2:

b) Bez prerušenia - zložitejšia úloha, nakoľko ide o permutačnú úlohu (n! možných rozvrhov), ktorú
až na špeciálne prípady nemožno riešiť v polynomiálnom čase. Niektoré špeciálne prípady nasledujú:

1. - Ti – úloh (i = 1, ..., n)

- ri = 0 (i = 1, ..., n)
- bez precedencií
- bez priorít
- bez di

Z hľadiska kriteriálnej funkcie Cmax sú všetky rozvrhy sú rovnako dobré

2. - Ti – úloh (i = 1, ..., n)

- ri = 0 (i = 1, ..., n)
- bez precedencií
- s prioritami wi
- bez di

Z hľadiska kriteriálnej funkcie Cmax je optimálne usporiadanie úloh podľa nerastúcej

postupnosti ich priorít, tj.:

w(1) ≥ w(2) ≥ ... ≥ w(n)

3. - Ti – úloh (i = 1, ..., n)

- ri = 0 (i = 1, ..., n)
- bez precedencií
- bez priorít
- di = rôzne

Z hľadiska kriteriálnej funkcie Lmax (ale aj kriteriálnych funkcií T a nT) je optimálne

usporiadanie úloh podľa neklesajúcej postupnosti ich požadoaných časov ukončenia, tj.:

d(1) ≤ d(2) ≤ ... ≤ d(n)

4. - Ti – úloh (i = 1, ..., n)

- ri = 0 (i = 1, ..., n)
- bez precedencií
- bez priorít
- bez di

Z hľadiska kriteriálnej funkcie Fmax je optimálne usporiadanie úloh podľa neklesajúcej

postupnosti ich dĺžok trvania, tj.: t(1)

≤ t

(2)

≤ ... ≤ t

(n)

5. - Ti – úloh (i = 1, ..., n)

- ri = 0 (i = 1, ..., n)
- bez precedencií
- s prioritami wi
- bez di

Z hľadiska kriteriálnej funkcie Fw je optimálne usporiadanie úloh podľa neklesajúcej

postupnosti

w(1)/t(1) ≥ w(2)/t(2) ≥ ... ≥ w(n)/t(n)

6. Všetky ostatné úlohy vedú na permutačné rozvrhy a je možné ich riešiť napríklad metódou vetvenia

a medzí, ktorá sa snaží efektívne prehľadať nasledujúci priestor prehľadávania:

n! listových uzlov

2. úloha

n*(n-1) vetiev

n-tá úloha

1.úloha

…

…

...