Online scheduling of multiprocessor jobs with preemption

• Název práce v češtině: Online rozvrhování víceprocesorových úloh s preempcí
• Název v anglickém jazyce: Online scheduling of multiprocessor jobs with preemption
• Klíčová slova: rozvrhování, online algoritmy, preempce, paralelní úlohy
• Klíčová slova anglicky: scheduling, online algorithms, preemption, multiprocessor jobs
• Akademický rok vypsání: 2017/2018
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.
• Řešitel: Mgr. Štěpán Šimsa - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.05.2018
• Datum zadání: 30.05.2018
• Datum potvrzení stud. oddělením: 20.07.2018
• Datum a čas obhajoby: 18.09.2018 00:00
• Datum odevzdání elektronické podoby: 20.07.2018
• Datum odevzdání tištěné podoby: 20.07.2018
• Datum proběhlé obhajoby: 18.09.2018
• Oponenti: doc. Mgr. Petr Kolman, Ph.D.

Zásady pro vypracování

Práce podá ucelený přehled výsledků pro rozvrhování paralelních úloh, který byl řešen v uvedených článcích. Pokusí se získat nové dolní a horní odhady kompetitivního poměru v některých konkrétních případech, např. pro 4 paralelní počítače.

Seznam odborné literatury

Aktuální články, včetně

J. Sgall, G. J. Woeginger: Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
In Proc. of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Comput. Sci. 8952, pages 236-247, Springer, 2015.

K.S. Hong and J.Y.-T. Leung. On-line scheduling of real-time tasks. IEEE Transactions on Computers 41, 1326-1331, 1992.

B. Johannes. Scheduling parallel jobs to minimize the makespan. Journal of Scheduling 9, 433-452, 2006.