Tak

1||Cmax

wszystko działa - łatwy

1|prec|Cma

sort topologiczny - łatwy

1|rj|Cmax

sort po rj - łatwy

1||Lmax

sort po dj - łatwy

1|rj, pmtn|Lmax

(Algorytm Horna) - sort po dj, wykonywanie zadań które są gotowe(rj), przerwanie jeśli są gotowe zadania o wcześniejszym dj - łatwy

1||sum(Cj)

sort po pj - łatwy

1||sum(wjCj)

sort po pj/wj - łatwy

1||sum(Uj)

(algorytm Hodgsona) sort po dj, wyluczenie na pewno spóźnionych(spóźnionen na końcu) - łatwy

1||Y

np-trudny

1 | pj = p | Y

(algorytm Jacksona) sort po dj, u = floor(Dmax/p) v= ceil(Dmax/p) best z (Tu+1, Tn) (T1, Tu) (Tv+1, Tn) (T1, Tv)

Algorytmy listowe - co to?

proste algorytmy przydzielające zadania względem sort, jakiejś listy(jak jacksona)

Maszyna P

parralel - identyczna (wszystkie czasy przetwarzania identyczne na każdej maszynie)

Maszyna Q

uniQ - jednorodna (różne prędkości maszyn)

Maszyna R

unRelated - dowolne(każde zadanie rózna prędkość na różnych maszynach

P | pmtn | Cmax

(Algorytm McNaughtona) Cmax = max(max(pj), 1/m*sum(pj)), dopóki czas na maszynie mniejszy od Cmax{dodawaj zadania}, w przeciwnym wypadku, przerwij zadanie i dodaj jego reszte do następnej maszyny

P||Cmax

np-trudny, istnieje algorytm aproksymacyjny - sort po pj

1, O, F, Pk, Qk, Q, Rk, R, J, FFS

1 -> O, F, Pk | Pk->P, Qk->Q, Rk -> R | F->J, FFK

...

...

...

...

Cmax, Lmax, D|E, Dw|Ew, U, Uw, Y, Yw, F, Fw

Cmax->Lmax->(D|E -> Dw|Ew, U->Uw, Y->Yw, F->Fw, D|E

Problem P | in-tree, pj = 1 | Cmax

łatwy (algorytm Hu) - oblicz poziomy zadań(gdzie poziom to oddalenie od ostatniego możliwego do wykonania zadania), wykonaj m zadań, przekalkuluj poziomy...

Problem P | pmtn, rj | Yw

łatwy (min-cost, max-flow + McNaughton) Ojcze Nasz żeby tego nie było

Problem P2 | dj = d | Y

np-trudny - programowanie dynamiczne - f(j, A, B) = min(max(0, pj-A) + f(j-1, A, B), ...)