Minimalizacja średniego czasu

przepływu na maszynach

równoległych

Algorytm optymalny i
algorytm RPT

Przygotował: Tomasz Hejne

Zadania podzielnie i niepodzielne

Przypadki

P||C

i

i podzielnych

P|pmtn|C

i

można

rozpatrywać razem (optymalny harmonogram
podzielny nie musi dzielić zadań).

Algorytm optymalny

O(nlog n):

1. Przyjmij, że liczba zadań dzieli się przez m (ew.
wprowadź zadania puste),

2. Uporządkuj je według SPT,

3. Przypisuj kolejne m–tki zadań w sposób dowolny do
różnych maszyn.

Algorytm optymalny

Algorytm optymalny - przykład

m = 3, n=13, p

j

=

{3,4,1,3,2,5,3,6,2,1,4,3,1}

SPT:

Z

14

Z

15

Z

3

Z

10

Z

13

Z

5

Z

9

Z

1

Z

4

Z

7

Z

12

Z

2

Z

11

Z

6

Z

8

p

j

= 0 0 1 1 1 2 2 3 3 3 3 4 4

5 6

Ponumerowane i uszeregowana zadania w niemalejącej kolejności

Dodajemy dwa zadania
puste by liczba zadań
dzieliła się przez m

Lista zadań (wraz z dopisanymi zadaniami pustymi) dzielimy na bloki o długości m

W pierwszym momencie
szeregujemy zadania o
zerowym czasie trwania, potem
następne, na kolejnych
maszynach

M

1

M

2

M

3

14

5

10

1

Z

3

Z

10

Z

13

Z

5

Z

9

Z

1

Z

4

Z

7

Z

12

Z

2

Z

11

Z

6

Z

8

C

i

=

80

C

max

= 14

Próbą pogodzenia kryteriów

C

max

i

C

i

jest

algorytm RPT

:

1. Zastosuj szeregowanie LPT.
2. Na każdej maszynie posortuj zadania według SPT.

Dokładność:

1C

i

(RPT)

/C

i

*m

(zwykle jest

lepsza)

Minimalizacja średniego czasu przepływu

na maszynach równoległych

Procesory identyczne, zadania niezależne

Algorytm RPT

Algorytm RPT

LPT: Z

8

Z

6

Z

11

Z

2

Z

12

Z

7

Z

4

Z

1

Z

9

Z

5

Z

13

Z

10

Z

3

p

j

= 6 5 4 4 3 3 3 3 2 2 1 1

1

C

i

=

80

Z

10

Z

13

Z

3

Z

5

Z

9

Z

1

Z

4

Z

7

Z

12

Z

2

Z

11

Z

6

Z

8

LPT

m = 3, n=13, p

j

=

{3,4,1,3,2,5,3,6,2,1,4,3,1}

C

max

= 13

M

1

M

2

M

3

14

5

10

1

+
SPT
=
RPT

Z

10

Z

9

Z

7

Z

8

Z

13

Z

3

Z

1

Z

12

Z

6

Z

5

Z

4

Z

2

Z

11

1.Szeregowanie LPT

(

Longest Processing Time

):

• Szereguj listowo( z ustalonego ciągu zadań wybieraj pierwsze wolne (według
„listy”), przypisując je zawsze do zwalniającego się procesora) przy czym zadania na
liście są wstępnie posortowane według nierosnących czasów wykonania p

i

.

2.Szeregowanie
LPT

: Na każdej

maszynie posortuj
zadania` według SPT