Minimalizacja maksymalnego

opóźnienia na maszynach

równoległych

Algorytm Liu

Magdalena Kaźmierczak

Reguła EDD (Earliest Due
Date)



Reguła EDD stosowana jest do
szeregowania zadań na jednej
maszynie
o czasach przybycia ustalonych na 0.



Reguła EDD porządkuje sekwencje
zadań według niemalejących
wymaganych terminów zakończenia d

j

.

Reguła EDD - właściwości



Złożoność obliczeniowa reguły EDD
O(nlogn).



Reguła EDD pozwala na znalezienie
optymalnego harmonogramu
minimalizującego maksymalne
opóźnienia lub spóźnienia.

Algorytm Liu



1. Spośród dostępnych zadań
przydziel maszynę temu, które ma
najmniejszy wymagany termin
zakończenia.



2. Przerwij wykonywane zadanie (jeśli
takie istnieje) w momencie przybycia
nowego. Wróć do 1.

Algorytm Liu - właściowości



Złożoność obliczeniowa O(n

2

), oparty

na regule EDD.



Pozwala na odnalezienie
optymalnego harmonogramu nawet
dla przypadku

1 | r

i

, pmtn | L

max

Przykład 1



1|r

i

,pmtn|L

max



n=6



Z

1

Z

2

Z

3

Z

4

Z

5

Z

6



p=[2, 2, 3, 1, 2, 2 ]



r= [0, 0, 1, 2, 3, 3 ]



d=[2, 3, 1, 4, 5, 5 ]

1 2 3 4 5 6 7 8 9 10 11 12

Z

1

Z

3

Z

1

Z

2

Z

4

Z

5

Z

6

M

1

L

max

=7

L

Z1

=3

L

Z2

=4

L

Z3

=3

L

Z4

=4

L

Z5

=5

L

Z6

=7

Zadania dostępne do wykonania Zadania zakończone

Z

3

Z

3

Przykład 2



1|r

i

,pmtn|L

max



n=5



Z

1

Z

2

Z

3

Z

4

Z

5



p=[1, 2, 2, 2, 2 ]



r= [0, 0, 2, 3, 6 ]



d=[2, 5, 4, 10, 9 ]

Z

1

1 2 3 4 5 6 7 8 9

M

1

L

max

=0

Zadania dostępne do wykonania Zadania zakończone

Z

2

Z

2

Z

4

Z

5

Z

4

L

Z1

=-1

L

Z2

= 0

L

Z3

= 0

L

Z4

=-1

L

Z5

=-1

Z

3

Z

3

Zasoby w sieci



Opis algorytmów szeregowania zadań

http://riot.ieor.berkeley.edu/riot/Applications/Scheduling/index.
html



Program LEKIN umożliwiający tworzenie harmonogramów

http://www.stern.nyu.edu/om/software/lekin/index.htm