Politechnika Poznańska
Wydział Informatyki
STRESZCZENIE ROZPRAWY DOKTORSKIEJ
mgr inż. Xin Chen
Wybrane zagadnienia szeregowania zadań na procesorach równoległych
w trybie online
( Selected Problems of Online Scheduling on Parallel Machines )
promotor: dr hab. inż. Małgorzata Sterna
Problem szeregowania zadań, który należy do klasycznych zagadnień
rozważanych m.in. w ramach optymalizacji kombinatorycznej i badań operacyjnych,
dotyczy przydziału ograniczonych zasobów (np. maszyn) do zbioru zadań, w celu
optymalizacji jednego lub kilku kryteriów. Problematyka ta została w pewnym sensie
zainspirowana przez rzeczywiste problemy występujące w przemyśle, i szerzej w
gospodarce, a następnie stała się przedmiotem szeroko zakrojonych badań w ramach
różnych dziedzin: wspomnianych już badań operacyjnych, badań systemowych, nauk
o zarządzaniu, informatyki itd. W trakcie długiej historii teorii szeregowania zadań
zaproponowano szereg modeli teoretycznych, inspirowanych rzeczywistymi
środowiskami produkcyjnymi i praktycznymi zastosowaniami, wzbogacając literaturę
przedmiotu wieloma interesującymi i wartościowymi rezultatami.
Badania nad zagadnieniami szeregowania zadań dotykają dwóch różnych aspektów o
charakterze teoretycznym z jednej strony i o charakterze praktycznym z drugiej.
Stosując pewne uproszczenie można uznać, że teoretycy zajmują się między innymi
proponowaniem nowych modeli opartych o obserwację świata rzeczywistego, ich
analizą z użyciem różnego rodzaju metod oraz proponowaniem algorytmów
rozwiązujących wyekstrahowane problemy. Natomiast praktycy wykorzystują
podejścia wypracowane przez teoretyków, dostosowując je do specyfiki konkretnych
problemów na które napotykają w rzeczywistości, sprawdzają ich efektywność w
rozwiazywaniu tych zagadnień, także w ramach eksperymentów obliczeniowych.
Problemy szeregowania zadań mogą być klasyfikowane z różnych punktów widzenia.
Jedna z możliwych klasyfikacji zakłada podział tych zagadnień na problemy
szeregowania w trybie offline i online, w zależności od dostępności informacji na
temat zadań. W pierwszym przypadku całość informacji o zadaniach do wykonania w
analizowanym systemie jest dostępna od razu, natomiast w drugim - informacja
pojawia się stopniowo. Zagadnienia szeregowania w trybie online związane są z
dwoma podstawowymi własnościami, które mogą być nieformalnie opisane dwoma
hasłami: niekompletność informacji i determinizm . Niekompletność informacji
1
oznacza, że dane na temat zadań nie są dostępne z wyprzedzeniem, natomiast
determinizm oznacza, że zadania pojawiające się w systemie muszą zostać
natychmiastowo uszeregowane i sposób ich wykonania nie może ulec zmianie.
Jednakże obie wspomniane własności, charakterystyczne dla zagadnień szeregowania
we właściwym trybie online (ang. pure online), mogą zostać w pewnym stopniu
złagodzone prowadząc do problematyki szeregowania zadań w trybie semi-online.
Rozprawa doktorska została poświęcona analizie teoretycznej problemów
szeregowania zadań w trybie online i semi-online.
Tego typu analiza obejmuje między innymi propozycje algorytmów rozwiązujących
zagadnienia wspomnianego typu, które nazywane są odpowiednio algorytmami online
i algorytmami semi-online. Do oceny jakości tych podejść wykorzystuje się metodę
analizy porównawczej (ang. competitive analysis), która pozwala na określenie
różnicy miedzy jakością rozwiązania uzyskanego w trybie online z jakością
rozwiązania, które może zostać skonstruowane w trybie offline. W metodzie analizy
porównawczej, wydajność algorytmu online (lub semi-online) jest mierzona z użyciem
współczynnika jakości (ang. competitive ratio). Załóżmy, że J oznacza sekwencję
zadań, A algorytm szeregowania, jakość rozwiązania utworzonego przez ten
algorytm czyli wartość kryterium (dla problemu minimalizacji lub maksymalizacji
tego kryterium), a jakość rozwiązania optymalnego dla wersji offline badanego
zagadnienia. Współczynnikiem jakości algorytmu A nazywana jest najmniejsza
wartość r taka, że dla dowolnej instancji wejściowej (dla problemu
minimalizacji kryterium) albo (dla problemu maksymalizacji). Jeśli
algorytm posiada współczynnik jakości r, wówczas nazywany jest algorytmem
r-konkurencyjnym (ang. r-competitive).
Ponadto, problem szeregowania zadań w trybie online lub semi-online ma dolne
ograniczenie (ang. lower bound) , jeśli żaden algorytm online nie posiada
współczynnika jakości mniejszego niż . Do wyznaczenia dolnego ograniczenia
problemów stosuje się metodę przeciwstawienia (ang. adversary method).
W podejściu tym dąży się do określenia trudnej sekwencji wejściowej zadań (ang.
adversary sequence), dla której żaden algorytm online nie jest w stanie skonstruować
dobrego rozwiązania (tzn. nie może osiągnąć współczynnika jakości mniejszego od
wartości dolnego ograniczenia). Podobnie, problem szeregowania zadań w trybie
online lub semi-online posiada górne ograniczenie (ang. upper bound) r, jeśli istnieje
algorytm online o współczynniku jakości r. Ponadto, jeśli algorytm online (lub semi-
online) posiada współczynnik jakości r równy dolnemu ograniczeniu problemu ,
wówczas jest on nazywany optymalnym (ang. optimal) lub najlepszym możliwym
(ang. best possible) algorytmem online (lub semi-online). Należy podkreślić, iż pojęcie
optymalności w kontekście algorytmów online nie oznacza, że algorytm jest w stanie
skonstruować uszeregowanie optymalne przy założeniu pełnej wiedzy o danych
problemu (rozwiązanie optymalne w trybie offline), ale oznacza jedynie, że żaden
algorytm online nie może zbudować lepszego rozwiązania. Jeśli dla określonego
problemu dolne ograniczenie jest zgodne z górnym ograniczeniem, oznacza to, że
problem posiada ścisłe ograniczenie (ang. tight bound).
2
Rozprawa doktorska rozpoczyna się krótkim wstępem do tematyki
szeregowania zadań, w szczególności zasygnalizowano w nim podział problemów na
wspomniane wcześniej kategorie: problemy typu offline, online i semi-online.
Omówiono podstawowe pojęcia z zakresu teorii złożoności obliczeniowej
wykorzystywane w pracy, prezentując m.in. klasyfikację problemów kombinatory-
cznych i metodę dowodzenia NP-zupełności opartą o transformację wielomianową.
W dalszej kolejności przedstawiono ogólną definicję problemu szeregowania zadań
wraz z notacją trójpolową ( ). W notacji tej, pole zawiera opis zbioru maszyn,
pole charakteryzuje zbiór zdań, a pole precyzuje funkcję kryterialną. Następnie
przytoczono podstawowe pojęcia związane z zagadnieniami szeregowani online tj.
współczynnik jakości, dolne ograniczenie, górne ograniczenie, optymalność
algorytmów online itd.
W kolejnym rozdziale rozprawy przedstawiono krótki przegląd literatury
związanej z poszczególnymi zagadnieniami rozważanymi w pracy. Przegląd ten
rozpoczyna się od prezentacji literatury poświęconej problemom szeregowania zadań
we właściwym trybie online (pure online), aby umożliwić ich porównanie z
problemami semi-online omówionymi w dalszej części rozdziału, w której opisano, w
szczególności, zagadnienia szeregowania w trybie semi-online z buforem (ang. with a
buffer) oraz z możliwością zmiany uszeregowania (ang. reassignment). Ponadto
przedstawiono wyniki uzyskane w literaturze dla problemu semi-online z
ograniczeniem hierarchicznym (ang. hierarchical constraint, GoS). Na koniec
omówiono tematykę szeregowania zadań z kryterium pracy spóznionej, będącej
przykładem nieklasycznej funkcji kryterialnej.
Właściwą część rozprawy stanowią wyniki uzyskane dla trzech modeli
szeregowania zadań w trybie online i semi-online na maszynach równoległych.
Zagadnienie szeregowania zadań na maszynach równoległych (ang. parallel) oparte są
na założeniu, iż każda z maszyn dostępnych w systemie może wykonać każde z
pojawiających zadań. Maszyny identyczne (ang. identical, P) pracują z tą samą
szybkością, maszyny jednorodne (ang. uniform, Q) różnią się współczynnikiem
szybkości, natomiast prędkość maszyn dowolnych (ang. unrelated, R) zależy od
zadania, które zostaje do nich przypisane.
(1) Pierwszym problemem rozważanym w rozprawie jest problem szeregowania
zadań na maszynach równoległych w trybie semi-online z możliwością zmiany
uszeregowania zadań.
Wspomniany model zakłada osłabienie własności determinizmu występującej we
właściwym trybie online, dopuszczając modyfikacje pierwotnie utworzonego
uszeregowania. W problemach szeregowania z możliwością zmiany uszeregowania,
po przyjęciu do systemu wszystkich zadań i ich przypisaniu do maszyn, istnieje szansa
zmiany przypisania określonej liczby zadań (K), w celu poprawy jakości funkcji
kryterialnej. W rozprawie poddano analizie dwa konkretne problemy szeregowania
tego typu dotyczące dwóch maszyn jednorodnych bez dodatkowych ograniczeń oraz
dwóch maszyn identycznych z ograniczeniem hierarchicznym. Oba problemy
3
rozważano w kontekście minimalizacji długości uszeregowania (ang. makespan,
Cmax).
(1.1) Problem Q2|online over list, reassignment|Cmax
Dane: Dwie maszyny równoległe jednorodne M1 i M2 o różnych prędkościach
wykonywania zadań wynoszących odpowiednio 1 i s e" 1. Zbiór zadań J = {J1, J2, ...,
Jn} przybywających do systemu sekwencyjnie, jedno po drugim (ang. over list), co
oznacza, iż kolejne zadanie pojawia się w systemie dopiero po uszeregowaniu
poprzedniego. Każde z zadań Jj jest opisane czasem wykonywania pj.
Cel: Uszeregowanie zadań ze zbioru J na maszynach M1 i M2 w celu minimalizacji
długości uszeregowania, czyli czasu zakończenia wykonywania ostatniego z zadań na
maszynach M1, M2.
Możliwość zmiany uszeregowania: Po przypisaniu wszystkich zadań ze zbioru J do
maszyn, pojawia się informacja o zakończeniu sekwencji wejściowej, dając możliwość
zmiany uszeregowania co najwyżej K e" 1 zadań, gdzie K jest wartością stałą, czyli
możliwość ich przesunięcia z jednej maszyny na drugą.
Dla zdefiniowanego powyżej problemu, wykazano w rozprawie nowe dolne
ograniczenie, poprawiające wynik znany z literatury. Stosując metodę
przeciwstawiania rozwiązań udowodniono, że dolne ograniczenie wynosi:
(s +1)2 1+ 5
s2 + s +1 1Ł s < 2
s2 1+ 5
rRA= Ł s < 2
2
s - s +1 2
s + 2
s ł 2
s +1
dla poszczególnych wartości szybkości maszyny M2 (s). W dowodzie wykorzystano
niekorzystną dla algorytmów online sekwencję wejściową zadań składającą się z
pierwszych t krótkich zadań o czasie wykonywania , gdzie > 0 jest odpowiednio
1
małą liczbą, taką że t = jest liczbą całkowitą. Po przypisaniu wspomnianych t zadań
e
do maszyn, poddano analizie trzy przypadki odpowiadające różnym wartościom
1+ 5 1+ 5
parametru reprezentującego szybkość maszyny s: 1Ł s < , Ł s < 2 i s ł 2 . W
2 2
każdym przypadku udowodniono, iż żaden algorytm online nie jest w stanie osiągnąć
lepszej wydajności niż podana powyżej dla odpowiednio spreparowanej sekwencji
zadań.
Następnie, w ramach analizy górnego ograniczenia wspomnianego problem
szeregowania, zaproponowano dwa algorytmy optymalne: SMU (Slow Machine
Underloaded) i SMF (Slow Machine First) oraz algorytm online poprawiający wynik
dostępny w literaturze SMO (Slow Machine just Overloaded). We wszystkich trzech
przypadkach przedstawiono w rozprawie ideę algorytmu wraz z dowodem jego
efektywności, czyli wykazano współczynnik efektywności danej metody. Każdy z
algorytmów oparty jest o podobną ideę działania składa się z fazy szeregowania i z
fazy zmiany uszeregowania. W pierwszej fazie, algorytm przypisuje zadania do
4
maszyn kierując się określoną strategią, natomiast w drugiej fazie przesuwa co
najwyżej K zadań pomiędzy maszynami dążąc do redukcji długości uszeregowania. W
szczególności:
(1.1.1) Algorytm SMU stara się w fazie szeregowania utrzymać wolniejszą z maszyn
niedociążoną, czyli długość uszeregowania częściowego na tej maszynie nie powinna
przekroczyć progu wynikającego z założonego współczynnika jakości (w pracy
zamieszczono precyzyjne definicje pojęcia maszyny przeciążonej i niedociążonej). W
drugiej fazie, metoda zmienia sposób wykonania jednego zadania (tzn. maszynę do
której jest ono przypisane) w celu skrócenia długości uszeregowania. W rozprawie
s+2
udowodniono, że współczynnik jakości algorytmu SMU wynosi dla dowolnego
s+1
współczynnika szybkości maszyny s e" 1. Dowód współczynnika jakości skupia się
przede wszystkim na przypadku, w którym stosunek długości uszeregowania i
naturalnego dolnego ograniczenia (wynikającego z łącznego czasu trwania zadań i
maksymalnego czasu trwania pojedynczego zadania) przekracza oczekiwaną wartość.
W tym celu udowodniono dwa lematy dotyczące własności uszeregowania, których
zachowanie zapewnia w trakcie swojego działania algorytm SMU. Na koniec
porównano jakość uzyskanego rozwiązania online z uszeregowaniem optymalnym dla
trybu offline.
Uwzględniając wykazane uprzednio dolne ograniczenie rozważanego problemu,
uzyskany wynik oznacza, że udowodniono ścisłe ograniczenie, a algorytm SMU jest
algorytmem optymalnym dla problemu Q2|online over list, reassignment|Cmax przy
założeniu, że s e" 2 i K e" 1.
(1.1.2) Algorytm SMF faworyzuje w procesie szeregowania zadań wolniejszą
maszynę, zapewniając, że konstruowane rozwiązanie posiada określone własności
istotne z punktu widzenia założonego współczynnika jakości. Następnie metoda
zmienia sposób uszeregowania dwóch zadań w celu redukcji długości uszeregowania.
W rozprawie udowodniono, że algorytm jest RA-konkurencyjny, prezentując definicję
współczynnika jakości RA, zróżnicowaną w zależności od wartości współczynnika
szybkości s. Dowód współczynnika jakości dla algorytmu SMF jest oparty o szereg
dodatkowych obserwacji oraz lematów. Wymagał wykazania między innymi dwóch
własności rozwiązania tworzonego przez metodę w fazie szeregowania, kluczowych
dla fazy zmiany uszeregowania.
Podobnie jak w przypadku algorytmu SMU, uwzględniając dolne ograniczenie
rozważanego problemu, uzyskany wynik oznacza, że algorytm SMF jest algorytmem
optymalnym dla problemu Q2|online over list, reassignment|Cmax przy założeniu, że
1 d" s < 2 and K e" 2.
(1.1.3) Wspomniane wcześniej algorytmy SMU i SMF są algorytmami optymalnymi
dla niemal wszystkich możliwych typów instancji wejściowych. Jedynym otwartym
podproblemem, dla którego nie zaproponowano dotychczas algorytmu optymalnego,
jest podproblem w którym 1 d" s < 2 i K = 1. Niemniej, w rozprawie przedstawiono
algorytm SMO, który nie jest w prawdzie metodą optymalną, ale charakteryzuje się
lepszym współczynnikiem jakości niż algorytmy dotychczas dostępne w literaturze. W
fazie szeregowania, metoda SMO utrzymuje szybszą maszynę w stanie niedociążenia
dopuszczając pewne przeciążenie wolniejszej z maszyn (należy podkreślić, iż definicja
5
stanu niedociążenia i przeciążenia została odpowiednio zmodyfikowana w porównaniu
do definicji użytych w analizie poprzednich algorytmów). W fazie zmiany
uszeregowania, algorytm SMO przesuwa najdłuższe z zadań pomiędzy maszynami,
jeśli tego rodzaju modyfikacja prowadzi do redukcji długości uszeregowania.
2(s+1)
W rozprawie udowodniono, że algorytm SMO jest -konkurencyjny przy
s+2
założeniu, że 1 d" s < i K = 1, a tym samym jest bardziej efektywny niż podejścia
"
opisane w literaturze. Dowód przytoczonego współczynnika efektywności oparto o
technikę sprowadzenia do sprzeczności przyjmując, że górne ograniczenie nie
obowiązuje dla pewnej minimalnej instancji problemu. Szczegółowa analiza
zaproponowanego kontrprzykładu, pozwoliła na uzyskanie sprzeczności z założeniem
o minimalnym rozmiarze sekwencji zadań.
Należy podkreślić, że omówiony uprzednio algorytm SMU charakteryzuje się wyższą
wydajnością od podejść znanych z literatury, dla pozostałych zakresów wartości
parametrów problemu, czyli "2 d" s < 2 i K = 1. Tym samym, zaproponowane
algorytmy SMO i SMU poprawiają wyniki dostępne w literaturze dla 1 d" s < 2 i K = 1,
dla których to wartości parametrów ścisłe ograniczenie problemu nie zostało
dotychczas udowodnione.
(1.2) Problem P2|online over list, GoS, reassignment|Cmax
Dane: Dwie maszyny równoległe identyczne M1 i M2 o takich samych prędkościach
wykonywania zadań. Zbiór zadań J = {J1, J2, ..., Jn} przybywających do systemu
sekwencyjnie. Każde z zadań Jj jest opisane czasem wykonywania pj. Ponadto każda
maszyna i zadanie opisane są współczynnikiem hierarchii g (g = 1 lub 2), który
oznacza, że zadanie Jj może być przypisane do maszyny Mi jedynie, jeśli
współczynnik hierarchii tego zadania (gJj) jest nie mniejszy niż współczynnik
hierarchii maszyny (gMi), tzn. gJj e" gMi.
Cel: Uszeregowanie zadań ze zbioru J na maszynach M1 i M2 w celu minimalizacji
długości uszeregowania.
Możliwość zmiany uszeregowania: Po przypisaniu wszystkich zadań ze zbioru J do
maszyn, pojawia się informacja o zakończeniu sekwencji wejściowej, dając możliwość
zmiany uszeregowania co najwyżej K e" 1 zadań, gdzie K jest wartością stałą, czyli
możliwość ich przesunięcia z jednej maszyny na drugą.
Dla zdefiniowanego powyżej problemu, wykazano w rozprawie ścisłe
ograniczenie, które wynosi 1,5.
W pracy zamieszczono dowód dolnego ograniczenia problemu, oparty o analizę
1
niekorzystnej sekwencji wejściowej rozpoczynającej się od t = odpowiednio małych
e
zadań, o czasie trwania wynoszącym i współczynniku hierarchii g = 2, oraz z
pewnych zadań dodatkowych. Następnie rozważono dwa przypadki w zależności od
relacji jaka występuje między czasem zakończenie zadań przypisanych do maszyny
M1 i M2.
W ramach analizy górnego ograniczenia rozważanego problemu,
zaproponowano algorytm HMF (High hierarchy Machine First). Metoda stara się w
fazie szeregowania przypisać maksymalną możliwą liczbę zadań do maszyny drugiej
M2, w sposób zgodny z hierarchią zadań i maszyn. Następnie, w fazie zmiany
6
uszeregowania, algorytm ma możliwość przesunięcia najdłuższego zadania między
maszynami. W rozprawie zamieszczono dowód 1,5-konkurencyjności algorytmu
HMF. Dowód ten oparto ponownie o technikę sprowadzenia do sprzeczności,
wyodrębniając dwa przypadki odpowiadające sytuacjom, w której algorytm dokonuje
zmiany uszeregowania w swojej drugiej fazie, lub też pozostawia pierwotne
rozwiązanie niezmienionym. W każdym z przypadków udowodniono, że długość
uszeregowania wygenerowanego przez metodę jest nie dłuższa niż 1,5-krotność
wartości naturalnego dolnego ograniczenia problemu.
Biorąc pod uwagę, że współczynnik jakości algorytmu HMF jest zgodny z
dolnym ograniczeniem problemu, zaproponowana metoda jest algorytmem
optymalnym. Tym samym, w rozprawie, udowodniono ścisłe ograniczenie (1,5) dla
problemu P2|online over list, GoS, reassignment|Cmax, zamykając analizę teoretyczną
tego zagadnienia.
(2) Drugim problemem rozważanym w rozprawie jest problem szeregowania
zadań na maszynach równoległych w trybie semi-online z wykorzystaniem
bufora.
Wspomniany model zakłada możliwość wykorzystania w procesie szeregowania
dodatkowego zasobu w postaci bufora o ograniczonym rozmiarze (B), w którym
przechowywane są zadania przed ostatecznym przypisaniem do maszyn. W momencie
pojawienia się nowego zadania w systemie, istnieje możliwość jego natychmiastowego
uszeregowania na maszynie lub też skierowanie go do bufora w celu pózniejszego
uszeregowania. Wprowadzenie bufora, prowadzi do modelu szeregowania w trybie
semi-online, oznacza bowiem relaksację własności determinizmu obowiązującej we
właściwym trybie online. W odróżnieniu od omówionego uprzednio modelu z
możliwością zmiany uszeregowania, który dopuszcza modyfikację raz podjętej
decyzji, model zakładający obecność bufora nie wymaga podjęcia decyzji o sposobie
wykonania zadania od razu po jego pojawieniu się w systemie decyzja taka może
zostać podjęta pózniej, w szczególności po zakończeniu wejściowej sekwencji zadań.
W rozprawie poddano analizie dwa konkretne problemy szeregowania tego typu
dotyczące dwóch maszyn identycznych lub jednorodnych bez dodatkowych
ograniczeń oraz dwóch maszyn identycznych z ograniczeniem hierarchicznym.
Podobnie jak poprzednio, oba problemy rozważano w kontekście minimalizacji
długości uszeregowania.
(2.1) Problem X|online over list, buffer|Cmax (gdzie X{P, P3, Q})
Dane: Zbiór maszyn równoległych identycznych albo jednorodnych M = {M1, M2, ...,
Mm} o takich samych albo różnych prędkościach wykonywania zadań. Zbiór zadań J =
{J1, J2, ..., Jn} przybywających do systemu sekwencyjnie. Każde z zadań Jj jest
opisane czasem wykonywania pj.
Cel: Uszeregowanie zadań ze zbioru J na maszynach M1 i M2 w celu minimalizacji
długości uszeregowania.
Bufor: W odróżnieniu od właściwego trybu online, podczas procesu szeregowania
zadań, wykorzystywany jest bufor o stałym rozmiarze B umożliwiający chwilowe
7
przechowanie zadań przed ich ostatecznym przypisaniem do maszyn. Każde nowo
przybyłe zadanie, może zostać obsłużone na dwa sposoby: poprzez przypisanie go do
jednej z maszyn lub poprzez zmagazynowanie w buforze w celu pózniejszego
przypisania. Jeśli w chwili pojawienia się nowego zadania w systemie bufor jest pełen,
jedno z zadań musi zostać z niego usunięte i uszeregowane na maszynie, zanim
możliwe będzie wprowadzenie do bufora nowego zadania. Należy podkreślić, iż raz
dokonane przypisanie zadania do maszyny nie może ulec zmianie: zadanie takie nie
może zostać przesunięte do bufora albo skierowane na inną maszynę. W momencie
zakończenia sekwencji wejściowej wszystkie zadania znajdujące się w buforze muszą
zostać przypisane do maszyn.
Omówiony powyżej problem szeregowania na maszynach identycznych
(P|online over list, buffer|Cmax) był już analizowany w literaturze wykazano jego
dolne ograniczenie oraz zaproponowano kilka algorytmów online. Jednakże dostępne
rezultaty mogą zostać poprawione z dwóch punktów widzenia, poprzez
zaproponowanie algorytmów wykorzystujących bufor o mniejszym rozmiarze przy
zachowaniu tego samego współczynnika jakości lub posiadających lepszy
współczynnik jakości przy takim samym rozmiarze bufora.
W rozprawie zastosowano obie koncepcje, proponując trzy algorytmy poprawiające
wyniki dostępne w literaturze: BUM (algorithm for problem with a BUffer on M
identical machines), BUT (algorithm for problem with a BUffer on Three identical
machines) oraz BUU (algorithm for problem with a BUffer on Uniform machines).
Każdy ze wspomnianych algorytmów składa się z dwóch etapów: iteracji oraz
finalizacji. W fazie iteracyjnej, algorytm umieszcza w buforze B początkowych zadań,
a następnie porównuje najmniejsze z nich z nowo przybyłym zadaniem. Każdorazowo
metoda umieszcza większe z tych zadań w buforze, natomiast mniejsze jest przypisane
do maszyny zgodnie z pewną przyjętą strategią. W fazie finalizacji, algorytm
szereguje zadania znajdujące się dotychczas w buforze na maszynach tak jak w trybie
offline.
(2.1.1) Algorytm BUM pozwala na rozwiązanie problemu szeregowania na
maszynach równoległych identycznych, P|online over list, buffer|Cmax, przy założeniu,
że liczba maszyn jest wystarczająco duża (m e" 23) z wykorzystaniem bufora o
# # # #
rozmiarze . W fazie iteracyjnej metoda przechowuje największych zadań
w buforze, równocześnie zapewniając możliwość ich pózniejszego uszeregowania na
określonej maszynie, poprzez zachowanie założonego współczynnika jakości w
trakcie szeregowania pozostałych zadań. Mianowicie, algorytm przypisuje zadania do
maszyn w taki sposób, że ich obciążenie jest co najwyżej 1,5-krotnie większe od
naturalnego dolnego ograniczenia tego problemu. W fazie finalizacji, metoda
przypisuje m największych zadań oczekujących w buforze do odpowiednich maszyn, a
pozostałe zadania przydziela kierując się strategią zachłanną.
Opierając się na szeregu pomocniczych obserwacji i lematów, w rozprawie
udowodniono, że współczynnik jakości algorytmu BUM wynosi 1,5. Metoda
wykazuje więc taką samą efektywność jak podejścia znane z literatury. Jednakże
algorytm BUM wykorzystuje mniejszy bufor niż konkurencyjne podejścia, a tym
samym w lepszy sposób gospodaruje tym dodatkowym zasobem.
8
(2.1.2) Drugi z zaproponowanych algorytmów, poprawiający wyniki dostępne w
literaturze, algorytm BUT, jest przeznaczony do rozwiązywania problemu
szeregowania na trzech maszynach równoległych identycznych z buforem, P3|online
over list, buffer|Cmax.
Idea metody BUT i jej struktura jest zbliżona do algorytmu BUM, z tym że w fazie
iteracyjnej w buforze przechowywanych jest 6 największych zadań, a pozostałe
zadania przypisywane są do maszyn dysponujących odpowiednio dużą rezerwą
czasową. W fazie finalizacji, BUT kieruje 6 zadań znajdujących się w buforze na
maszyny, podejmując decyzję o maszynie docelowej na podstawie rozmiaru zadania.
W rozprawie wykazano, że metoda BUT posiada współczynnik jakości , równy
dolnemu ograniczeniu tego problemu. Dotychczas dostępny w literaturze algorytm
optymalny wykorzystywał w procesie konstrukcji uszeregowania bufor o rozmiarze 9.
Nowe podejście pozwala na redukcję rozmiaru bufora do zaledwie 6, przy zachowaniu
optymalnego współczynnika jakości.
(2.1.3) Ostatni z zaproponowanych algorytmów metoda BUU przeznaczony jest
do rozwiązywania problemu szeregowania na maszynach równoległych jednorodnych
z buforem - Q|online over list, buffer|Cmax, w którym maszyny różnią się prędkością
wykonywania zadań (si). Celem szeregowania jest konstrukcja rozwiązania
minimalizującego długość uszeregowania z wykorzystaniem bufora o rozmiarze m.
Podobnie jak w przypadku maszyn identycznych, algorytm BUU działa w dwóch
fazach. W fazie iteracyjnej metoda w pełni wykorzystuje bufor o rozmiarze m, a w
fazie finalizacji przesuwa zadania z bufora na maszyny kierując się dwoma
strategiami, zależnie od rozmiaru największego z nich.
W pracy wykazano, że współczynnik jakości algorytmu BUU wynosi 2 - + .
Poprawiono tym samym wynik dostępny w literaturze, w której omówiono metodę
wykorzystującą bufor o tym samym rozmiarze m, ale charakteryzującą się gorszym
współczynnikiem jakości 2 + .
(2.2) Problem P2|online over list, GoS, buffer|Cmax
Podobnie jak w przypadku modelu z możliwością zmiany uszeregowania zadań,
badania nad zagadnieniem szeregowania z buforem uzupełniono również o analizę
problemu z dodatkowym ograniczeniem ograniczeniem hierarchicznym.
Dane: Dwie maszyny równoległe identyczne M1 i M2 o takich samych prędkościach
wykonywania zadań. Zbiór zadań J = {J1, J2, ..., Jn} przybywających do systemu
sekwencyjnie. Każde z zadań Jj jest opisane czasem wykonywania pj. Ponadto każda
maszyna i zadanie opisane są współczynnikiem hierarchii g (g = 1 lub 2). Zgodnie z
przyjętymi założeniami, maszyna M1 może wykonać każde z zadań zgłoszonych do
systemu, natomiast maszyna M2 może przetwarzać jedynie zadania o współczynniku
hierarchii 2, tym samym zadania o współczynniku hierarchii 1 muszą być wykonane
na maszynie M1.
Cel: Uszeregowanie zadań ze zbioru J na maszynach M1 i M2 wykorzystujące bufor o
rozmiarze B w celu minimalizacji długości uszeregowania.
9
W rozprawie udowodniono, że dolne ograniczenie przedstawionego problemu
wynosi 1,5, posługując się niekorzystną sekwencją zadań podobną do sekwencji użytej
w badaniach nad analogicznym problemem dopuszczającym zmianę uszeregowania
(pkt 1.2). Ponadto zaproponowano algorytm LJL (Largest Job Last) wykorzystujący
bufor o jednostkowym rozmiarze. Metoda przechowuje największe zadanie o
współczynniku hierarchii 2 w buforze, a po zakończeniu sekwencji wejściowej
przypisuje je do maszyny charakteryzującej się najmniejszym obciążeniem.
W rozprawie udowodniono, stosując metodę przeciwstawiania rozwiązań, że
współczynnik jakości nowego algorytmu wynosi 1,5 i jest równy dolnemu
ograniczeniu problemu. Tym samym wykazano, że metoda LJL jest algorytmem
optymalnym i określono ścisłe ograniczenie dla problemu P2|online over list, GoS,
buffer|Cmax.
(3) Trzecim problemem rozważanym w rozprawie jest problem szeregowania
zadań na maszynach równoległych w trybie online z kryterium pracy spóznionej.
W zagadnieniach szeregowania zadań z kryterium pracy spóznionej (ang. late work,
Y) zadania Jj opisane są nie tylko czasem trwania, ale również oczekiwanym czasem
zakończenia ich wykonywania dj (ang. due date). Jeśli w zaproponowanym
rozwiązaniu, zadanie kończy się po oczekiwanym terminem dj, w trakcie oceny
jakości takiego rozwiązania pojawia się czynnik kary, równy rozmiarowi spóznionej
części zadania, wykonanej po dj. Celem szeregowania z kryterium pracy spóznionej
jest minimalizacja łącznego rozmiaru spóznionych części wszystkich zadań.
W rozprawie rozważano najprostszy model szeregowania zadań z kryterium pracy
spóznionej, zakładający wspólny żądany termin zakończenia wykonywania wszystkich
zadań, dj = d. Badania rozpoczęto od podstawowego modelu, ponieważ tego typu
zagadnienia nie były dotychczas rozważane w trybie online. Przytoczono dowód
binarnej NP-trudności wersji offline oparty o transformację wielomianową problemu
podziału zbioru. Następnie zaproponowano metodę oceny jakości algorytmów online
minimalizujących pracę spóznioną. W przypadku tej funkcji kryterialnej, optymalna
wartość pracy spóznionej w trybie offline może być zerowa, jeśli wszystkie zadania
zostaną ukończone przed oczekiwanym terminem ich wykonania. W takiej sytuacji nie
można określić współczynnika jakości wyrażonego jako stosunek niezerowej pracy
spóznionej wyznaczonej przez algorytm online do zerowej wartości optymalnej. W
rozprawie zaproponowano wykorzystanie w procesie analizy algorytmów online
koncepcji pracy wczesnej, w której dąży się do maksymalizacji części zadań
wykonanych przed żądanym terminem zakończenia wykonywania. Ponieważ praca
wczesna przyjmuje wyłącznie niezerowe wartości (poza przypadkiem trywialnym)
umożliwia analizę efektywności algorytmów online.
W ramach badań na zagadnieniami minimalizacji kryterium pracy spóznionej w trybie
online rozważono trzy problemy szeregowania online i semi-online.
(3.1) Problem P|online over list, dj = d|Y
Dane: Zbiór maszyn równoległych identycznych M = {M1, M2, ..., Mm} o takich
samych prędkościach wykonywania zadań. Zbiór zadań J = {J1, J2, ..., Jn}
10
przybywających do systemu sekwencyjnie. Każde z zadań Jj jest opisane czasem
wykonywania pj oraz wspólnym żądanym terminem zakończenia wykonywania dj = d.
Cel: Uszeregowanie zadań ze zbioru J na maszynach M1 i M2 w celu minimalizacji
pracy spóznionej.
Dla zarysowanego powyżej problemu szeregowania we właściwym trybie
online zaproponowano algorytm EFF (Extended First Fit), wykorzystujący
podobieństwo analizowanego modelu do problemu pakowania. Idea metody opiera się
na przypisaniu nowego zadania do pierwszej z maszyn która pozwala na jego
wykonanie, z uwzględnieniem założonego współczynnika jakości. W rozprawie
2m2 -2m+1-1
udowodniono, że współczynnik jakości algorytmu EFF wynosi , gdzie m
m-1
oznacza liczbę maszyn w systemie. Dowód skupia się na analizie dwóch
nietrywialnych przypadków, w których obciążenie wszystkich maszyn nie przekracza
oczekiwanego czasu zakończenia wykonywania d oraz, przeciwnie, wszystkie
maszyny kończą przetwarzanie zadań po tym czasie. W pozostałych przypadkach
wykazano, że algorytm online konstruuje rozwiązanie równoważne rozwiązaniu
osiągniętemu w trybie offline.
Następnie udowodniono, że rozważany problem szeregowania zadań posiada
dolne ograniczenie równe 5 -1 1.236. W dowodzie wykorzystano klasyczną
niekorzystną sekwencję wejściową zadań, składającą się z 2 zadań o rozmiarze 1, albo
z 3 zadań o rozmiarach 1, 1, 2, znaną z analizy zagadnień szeregowania z kryterium
długości uszeregowania. Wartość wspólnego żądanego terminu zakończenia
"
wykonywania ustalono na . Tym samym, zaproponowany w rozprawie
algorytm EFF jest algorytmem optymalnym dla problemu szeregowania zadań na
dwóch maszynach identycznych P2|online over list, dj = d|Y.
(3.2) Problem P2|online over list, dj = d, sum|Y
Drugim zagadnieniem rozważanym w trybie semi-online z kryterium pracy spóznionej
był problem szeregowania zadań na dwóch maszynach identycznych, ze wspólnym
żądanym terminem zakończenia wykonywania, w którym dostępna jest informacja o
łącznym czasie trwania wszystkich zadań (sum). W modelu tym nastąpiło więc
osłabienie własności niekompletności informacji występującej w modelu online.
W rozprawie udowodniono ścisłe ograniczenie wspomnianego problemu, które wynosi
. Oznacza to, iż wykazano dolne i górne ograniczenie problemu, których wartości się
pokrywają. Dowód dolnego ograniczenia oparto o niekorzystne sekwencje zadań
zawierające zadania o czasie trwania (1, 1, 2, 2) oraz (1, 1, 1, 3). W ramach analizy
górnego ograniczenia zaproponowano algorytm OMF (One Machine First) oraz
udowodniono, że jego współczynnik jakości wynosi , wykazując tym samym, że jest
to algorytm optymalny.
(3.3) Problem P2|online over list, dj = d, OPT|Y
Stosując podobne podejście jak w przypadku wcześniej omówionego problemu, w
rozprawie zbadano problem szeregowania zadań z kryterium pracy spóznionej na
dwóch maszynach identycznych, w trybie semi-online, przy założeniu, że dostępna
11
jest a priori dodatkowa informacja o optymalnej wartości kryterium (OPT).
Udowodniono ścisłe ograniczenie tego problemu, które wynosi również . Stosując
analogiczne do uprzednio wspomnianych niekorzystne sekwencje zadań, z wartością
optymalną kryterium OPT=6, udowodniono dolne ograniczenie problemu. Dowodząc
górnego ograniczenia zaproponowano algorytm MOMF (Modified One Machine First)
będący adaptacją metody OMF.
Poza zarysowanymi powyżej wynikami dotyczącymi trzech modeli
szeregowania zadań na procesorach równoległych w trybie online i semi-online,
rozpraw doktorska zawiera również wyniki dodatkowe, dotyczące między innymi
porównania analizowanych zagadnień.
W pracy dokonano porównania zagadnień szeregowania semi-online z możliwością
zmiany uszeregowania z zagadnieniem szeregowania z wykorzystaniem bufora. Na
przykładzie konkretnych instancji tych problemów, pokazano, iż pomimo dużego
podobieństwa tych modeli, nie są to modele identyczne, w szczególności biorąc pod
uwagę możliwość uzyskania przez algorytm semi-online rozwiązania optymalnego dla
trybu offline. Z drugiej strony oba zagadnienia analizowane są w podobny sposób, w
celu określenia ich dolnych oraz górnych ograniczeń. Wykazane w rozprawie
podobieństwa i różnice między wspomnianymi modelami szeregowania zadań w
trybie semi-online wskazują na interesujący kierunek dalszych badań, które mogłyby
zostać poświęcone usystematyzowanej analizie ich wzajemnych powiązań.
Następnie, w rozprawie zestawiono ze sobą problematykę szeregowania zadań na
maszynach równoległych z kryterium długości uszeregowania oraz z kryterium pracy
spóznionej. Wskazano na pewne podobieństwa i różnice pomiędzy tymi modelami,
podkreślając, że ich systematyczne zbadanie również stanowi interesujący kierunek
dalszych prac.
Podsumowując rozprawę, zebrano i skomentowano wszystkie uzyskane
rezultaty. Wyniki przedstawione w pracy pokazują, iż dalsze badania nad problemami
szeregowania w trybie online poza wspomnianymi wcześniej propozycjami
powinny podążać dwoma równoległymi torami. Z jednej strony istnieje możliwość
poprawy rozwiązań dostępnych w literaturze poprzez propozycję algorytmów
charakteryzujących się wyższą wydajnością w sensie jakości rozwiązań lub ilości
użytych zasobów. Z drugiej strony bogactwo modeli szeregowania zadań, które nie
były dotychczas rozważane w trybie online, stwarza szansę uzyskiwania wielu
całkowicie nowych rezultatów.
12
Wyszukiwarka
Podobne podstrony:
BORODO STRESZCZENIE antastic plWESELE streszczenie szczegółowe i bohnotatek pl irydion streszczenie utworustreszczenie raportu pzh dla portaluStreszczenie Pieśni VI IliadyBAZY DANYCH Streszczenie z wykładówStreszczenieĹšwiÄ™toszek streszczenie2 Kamizelka streszczenieStreszczenie Pana KleksaSciaga pl Streszczenie ChłopówPOTOP streszczenieStreszczenie Grażyny07 Chen GCEP WorkshopPanTadeusz Streszczeniewięcej podobnych podstron