[ Pobierz całość w formacie PDF ]

Uporządkuj zadania według EDD: Zπ(1), Zπ(2),...,Zπ(n);
A:=∅;
for i:=1 to n do begin
A:=A∪{Zπ(i)};
if ΣZj∈A pjdπ(i) then usuń z A najdłuŜsze zadanie;
Dla k=0,...,|A| najkrótszym (w sensie sumy
długości zadań) k–elementowym podzbiorem
zbioru Z', moŜliwym do uszeregowania bez
spóźnień jest A po skreśleniu jego |A|–k
najdłuŜszych zadań.
end;
Uporządkuj zadania według EDD: Zπ(1), Zπ(2),...,Zπ(n);
A:=∅;
for i:=1 to n do begin
A:=A∪{Zπ(i)};
if ΣZj∈A pjdπ(i) then usuń z A najdłuŜsze zadanie;
A – najliczniejszy moŜliwy podzbiór zadań, które
moŜna wykonać bez spóźnienia.
end;
Szereguj najpierw A według EDD, po nich pozostałe zadania
w dowolnym porządku;
Minimalizacja całkowitego spóźnienia 1||ΣT jest pseudowielomianowa.
14
Przykład. k=3
a
c
d
b
Minimalizacja liczby spóźnionych zadań na jednej
maszynie
Zadania niezaleŜne i niepodzielne
• Wersja z wagami 1||ΣwiUi jest NP–trudna jako uogólnienie problemu
plecakowego i podobnie jak dla problemu plecakowego znany jest
algorytm pseudowielomianowy.
• Podobny 1||ΣwiTi jest teŜ NP–trudny.
• Zagadnienia optymalizacyjne upraszczają się dla zadań
jednostkowych: P|pj=1|ΣwiUi i P|pj=1|ΣwiTi są wielomianowe np.
prosta redukcja do najtańszego skojarzenia w grafie dwudzielnym.
Minimalizacja liczby spóźnionych zadań na jednej
maszynie
Zadania zaleŜne i niepodzielne
NP–trudność pojawia się nawet dla zadań jednostkowych, w
zagadnieniach 1|pj=1,prec|ΣUi i 1|pj=1,prec|ΣTi.
Dowód. Problem kliki: dany jest graf G (V,E) i liczba k. Czy w G istnieje
pełny podgraf k–wierzchołkowy?
Redukcja PK
1|pj=1,prec|ΣUi: bierzemy zadania jednostkowe Zv z
di=|V∪E| dla wierzchołków v∈V oraz Ze z di=k+k(k–1)/2 dla krawędzi e∈E.
ZaleŜności kolejnościowe: Zv p Ze ⇔ v sąsiaduje z e. Limit L=|E|–k(k–1)/2.
Z
Zb
Zc
Zd
di=8
Z{a,c}
L=1
Z{b,c}
Z{c,d}
di=6
M 1
...
Z v Z v
...
Z v
Z e
Z e
...
Z
k
k+k(k-1)/2
|V∪E
W uszeregowaniu optymalnym wszystkie zadania kończą się do chwili
|V∪E|. JeŜeli ΣUi≤L, czyli co najmniej k(k–1)/2 zadań Ze wykona się przed
k+k(k–1)/2, ich krawędzie muszą sąsiadować z co najmniej k wierzchołkami
(których zadania Zv poprzedzają te Ze). Jest to moŜliwe jedynie, gdy k
wierzchołków tworzy klikę.
Podobnie przebiega redukcja PK
1|pj=1,prec|ΣTi.
Szeregowanie na procesorach dedykowanych
Przypomnienie
• zadania są podzielone na operacje (zadanie Zj ma operację Oij do
wykonania na maszynie Mi, o długości czasowej pij). Zadanie kończy się
wraz z wykonaniem swej najpóźniejszej operacji,
• dopuszcza się sytuację, gdy zadanie nie wykorzystuje wszystkich maszyn
(operacje puste),
• Ŝadne dwie operacje tego samego zadania nie mogą wykonywać się
równocześnie,
• Ŝaden procesor nie moŜe jednocześnie pracować nad róŜnymi operacjami.
Systemy obsługi:
• system przepływowy (flow shop) – operacje kaŜdego zadania są
wykonywane przez procesory w tej samej kolejności wyznaczonej przez
numery maszyn,
• system otwarty (open shop) – kolejność wykonania operacji w obrębie
zadań jest dowolna,
• inne, ogólniejsze ...
Szeregowanie na procesorach dedykowanych
System przepływowy
JuŜ przypadek trzech maszyn (F3||Cmax) jest NP–trudny.
Dowód. Problem podziału: dany jest ciąg a1,...an liczb naturalnych o
S=Σi=1,...,n ai parzystej. Czy istnieje jego podciąg o sumie S/2?
Redukcja PP
F3||Cmax: bierzemy n zadań o czasach (0,ai,0) i=1,...,n oraz
jedno z czasami (S/2,1,S/2). Pytamy o istnienie uszeregowania z Cmax≤S+1.
M1
M2
M3
S/2
...
1
...
S/2
S+1
Permutacyjny system przepływowy (PF): system przepływowy + [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

forum-gsm.htw.pl