Minimalizacja średniego czasu
przepływu na maszynach
równoległych
Algorytm optymalny i
algorytm RPT
Przygotował: Tomasz Hejne
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ść:
1C
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