Rozvrhovanie na viacerých procesoroch

2) Rozvrhovanie na viacerých procesoroch

(Viacstup

ň

ová výroba)

Používajú sa tu rôzne heuristiky, napr. LPT (Longest Processing Time)

Algoritmus heuristiky LPT:
begin

vytvor zoznam úloh t(1)≥ t(2)≥ ... ≥ t(n)

for j=1 to m Sj=0;

j := 1

repeat

urči také k, že Sk=min{Si}

1≤i≤m

priraď úlohu Tj (prvá v aktuálnom zozname) na procesor k

Sk := Sk+tj;

j := j+1;

until j=n;

end;

n = 7
m = 3
T = [5, 5, 4, 4, 3, 3, 3]

Dokázaná najväčšia možná chyba, ktorej sa môže dopustiť algoritmus LPT oproti optimálnemu

rozvrhu je:

9

11

9

1

12

9

1

3

4

3

1

3

4

=

−

=

−

=

−

=

LPT

LPT

Q

m

Q

Príklad
R1:

R2:

P3

P2

P1

P2

P3

P1

P1

P2

II. DEDIKOVANÉ PROCESORY

1)

Open shop – každé riešenie úlohy typu flow shop je aj riešením úlohy open shop

2)

Flow shop – J1 ... Jn

Úlohy rozmeru m = 2, n =

ľ

ubovo

ľ

né, sa dajú riešiť Johnsonovým algoritmom.

R=[3, 4, 2, 6, 7, 1, 5]

Johnsonov algoritmus sa dá použiť aj pre 3 procesory (t.j. flow shop m = 2, n =

ľ

ubovo

ľ

né),

ale len ak platia nasledujúce dve obmedzenia:

{ }

{ }

{ }

{ }

i

i

i

i

i

i

P

P

P

P

2

3

2

1

max

min

max

min

≥

≥

3) Job shop
Úlohy rozmeru m =

ľ

ubovo

ľ

né, n = 2

sa dajú riešiť graficky.

Príklad

R1: 9 + 3 + 8 = 20

-> optimálny rozvrh

R2: 9 + 6 + 2 + 1 + 8 = 26