Selected Problems of Online Scheduling on Parallel Machines
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
PL Wybrane zagadnienia szeregowania zadań na procesorach równoległych w trybie online
english
- scheduling problems
- online scheduling
- semi-online scheduling
- competitive analysis
- problem szeregowania zadań
- szeregowanie w trybie online
- szeregowanie w trybie offline
- analiza porównawcza
EN This thesis concerns three selected online scheduling problems on parallel machines, identical as well as uniform ones, where jobs arrive into the system one by one over list, and the decision on their assignment to machines should be made without knowing the whole information on jobs sequence in advance. First, online scheduling problem with reassignment is considered, which means that after the input ends, some of jobs can be reassigned from the current machine to others. The second topic is devoted to online scheduling with a buffer, where a reordering buffer with fixed size can be used during the scheduling to store jobs temporarily. The third part of the thesis concerns online scheduling with late work criterion and a common due date, where pure online as well as two semi-online scheduling problems are investigated. For the models mentioned lower bounds are proven and upper bounds are provided by proposing several online algorithms and determining their competitive ratio.
PL Rozprawa dotyczy trzech wybranych zagadnień szeregowania w trybie online na maszynach równoległych, identycznych i jednorodnych. W systemach tego typu zadania przybywają jedno po drugim i decyzja o sposobie ich wykonania jest podejmowana przy braku informacji na temat kolejnych zadań, które mogą się jeszcze potencjalnie pojawić. W pracy rozważano problem szeregowania w trybie online przy założeniu możliwości zmiany sposobu uszeregowania pewnej liczb zadań po zakończeniu sekwencji wejściowej oraz problem szeregowania w trybie online z buforem, w którym zadania są chwilowo lokowane w celu późniejszego uszeregowania.Trzecim rozważanym zagadnieniem był problem szeregowania z kryterium pracy spóźnionej i wspólnym żądanym terminem zakończenia wykonywania zadań, który zbadano we właściwym trybie online, jak i w trybie semi-online. Dla podanych modeli udowodniono dolne ograniczenia oraz wykazano górne ograniczenia proponując szereg algorytmów wraz z określeniem ich współczynników jakości.
109
computer sciences and computer science
computer science
public
Piotr Jędrzejowicz
Gdynia, Polska
04.08.2014
english
public
Erwin Pesch
Siegen, Niemcy
28.09.2014
english
public
dissertation
Poznań, Polska
03.11.2014
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności: teoria szeregowania zadań