WYKŁAD 04

Dane jest n zadań. Każde zadanie charakteryzuje się czasem wykonania. Naszym kryterium jest
minimalizacja czasu potrzebnego na wykonanie wszystkich zadań.

Przydzielamy zadania do procesorów.
<rysunek 1>

Jak reprezentować te zadania w pamięci komputera?

Mamy n zadań:

J = {1, ... , n}

W ramach każdego z podzbiorów musimy przechować informacje o kolejności przechowywować
zadań. I czy to wystarczy. Czy może zapisać numer tego zadania i jego moment wykonywania?

Bo procesor może wykonywać zadania w sposób taki:

<rysunek 2>

Ale wiadomo, że aby było optymalnie, musi być jak najmniej przestojów maszyny. Dlatego
interesuje nas kolejność.

Naszym kryterium jest Cmax. Dla ustalonej kolejności ten moment wyznaczamy tak:L

C1 = p6+ p2+p7+p4

Zatem widać, że kolejność sumowania nie ma znaczenia. Więc to co jest ważne, to dokonanie
przydziału zsadań do procesorów, a kolejność ich wykonywania jest nieistotna.

Zostaje nam tylkio problem znalezienia reprezentacji rozbicia zadań na2 procesory.

Możemy wykorzystać wektor binarny. Każdy bit mówi do któ¶ego procesora przyporządkowujemy
dane zadanie.Najprostsze rozwiązanie to: przeszukujemy przestrzeń nbitowych wektorów. Dla
każdego wyznaczamy Cmax i dla tych wszystkich sprawdzamy które rozwiązanie jest optymalne.
Złożoność: O(2^n)

for(i = 0; i < 2^(n+1) - 1; i++)

no i po sprawie.

Niby to mało, ale powalczymy z tym trochę.

Zaczniemy od drzewa. Będziemy budować wektor podobnie jak permutację. Będziemy robić
prefiksy i badać wszystkie możliwości ustalenia kolejnych bitów w prefiksie.

<rys 3>

I tak można to drzewo bnudować. Poziom 1 to przydział zadania 1 do konkretnego procesora,
poziom drugie, to zadanie 2 itd.

Żeby uprościć to, to każdy z węzłów wzbogacimy o informacje, które nam pomogą w zzadaniu.

A - moment zakończenia wykonywania zadań z prefiksu na procesorze zerowym
B - moment zakończenia wykonywania zadań z prefiksu na procesorze pierwszym

Więc będzie to para liczb: (A,B)

Jeżeli jesteśmy w takim węźle, to rozszerzenie go to wygenerowanie dwóch nowych prefiksów.

Załóżmy, że byliśmy w kroku -1. przechodzimy do kroku i. Decydujemy zatem które będzie
wykonywane zadanie.

<rysunek 4>

Zapomnijmy o wekorze. Pomyślmy, że szukamty Cmax. Z naszych węzłów odpada informacja o
prefiksach. Zostają dwie liczby. Każdy węzeł to taka struktura.

Wprowadzimy poszukiwanie wszerz tego drzewa. Z poziomu 0 stworzymy wszyste węzły z
poziomu 1. Na ich podstawie robimy kolejne poziomy.

Najprościej to jakaś struktura, wskaźniki poprzednik/następnik, wartownik - obiekt 0,0. Każda
iteracja to przeglądanie tych elementów.

załóżmy, że:

p1 = 2
p2 = 3

Trafiamy na nasz obiekt. Przed usunięciem na listę wpisujemy

<rys 5>

Ale w liście jest wykładnicza liczba elementów. Powalczmy z tym.

Wprowadzimy małą zmianę: założymy, że każde zadanie ma czas wykonywania w liczbie
naturalnej dodatniej. Ta duża liczba węzłów, to duża część nich będzie reprezentowana przez tę
samę parę liczb. Każdy z tych węzłów mógłby mieć inny prefiks, ale przecież z tej informacji
zrezygnowaliśmy. Czy dobrze?

Jak mamy kilka takich liczb, to czy z pkt widzenia dalszych prefiksów te informacje są taki same?
SĄ!
Więc wystarczy, żebyśmy tylko jedną zapisywali.

Zróbmy tak: jakoś te zbiór inaczej reprezentujemy, aby nie był pamięciożerny.

Każda z liczb (a,B) będzie naturalna dodatnia. Możemy też podać zakres, w jakim będą się
zmieniać wartości. Przyjmijmy, że B to suma czasów wykonania wszystkich zadań. Jeżeli
wszystkie zadania będą przydzielone do jednej kałęzi, to jedna z liczb ma max, a druga zero. Liczby
A,B są naturalne i od 0 do B włącznie.

Wszystkie te pary na liście można zapisać też w sposób taki:

Tablica 2-wymiarowa od 0 do S. Skoro interesuje nas tylko istnienia pary liczb, to możemy to
istnienie liczb zakodować w tablicy tak:

<rys 6>

Złożoność algorytmu przy symetrycznych wartościach to O(n*2^n).
Jeżeli będziemy to za pomocą tablicy i-1 zapisywać, to mając taką tablicę konstruujemy taką samą
tablicę dla poziomu i. Przeszukujemy tamtą tablicę i szukamy jedynki. Ona oznacza, tak jakbyśmy
zapisali dwie nowe jedynki.

<rys 7>

Wypełniamy tablicę zerami, przeglądamy ją, jak znajdziemy jedynkę, to wstawiamy ją do tablicy.
Złożoność O(n*S^2)

S = Suma pi

JEżeli jesteśmy w węźle, tzn że podjęliśmy decyzję od zadania 1 do tego, w którym jesteśmy. Jeżeli
decyzja jest podjęta, to wiemy kjaklie zadania były przydzielone wcześniej, znamy ich czasy.
Znając A, możemy policzyć B. Bo to Suma B - A.

Wystarczy nam zatem:

<rys 9>

i tabela 1-wymiarowa od 0 do S. (dla i-1)
Dla (i) będzie podobnie.

Lepiej nie będzie, ale można przyśpieszyć.

Jakie może istnieć najlepsze rozwiązanie dla tego problemu.

(Suma s)/2 //zaokrąglenie w dół nawet!

Optymalne byłoby s/2 zadań.

Zatem indeksujemy do wartości s/2 i stworzenie nowej tablicy dla i będzie lepszym rozwiązaniem.
Bo zawsze mając odpowiednio większy czas na jednym procku niż s/2, to na drugim będzie
symetrycznie mniej.

Złożoność:

O(n*S/2)

PRzeszukując taką tablicę wystarczy, że bedziemy przeszukiwać tylko do pierwszej napotkanej
jedynki! Bo dalej są zera!

<rys 11>

Co nam to daje? Trochę szybciej będzie działać w niektórych przypadkach. Jak ten fakt
wykorzystać?

Najgorszy przypadek? Gdy każde kolejne zadanie jest dłuższe od poprzedniego.
A Najlepsze dla odwrotnej sytuacji.

Zatem może warto posortować zadania na początku? Należy to na własną rękę sprawdzic.

Co się jeszcze złego dzieje, podczas generowania tego weirsza? Jest np/. kilka jedynek
przedzielonych zerami. Fajnei byłoby przeskakiwać.

<rys 13>

Złożoność O(n*S)

Czas jest dobry. Pozostaje sprawa "S".

Schemat aproksymacyjny - rodzina algorytmów definiowana przez A(E), gdzie E > 0, taką, ze dla
zadanego parametru E, błąd algorytmu jest nie większy niż E, a jego złożoność obliczeniowa zależy
wielomianowo od rozmiaru instancji i w przypadku wielomianowych jest wykładnyczo zależna od
1/E.

A(E) definiuje sposób konstrukcji algorytmu i jego właściwość jest taka, że gwarantuje, że błąd
będzie nie większy niż Epsilon. Kosztem złożoności obliczeniowej oczywiście.

Przykład takiego schematu wielomianowego.

Problem P2||Cmax.

Sortujemy zadania (n) tak, że p1 >= P2 >= p3 >=... >= pn

Przenumerowujemy zadania.

Ustalamy wartość K i pierwsze k zadan wydzielamy z instancji i szukamy optymalnego zadania
wśród nich, np. przez przegląd zupełny. Intuicyjnie, jak to są największe zadania, to najwięcej
wnosządo kryterium Cmax. Reszta to kosmetyka.

To co zostanie można określić jakie będzie miało znaczenie.

Można np. algorytm Grahama (??)

<wzór 3>

W pełni wielomianowe schematy aproksymacyjne: Zbudujemy na podstawie alg programowania
dynakmicznego. To S trzeba zmianiać, aby działało szybciej. Więc na podstawie instancji I,
zrobimy instancję I':

<wzór 4>

Ciężko się jednak tworzy takie schematy aproksymacyjne.

J/akbyśmy chceili ten algorytm wykorzystać do programu z liczbami rzeczywistymi, to
musielibyśmy wprowadzić za k=1, i okazało by się, że wyszło by tak:

<wzór 5>